Задача №113339. Верёвочный парк
В парке развлечений «Пуперленд» открылся огромный верёвочный парк. Особая гордость парка — трасса, состоящая из \(n\) платформ, соединённых \(n − 1\) верёвками: первая платформа соединена со второй, вторая — с третьей, \(\dots\) , \(n − 1\)-я — с \(n\)-й, верёвка, соединяющая \(i\)-ю платформу с \(i + 1\)-й имеет длину \(l_i\) .
В парке серьёзно относятся к технике безопасности, так что для трассы были разработаны следующие правила эксплуатации:
- для всех \(i\) от \(2\) до \(n − 1\) на \(i\)-й платформе разрешается находиться не более, чем \(p_i\) людям одновременно; (первая и последняя платформы достаточно надёжны, и на них может находиться произвольное число людей);
- на верёвке, протянутой между \(i\)-й и \(i + 1\)-й платформами, разрешается находиться не более, чем \(r_i\) людям одновременно;
- для каждой верёвки известно минимальное безопасное расстояние \(d_i\) метров, такое что двум людям, одновременно идущим по этой верёвке, нельзя приближаться друг к другу ближе, чем на это расстояние.
Все люди разные и будут проходить трассу с разной скоростью. Пронумеруем посетителей от 1 до \(m\) в том порядке, в котором они выстроились в очередь. Для \(j\)-го посетителя известна скорость \(v_{i,j}\) м/c — максимальная скорость, с которой он может проходить по верёвке, соединяющей \(i\)-ю и \(i + 1\)-ю платформы. Таким образом, \(j\)-й посетитель может перемещаться по \(i\)-й верёвке с любой скоростью от 0 до \(v_{i,j}\) , соблюдая при этом условия про минимальное расстояние до других посетителей, идущих по той же верёвке.
Администрация парка не ожидала такого наплыва посетителей и теперь опасается, что все посетители могут не успеть пройти трассу до закрытия парка. Помогите им посчитать минимальное время, которое потребуется всем посетителям, чтобы пройти трассу
В первой строке заданы два целых числа \(n (2 \le n \le 100)\) и \(m (1 \le m \le 100)\) — число платформ на трассе и число посетителей.
Во второй строке заданы \(n − 2\) целых числа \(p_2, \dots , p_{n−1} (1 \le p_i \le 100)\) — ограничения на число людей на платформах. Обратите внимание, что если \(n = 2\), то эта строка пуста.
В следующей строке задано \(n − 1\) целое число \(r_1, r_2, \dots , r_{n−1} (1 \le r_i \le 100)\) — ограничение на число людей на \(i\)-й верёвке.
В следующей строке задано \(n − 1\) целое число \(l_1, l_2, \dots , l_{n−1} (1 \le l_i \le 100)\) — длины верёвок в метрах.
В следующей строке задано \(n − 1\) целое число \(d_1, d_2, \dots , d_{n−1}\) — ограничение в метрах на расстояние между людьми на \(i\)-й верёвке. Гарантируется, что \(1 \le d_i \le l_i\).
В оставшихся \(n − 1\) строке находится по \(m\) целых чисел: \(\)v_{1,1}, v_{1,2}, \dots , v_{1,m}\(\) \(\)v_{2,1}, v_{2,2}, \dots , v_{2,m}\(\) \(\)\dots\(\) \(\)v_{n−1,1}, v_{n−1,2}, \dots , v_{n−1,m},\(\) где \(v_{i,j}\) — скорость в м/с \(j\)-го посетителя на \(i\)-й верёвке (\(1 \le v_{i,j} \le 100\)).
Выведите единственное число — время в секундах, которое необходимо, чтобы все посетители прошли трассу
Ваш ответ должен иметь относительную или абсолютную погрешность не больше \(10^{−6}\).
Таким образом, он будет засчитан, если \(|a−p|/max(a,1) \le 10^{−6}\) , где \(p\) — ваш ответ, а \(a\) — правильный ответ
2 1 1 30 2 2
15.0
3 2 1 2 2 10 10 5 5 2 2 1 2
17.5