Страница: 1 Отображать по:
#3182
Колесо Фортуны
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Развлекательный телеканал транслирует шоу «Колесо Фортуны». В процессе игры участники шоу крутят большое колесо, разделенное на сектора. В каждом секторе этого колеса записано число. После того как колесо останавливается, специальная стрелка указывает на один из секторов. Число в этом секторе определяет выигрыш игрока.

Юный участник шоу заметил, что колесо в процессе вращения замедляется из-за того, что стрелка задевает за выступы на колесе, находящиеся между секторами. Если колесо вращается с угловой скоростью \(v\) градусов в секунду, и стрелка, переходя из сектора \(X\) к следующему сектору, задевает за очередной выступ, то текущая угловая скорость движения колеса уменьшается на \(k\) градусов в секунду. При этом если \(v \le k\), то колесо не может преодолеть препятствие и останавливается. Стрелка в этом случае будет указывать на сектор \(X\).

Юный участник шоу собирается вращать колесо. Зная порядок секторов на колесе, он хочет заставить колесо вращаться с такой начальной скоростью, чтобы после остановки колеса стрелка указала на как можно большее число. Колесо можно вращать в любом направлении и придавать ему начальную угловую скорость от \(a\) до \(b\) градусов в секунду.

Требуется написать программу, которая по заданному расположению чисел в секторах, минимальной и максимальной начальной угловой скорости вращения колеса и величине замедления колеса при переходе через границу секторов вычисляет максимальный выигрыш.

Входные данные

Первая строка входного файла содержит целое число \(n\) — количество секторов колеса (\(3 \le n \le 100\)).

Вторая строка входного файла содержит \(n\) положительных целых чисел, каждое из которых не превышает \(1000\) — числа, записанные в секторах колеса. Числа приведены в порядке следования секторов по часовой стрелке. Изначально стрелка указывает на первое число.

Третья строка содержит три целых числа: \(a\), \(b\) и \(k\) (\(1 \le a \le b \le 10^9\), \(1 \le k \le 10^9\)).

Выходные данные

В выходном файле должно содержаться одно целое число — максимальный выигрыш.

Примечание

В первом примере возможны следующие варианты: можно придать начальную скорость колесу равную 3 или 4, что приведет к тому, что стрелка преодолеет одну границу между секторами, или придать начальную скорость равную 5, что позволит стрелке преодолеть 2 границы между секторами. В первом варианте, если закрутить колесо в одну сторону, то выигрыш получится равным 2, а если закрутить его в противоположную сторону, то — 5. Во втором варианте, если закрутить колесо в одну сторону, то выигрыш будет равным 3, а если в другую сторону, то — 4.

Во втором примере возможна только одна начальная скорость вращения колеса — 15 градусов в секунду. В этом случае при вращении колеса стрелка преодолеет семь границ между секторами. Тогда если его закрутить в одном направлении, то выигрыш составит 4, а если в противоположном направлении, то — 3.

Наконец, в третьем примере оптимальная начальная скорость вращения колеса равна 2 градусам в секунду. В этом случае стрелка вообще не сможет преодолеть границу между секторами, и выигрыш будет равен 5.

Правильные решения для тестов, в которых \(1 \le a \le b \le 1000\), будут оцениваться из 50 баллов.

Примеры
Входные данные
5
1 2 3 4 5
3 5 2
Выходные данные
5
Входные данные
5
1 2 3 4 5
15 15 2
Выходные данные
4
Входные данные
5
5 4 3 2 1
2 5 2
Выходные данные
5
#3208
Делители
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Натуральное число \(a\) называется делителем натурального числа \(b\), если \(b = ac\) для некоторого натурального числа \(c\). Например, делителями числа 6 являются числа 1, 2, 3 и 6. Два числа называются взаимно простыми, если у них нет общих делителей кроме 1. Например, 16 и 27 взаимно просты, а 18 и 24 — нет.

Будем называть нормальным набор из \(k\) чисел (\(a_1, a_2, \ldots, a_k\)), если выполнены следующие условия:

  1. каждое из чисел \(a_i\) является делителем числа \(n\);
  2. выполняется неравенство \(a_1 \lt a_2 \lt \ldots \lt a_k\);
  3. числа \(a_i\) и \(a_{i+1}\) для всех \(i\) от \(1\) до \(k - 1\) являются взаимно простыми;
  4. произведение \(a_1a_2\ldots a_k\) не превышает \(n\).

Например, набор (2, 9, 10) является нормальным набором из 3 делителей числа 360.

Требуется написать программу, которая по заданным значениям \(n\) и \(k\) определяет количество нормальных наборов из \(k\) делителей числа \(n\).

Входные данные

Первая строка входного файла содержит два целых числа: \(n\) и \(k\) (\(2 \le n \le 10^8\), \(2 \le k \le 10\)).

Выходные данные

В выходном файле должно содержаться одно число — количество нормальных наборов из \(k\) делителей числа \(n\).

Примечание

Правильные решения для тестов, в которых \(n \le 1000\) и \(k = 2\), оцениваются из 30 баллов.

Правильные решения для тестов, в которых \(k = 2\), оцениваются из 60 баллов (в эти баллы включаются также 30 баллов для случая \(n \le 1000\), \(k = 2\)).

Примеры
Входные данные
90 3
Выходные данные
16
Входные данные
10 2
Выходные данные
4
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест