Затор на дорозі#1925
Найбільш дратівливим аспектом дорожніх заторів у великих містах є те, що водії постійно намагаються різко змінювати смугу руху в надії поїхати швидше. У цій задачі вам потрібно визначити, чи є така стратегія розумною.
Ми розглянемо відносно просту математичну модель затору. Припустимо, що є дорога з смугами, пронумерованими від до , і -та смуга рухається зі швидкістю b_i + a_i \cdot \sin(t + \delta_i) у момент часу . Завжди виконується умова b_i > a_i, тобто швидкість завжди додатна. Ви можете змінювати смугу у будь-який момент; перехід із смуги на смугу займає c \cdot |x - y| одиниць часу. Протягом цього часу ви не просуваєтеся вперед.
Визначте мінімальний час, необхідний для проїзду відстані , а також спосіб досягнення цього часу. Ви починаєте у момент часу на смузі . Закінчити рух можна на будь-якій смузі.
Перший рядок містить два цілих числа і та дійсне число (1 \leq N \leq 5, 1 \leq d \leq 1000, 0.001 \leq c \leq 1000). Наступні рядків описують смуги; кожен містить два цілих числа a_i та b_i і дійсне число \delta_i (0 \leq a_i < b_i \leq 100, 0 \leq \delta_i < 2\pi).
Виведіть у першому рядку мінімальний час, необхідний для проїзду відстані . У другому рядку виведіть число — кількість необхідних змін смуги. не повинно перевищувати 10^6; гарантовано, що завжди існує оптимальна стратегія, яка вимагає не більше 10^6 змін смуги. У наступних рядках виведіть самі зміни; кожен рядок повинен містити новий номер смуги та момент часу, коли починається зміна смуги. Зміни повинні бути впорядковані у хронологічному порядку. Якщо існує декілька можливих розкладів, виведіть будь-який із них.
Виводьте всі дійсні числа з максимально можливою точністю. Ваш розв'язок буде вважатися правильним, якщо при перевірці розбіжності не перевищуватимуть 10^{-6} (при перевірці загальної пройденої відстані, чи не перетинаються зміни смуги тощо). Тому рекомендується виводити принаймні 10–12 знаків після десяткової крапки у кожному дійсному числі.
Приклад 1