Задача A. Пицца ≡

Условие

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

На одной из таких тренировок пицца разделена на N различных по размеру кусочков. Но разделена не полностью — все кусочки всё ещё соединены расплавленным сыром. В связи с этим, чтобы взять какой-то кусочек, нужно отрезать его от соседей. Так как пицца имеет форму круга, у каждого из кусочков есть ровно два соседа.

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

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

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

Формат входного файла

Входной файл содержит целое число N — количество кусочков, на которые разделена пицца.

Далее следует N различных целых чисел a_i — размеры кусочков пиццы, перечисленные в порядке обхода по кругу.

Формат выходного файла

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

Ограничения

1 ≤ N ≤ 10⁵

1 ≤ a_i ≤ 10⁹

Описание подзадач и системы оценивания

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

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

Примеры тестов

3
1 2 3

1

5
8 5 6 10 3

5

1
1000000000

1000000000

Задача B. Сумма равна произведению ≡

Условие

Учитель математики придумал игру для развития навыков устного счёта. Учитель записывает на доске таблицу A из N × N натуральных чисел. Затем он вызывает к доске двух учеников, и указывает одно из чисел в таблице (A_ij). Первый ученик должен выбрать другое число в той же строке, что и указанное учителем (A_iq, q ≠ j), и сложить с указанным числом. Второй ученик должен выбрать другое число в той же столбце, что и указанное учителем (A_pj, p ≠ i), и перемножить с указанным числом.

Если результаты вычислений у двух учеников совпали (A_ij + A_iq = A_ij × A_pj), то ученики получают пятёрки. Чтобы игра была честной, учитель указывает только на такие элементы, для которых существует хотя бы одна подходящая пара чисел. Учитель хочет вызвать как можно больше учеников, указывая каждым на ранее не использованный элемент в таблице.

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

По втором примере учитель может выбрать число. 2 (2 + 8 = 2 × 5), 4 (4 + 8 = 4 × 3) либо 3 (3 + 9 = 3 × 4). Если вместо 13 поставить число 5, ответ не изменится, хотя для числа 2 появится второй способ выбора подходящей пары чисел.

Формат входного файла

Входной файл содержит целое число N — размер таблицы, за которым далее следует N строк по N чисел A_ij.

Формат выходного файла

Выходной файл должен содержать единственное целое число — количество элементов A_ij, для которых существуют p ≠ i, q ≠ j, такие что A_ij + A_iq = A_ij × A_pj.

Ограничения

1 ≤ N ≤ 500,

1 ≤ A_ij ≤ 10⁹

Описание подзадач и системы оценивания

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

Примеры тестов

2
2 2
2 2

4

4
2  8  12 4
5  6  7  1
9  10 11 3
13 14 15 16 

3

2
1000 1000
1000 1000

0

Задача C. Обработка картинок ≡

Условие

У юного программиста Васи есть младший брат Петя.

Однажды Петя пришел домой и похвастался Васе, что научился быстро находить геометрические фигуры на картинках и поспорил, что теперь находит их гораздо лучше Васи.

Тогда Вася решил найти сложную картинку и посоревноваться со своим младшим братом в нахождении геометрических фигур.

Картинка представляет из себя набор из N строк по M символов в каждом. Каждый символ может принимать значения с кодами от 33 до 126 в кодировке ASCII.

Петя и Вася решили искать на картинке ромбы специального вида. Контур таких ромбов можно задать уравнением |x − a| + |y − b| = r, где a  — номер столбца центра фигуры, b — номер строки центра фигуры, а r  — ее радиус. Фигура засчитывается только в том случае, если все клетки ее контура содержат один и тот же символ, а также не вылезают за границы картинки. Также не учитываются фигуры, радиус r которых равен 0.

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

Отправка решения и тестирование

В качестве решения принимается как программа, так и текстовый файл, содержащий ответ к задаче в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").

Баллы будут начисляться пропорционально количеству правильных ответов в выходном файле. Если правильный ответ на какой-то из тестов получить не удалось, выведите вместо него число −1.

Формат входного файла

Первая строка входного файла содержит целое число T — количество тестов. Следующие строки содержат описания тестов.

Первая строка каждого теста содержит два целых числа N, M — размеры картинки.

Следующие N строк содержат M символов — описание картинки.

Формат выходного файла

Выходной файл должен содержать T ответов на тесты. Каждый ответ состоит из одной или двух строк.

Первая строка содержит целое число K — количество ромбов на картинке. Вторая строка содержит K четверок a, b, r, c, разделенных пробелами, где целые числа a и b — строка и столбец центра ромба, целое число r — радиус ромба и c — символ, которым заполнен его контур. Четверки, описывающие каждый ромб, можно выводить в любом порядке.

В случае, если ответ на тест найти не удалось, выведите для этого теста одну строку с −1.

Примеры тестов

2
7 7
1111111
1~~A~~1
1.A.A.1
1A...A1
1~A~A~1
1~~A~~1
1111111
7 7
1111111
1~~A~~1
1.A.A.1
1A...A1
1BA~AB1
B~BAB~B
1B111B1

1
4 4 2 A
3
4 4 2 A 6 2 1 B 6 6 1 B

Задача D. Уровни доступа ≡

Условие

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

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

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

Рекомендуется рассмотреть частичные решения.

• N, K_i, M ≤ 100
• M ≤ 2000

Формат входного файла

В первая строка входного файла содержит целые числа N и M. Каждая из следующих N строк описывает права доступа одного сотрудника и содержит целое число K_i —количество доступных сотруднику кабинетов, за которым следует K_i различных целых чисел — номера кабинетов.

Каждый сотрудник имеет доступ к хотя бы одному кабинету, однако некоторые кабинеты могут остаться неиспользованными.

Формат выходного файла

Первая строка выходного файла должна содержать целое число L — количество разных уровней доступа. Следующие L строк должны содержать описания уровней. Каждая из этих строк соответствует очередному уровню доступа и должна содержать целое число D_i ≥ 1, за которым следует строго возрастающая последовательность из D_i целых чисел — номера кабинетов, доступных на этом и последующих уровнях, но недоступных на предыдущих уровнях.

Если решения не существует, выведите единственное число −1.

Ограничения

1 ≤ N, K_i ≤ 2000, 1 ≤ M ≤ 10⁹

Примеры тестов

3 3
2 0 1
3 0 2 1
3 2 1 0

2
2 0 1
1 2

3 3
1 0
1 1
1 2

-1

Задача E. Подходящий интервал ≡

Условие

Во время тура данная задача будет проверяться только на тестах из условия. Окончательное тестирование будет проведено после тура.

Дан массив из N целых чисел a_i.

Требуется найти два числа, a_p и a_q, удаленных друг от друга не менее, чем на L и не более чем на R (т.е. p < q, L ≤ q − p ≤ R), таких что минимальное из этих двух чисел будет максимально возможным.

Рекомендуется рассмотреть частичные решения

• N ≤ 1000
• L = 1
• R = N − 1

Формат входного файла

Входной файл содержит целые числа N L R, за которыми следуют N целых чисел: a₁ a₂ … a_N.

Формат выходного файла

Выходной файл должен содержать два целых числа p q — позиции искомых чисел в массиве. Нумерация позиций начинается с 1.

Если решений несколько, выберите решение с наименьшим значением p, а если и таких несколько — с минимальным значением q.

Ограничения

2 ≤ N ≤ 100000

1 ≤ L ≤ R < N; 1 ≤ p < q ≤ N

1 ≤ a_i ≤ 10⁹

Примеры тестов

3 1 2
2 1 2

1 3