|
Колесо Фортуны
(Время: 1 сек. Память: 16 Мб Сложность: 37%)
Первоначально определим множество секторов, над которыми может оказаться стрелка. Для этого установим минимальное и максимальное количество переходов между секторами. Минимальное количество переходов достигается при наименьшей скорости вращения a и равно na = (a-1) div k, а максимальное значение соответственно будет при максимальной скорости b и будет равно nb = (b-1) div k. Это означает, что при вращении колеса против часовой стрелки мы пройдем все сектора от 1 + na mod n до 1 + nb mod n. Аналогично можно определить множество секторов, над которыми окажется стрелка при вращении колеса в другую сторону.
В силу ограничений, накладываемых на n, a и b, стрелка может проходить значительное число секторов, достаточное для того, чтобы программа, полностью моделирующая процесс вращения колеса, не уложилась по времени. Для решения данной проблемы достаточно определить: будет ли колесо совершать полный оборот? И если будет, то за ответ можно будет взять максимальный элемент среди чисел всех секторов. Или, как другой вариант, в случае большого числа оборотов можно положить, что nb = na+n-1, тогда не придется рассматривать этот случай отдельно.
Алгоритмическая реализация данной задачи может быть описана следующим образом:
read(n)
for i=1..n read(x[i])
read(a,b,k)
na = (a-1) div k
nb = (b-1) div k
if(nb-na >= n-1) nb = na+n-1
m = -1
for i = na..nb
m = max(m, x[i mod n + 1], x[n - (n+i-1) mod n])
writeln(m)
| |
