Sublime Text Мальчик Дима написал решение для задачи с отбора на Высшую Пробу. Его код представляет собой n строк, где строка i содержит si позиций для курсора. Обозначим j-ю позицию в i-й строке как (i, j).
Решение все никак не заходит, поэтому Дима решил воспользоваться своей новой техникой дебага кода.
В его редакторе есть две кнопки, которые работают по естественным правилам:
Up: если курсор находится в положении (i, j), то при i = 1 курсор остается на месте, иначе сдвигается в положение (i - 1, min(j, si - 1)).
Right: если курсор находится в положении (i, j), то при j < si курсор передвигается в (i, j + 1), иначе в (i + 1, 1), кроме случая (n, sn) - тогда он остается на месте.
Для дебага Дима выбирает себе некоторое положение курсора и последовательно повторяет следующую операцию, состоящую из комбинации нажатий: u раз Up, затем r раз Right.
Например при n = 5, u = 2, r = 5, s = {5, 2, 4, 3, 1}, стартовом положении (4, 3), будет следующая последовательность позиций:
(4, 3) Up (3, 3) Up (2, 2) Right (3, 1) Right (3, 2) Right (3, 3) Right (3, 4) Right (4, 1)
Положение называется успешным, если в какой-то момент (возможно внутри операции), курсор окажется в первой строке.
Диме посчитать, сколько успешных положений в его коде.
Формат входных данных
Первая строка теста содержит одно целое число t (t ≤ 10) - количество наборов тестовых данных. Затем следуют t наборов тестовых данных.
Первая строка набора тестовых данных содержит три целых числа n, u, r (1 ≤ n ≤ 105, 1 ≤ u, r ≤ 1018).
Вторая строка набора тестовых данных содержит n целых чисел s1, s2, ..., sn (1 ≤ si ≤ 1012).
Формат результата
Для каждого набора тестовых данных выведите одно целое число - ответ на него
Примеры
Входные данные
2
5 2 5
5 2 4 3 1
5 2 10
5 2 4 3 1
Результат работы
15
11
Входные данные
1
10 1 42
169 42 42 42 42 42 42 42 42 42
Результат работы
211
Примечания
Система оценки:
sums = s1 + s2 + ... + sn
Группа Дополнительные ограничения Комментарий
n sums u, r
0 0 - - - Тесты из условия
1 8 n ≤ 100 sums ≤ 100 u, r ≤ 100 -
2 10 - sums ≤ 105 - -
3 2 - - u = 1, r = 1 -
4 10 - - - -
Если ваше решение работает корректно на всех тестах некоторой подгруппы, то оно наберет за нее не меньше указанного количества . Тесты по подгруппам не пересекаются. Подгруппы складываются
Путь из (5, 1) в первом тестовом случае первого теста:
Шаг 1: (5, 1) Up (4, 1) Up (3, 1) Right (3, 2) Right (3, 3) Right (3, 4) Right (4, 1) Right (4, 2)
Шаг 2: (4, 2) Up (3, 2) Up (2, 2) Right (3, 1) Right (3, 2) Right (3, 3) Right (3, 4) Right (4, 1)
Шаг 3: (4, 1) Up (3, 1) Up (2, 1) Right (2, 2) Right (3, 1) Right (3, 2) Right (3, 3) Right (3, 4)
Шаг 4: (3, 4) Up (2, 2) Up (1, 2) Right ...
Объяснение:
h,w = int(input().split())
c,p = int(input().split())
s = []
roadm = []
parks = []
cp = []
for i in range(1, h+1):
for j in range(1, w+1):
s.append([i,j])
for k in s:
if k[0]==1 or k[1]==1:
roadm.append(s.pop(k))
for t in s:
if t[0] == 2 or t[1] == 2:
cp.append(s.pop(t))
for y in s:
if y[0] == (f[0]+1 for f in cp) and y[1] == (f[1]+1 for f in cp) and y[0] == (f[0]-1 for f in cp) and y[1] == (f[1]-1 for f in cp):
parks.append(s.pop(y))
a = []
b = []
for o in s:
a.append(o[0])
b.append(o[1])
print(min(a))
print(min(b))