Задача A. В ожидании Нового года ≡

Условие

31 декабря. Марфа Геннадьевна и Глафира Сергеевна уже приготовили новогодний ужин, и теперь они с нетерпением ждут Нового года.

Каждые 5-10 минут они смотрят на часы и вычисляют, сколько часов и минут осталось до Нового года. При этом на вычисление у них уходит много времени.

Поэтому им хотелось бы иметь компьютерную программу, принимающую на вход текущее время (часы и минуты) и вычисляющую, сколько времени осталось до Нового года.

Число секунд в текущем времени принять равным 0.

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

Входной файл содержит текущее время — часы и минуты.

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

Требуется вывести в выходной файл, сколько времени осталось до Нового года — часы и минуты.

Ограничения

Часы от 0 до 23. Минуты от 0 до 59.

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

12 0

12 0

23 59

0 1

22 25

1 35

Задача B. Вынутый разворот ≡

Условие

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

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

Во входном файле содержатся два целых числа A и B — номера страниц на стороне листа, в произвольном порядке

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

В выходном файле должно содержаться единственное число:

• 0 — если такой брошюры не существует
• Число страниц в брошюре — в противном случае

Ограничения

1 ≤ A, B ≤ 10⁶

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

3 14

16

9 1

0

Задача C. Яблоки поровну ≡

Условие

В школьной столовой на завтрак раздавали яблоки. Каждому школьнику должно было достаться по одному яблоку, но трём из них удалось незаметно набрать в карманы a₁, a₂ и a₃ яблок соответственно.

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

Например, если у первого школьника 2 яблока, у второго — 3, а у третьего — 4, то третий школьник может передать первому одно яблоко, и тогда у каждого из них будет по 3 яблока.

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

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

Входной файл содержит целые числа a₁ a₂ a₃.

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

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

Если у школьников уже одинаковое количество яблок, выведите единственное число 0.

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

Ограничения

1 ≤ a_i ≤ 1000; 1 ≤ x, y ≤ 3

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

3 3 3

0

1 3 5

3 1 2

1 3 6

-1

Задача D. Точка в углу ≡

Условие

Прямоугольник со сторонами, параллельными осям координат, задан координатами противоположных вершин (x₁, y₁) и (x₂, y₂).

Будем считать, что точка (x, y) внутри прямоугольника находится в углу, если расстояние от точки до одной из вершин прямоугольника строго меньше, чем до центра прямоугольника.

Напишите программу, которая по данному прямоугольнику и точке определяет, находится ли точка в углу.

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

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

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

Выходной файл должен содержать единственную строку CORNER, если точка находится в углу, или CENTER в противном случае.

Ограничения

 − 10⁴ ≤ x₁,y₁,x₂,y₂ ≤ 10⁴

min(x₁, x₂) ≤ x ≤ max(x₁, x₂)

min(y₁, y₂) ≤ y ≤ max(y₁, y₂)

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

100 200 300 400 290 210

CORNER

100 200 300 400 200 300

CENTER

Задача E. Контрольное списывание ≡

Условие

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

Одновременно у одного ученика может списывать только один другой ученик. На списывание уходит 1 минута. Те, кто уже списал, могут дать списать остальным.

Среди неподготовленных учеников K имеют плохой почерк, из-за чего у них никто не может ничего списывать.

Напишите программу, которая определит минимальное время в минутах, за которое все неподготовленные ученики смогут списать контрольную.

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

Входной файл содержит три целых числа N M K.

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

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

Если некоторые неподготовленные ученики никогда не смогут списать, выведите  − 1.

Ограничения

1 ≤ N ≤ 10⁹

0 ≤ M ≤ N

0 ≤ K ≤ N − M

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

2 1 0

1

4 1 3

3

11 1 8

5

Задача F. Подсчёт баллов за задачу ≡

Условие

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

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

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

В первой строке файла содержится единственное число N.

Во второй строке файла содержатся N чисел — на i-ом месте находятся баллы за i-ый тест.

В третьей строке файла содержаться N символов '+' (ASCII 43) или '-' (ASCII 45). Если ответ на i-ый тест верный, то i-ый символ — '+', в противном случае — '-'

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

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

Ограничения

1 ≤ N ≤ 100

1 ≤ a_i ≤ 100

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

5
1 2 3 5 10 
+-++-

9

6
1 1 3 5 10 25
+-+--+

29

Задача G. Синхронизация ≡

Условие

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

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

Известно, что на протяжении своего эксперимента Вася фиксировал те же самые события, которые фиксировал коллайдер.

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

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

Входной файл содержит целое число N. Далее следует N целых чисел a₁, a₂, …, a_N — времена событий, зафиксированных коллайдером. Затем записано целое число M. Далее следует M чисел b₁, b₂, …, b_M — времена событий, зафиксированных Васей.

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

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

Ограничения

2 ≤ M ≤ N ≤ 10⁵;

0 ≤ a₁ ≤ a₂ ≤ …  ≤ a_N ≤ 10⁹;

0 = b₁ ≤ b₂ ≤ …  ≤ b_M ≤ 10⁹;

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

5
10 15 17 19 20
2
0 2 

2

Задача H. CamelCase ≡

Условие

При написании сложных программ важное значение имеет стандартизация стиля кодирования, в частности формата записи имён переменных. Часто используются следующие два стандарта для имён переменных, состоящих из нескольких слов:

1. Слова записываются друг за другом через знак подчёркивания с маленькой буквы (например my_variable).
2. Слова записываются друг за другом подряд, при этом каждое слово начинается с большой буквы (например MyVariable).

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

1. Имя состоит из одного слова

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

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

Ограничения

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

x

X

ATest

a_test

Задача I. Миша и негатив ≡

Условие

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

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

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

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

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

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

Первая строка входного файла содержит целые числа n и m — высоту и ширину исходного изображения (в пикселях).

Последующие n строк содержат описание исходного изображения. Каждая строка состоит из m символов B и W. Символ B соответствует черному пикселю, а символ W — белому.

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

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

В выходной файл необходимо вывести число пикселей негатива, которые неправильно сформированы Мишиной программой.

Ограничения

1 ≤ n, m ≤ 100

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

3 4
WBBW
BBBB
WBBW

BWWW
WWWB
BWWB

2

2 2
BW
BB

WW
BW

2

Задача J. Упрощение XOR ≡

Условие

Дано выражение вида a xor b … xor x. Операндами выражения могут быть только строчные латинские буквы. Операнды могут повторяться. Операнды отделяются от операции ровно одним пробелом.

Единственная использующаяся операция — xor, операция "исключающего или".

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

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

Входной файл содержит единственную строку s — исходное выражение.

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

Выходной файл должен содержать единственную строку — упрощённое выражение. Если решений несколько, выведите любое из них.

Ограничения

Длина строки s не превосходит 10⁶ символов.

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

a xor a xor b xor a xor c xor b

a xor c

a

a

a xor a

0

Задача K. Правдивая летопись ≡

Условие

"...И узрели они войско вражье хазарское. И было хазарам несметное число." — Тут летописец задумался. Он знал, что число воинов было равно N. Однако, это число могло делиться на три, а могло (что еще хуже) содержать цифру три в десятичной записи! Число три счастливое, а это никак не согласуется с образом врага!

Поэтому летописец решил написать вместо числа N другое число M, которое не делится на три и не содержит в десятичной записи цифру три. Разумеется, число M не может быть меньше N (летописец не преуменьшает количество воинов). С другой стороны, число M должно как можно меньше отличаться по величине от N, иначе летописца могут обвинить в некомпетентности. Помогите летописцу найти нужное M.

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

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

Ограничения

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

1

1

3

4

12

14

Задача L. Открытка программиста ≡

Условие

На день святого Валентина Дима решил сделать подарить своей девушке Лене открытку с сердечками. Лена учится в ДВФУ на программиста, поэтому Диме хотелось сделать программистскую открытку.

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

Изображение открытки представляет собой прямоугольную таблицу, состоящую из символов "." (ASCII 46), "/" (ASCII 47), "V" (ASCII 86), "\" (ASCII 92), "^" (ASCII 94). На открытке изображено n сердец. Каждое сердце задаётся координатами центра x y и размером d. Координата x отсчитывается по горизонтали слева направо, а координата y — по вертикали сверху вниз.

Изображение сердца состоит из шести наклонных линий, состоящих из символов "/" и "\". Две линии, образующие нижний контур сердца, имеют длину по d символов, две линии, образующие внешнюю часть верхнего контура, имеют длину по ⌊(d + 1) / 2⌋ символов, а две линии, образующие внутреннюю часть верхнего контура, имеют длину по ⌊(d − 1) / 2⌋ символов.

Центр и нижняя точка сердца обозначены символами "V". Если d чётно, то две верхние точки сердца обозначены символами "^".

Изображение открытки должно иметь минимально возможный размер, охватывающий изображения всех заданных сердец. Все позиции, не занятые изображениями сердец, должны содержать символ ".".

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

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

Входной файла содержит натуральное число n  — количество сердец, за которым следует n троек натуральных чисел x_i y_i d_i.

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

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

Ограничения

1 ≤ n ≤ 10²

1 ≤ x_i, y_i, d_i ≤ 50

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

3
4 4 3
7 7 6
17 11 1

./\./\............
/..^..\..^........
\./.\././.\.......
./...\./...\......
/.\./.V.....\.....
\..V......../.....
.\........./......
..\......./.......
...\...../...../V\
....\.../......\./
.....\./........V.
......V...........

Задача M. Забор по фен-шую ≡

Условие

Марфа Геннадьевна попросила внука построить новый забор вдоль огорода. Внук выполнил просьбу бабушки и построил забор из N досок, в котором доска с номером i имела высоту a_i сантиметров.

Марфа Геннадьевна недавно прочитала книгу, в которой было написано, что гармоничным является забор, состоящий из чередующихся высоких и низких деревянных досок, то есть должно выполняться либо условие a₁ < a₂ > a₃ < a₄ > …, либо условие a₁ > a₂ < a₃ > a₄ < ….

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

Напишите программу, которая по указанным длинам досок a_i определяет новый набор длин b_i, в котором:

1. a_i ≤ b_i,
2. либо b₁ < b₂ > b₃ < b₄ > …, либо b₁ > b₂ < b₃ > b₄ < …
3. сумма b_i минимальна.

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

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

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

Входной файл должен содержать N целых чисел b_i — новые длины досок. Если существует несколько решений, выведите любое из них.

Ограничения

1 ≤ N ≤ 100; 1 ≤ a_i ≤ 100

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

1
20

20

4
11 10 11 15

11 12 11 15

Задача N. Кампус ≡

Условие

Новое здание кампуса Университета Байтбурга имеет n этажей, пронумерованных снизу вверх от 1 до n. Комнаты студентов расположены в нескольких подъездах.

В каждом подъезде на этажах, номер которых кратен числу k, расположено по x комнат, а на остальных этажах расположено по y комнат.

Комнаты внутри каждого подъезда пронумерованы последовательными натуральными числами. Номера комнат на первом этаже имеют наименьшие значения в этом подъезде, затем следуют номера комнат на втором этаже, и так далее. Комнаты в первом подъезде пронумерованы, начиная с 1, в каждом следующем подъезде нумерация комнат начинается с числа, следующего после максимального номера комнаты в предыдущем подъезде.

На рис.1 показаны номера комнат в здании с n = 7 этажами, 3 подъездами, и параметрами k = 3, x = 2, y = 3.

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

Требуется написать программу, которая по заданным числам n, k, x и y, а также по номерам комнат, определяет для каждой комнаты, на каком этаже она находится.

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

Первая строка входного файла содержит натуральные числа n, k, x и y. Соседние числа разделены ровно одним пробелом.

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

Третья строка содержит q целых чисел a₁, a₂, ..., a_q  — номера комнат. Можно считать, что в здании так много подъездов, что все комнаты с заданными номерами существуют.

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

Требуется вывести q чисел, по одному на строке. Для каждого номера комнаты во входном файле требуется вывести номер этажа, на котором она находится.

Ограничения

1 ≤ n ≤ 10⁹, 1 ≤ x, y ≤ 10⁹, 1 ≤ q ≤ 1000, 1 ≤ a_i ≤ 10¹⁸

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

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

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

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

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

7 3 2 3
4
1 19 20 50

1
7
1
5

Задача O. Автоматизированное управление доставкой ≡

Условие

Группа программистов регионального сортировочного центра работает над автоматизацией управления доставкой почты.

Посылки принимаются в клиентских почтовых пунктах. Почтовый пункт принимает посылки, вес каждой из которых составляет целое число килограммов. Минимальный вес посылки равен 1 кг, а максимальный вес — k кг. Принятые посылки помещаются в специальный пакет.

Если после приема очередной посылки суммарный вес посылок в пакете больше или равен x кг, то пакет доставляется в муниципальный почтовый центр, где пакет с посылками перемещается в специальный контейнер.

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

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

Требуется написать программу, которая по заданным значениям k — максимального веса посылки, x — необходимого веса пакета для его отправки в муниципальный почтовый центр, и y — необходимого веса контейнера для его отправки в региональный сортировочный центр, определяет минимальный вес контейнера при его перевозке.

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

Входной файл содержит три целых положительных числа, по одному на строке. Первая строка содержит число k. Вторая строка содержит число x. Третья строка содержит число y.

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

Требуется вывести одно целое число — минимальный возможный вес контейнера при перевозке.

Ограничения

1 ≤ k, x, y ≤ 10⁹

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

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

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

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

Пояснение к примеру

В приведенном примере принимаются посылки весом 1 и 2 кг. При накоплении посылок с суммарным весом хотя бы в 7 кг пакет доставляется из клиентского почтового пункта в муниципальный почтовый центр. При накоплении посылок с суммарным весом хотя бы в 20 кг контейнер перевозится из муниципального почтового центра в региональный сортировочный центр.

Минимальный возможный вес контейнера в данном примере составляет 21 кг и достигается, например, следующим образом: в муниципальный почтовый центр последовательно доставляется 3 пакета по 7 кг каждый. Пакет весом 7 кг может получиться, например, после приема семи посылок по 1 кг.

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

2
7
20

21

Задача Q. Упаковка конфет ≡

Условие

Кондитерская фабрика изготовила партию конфет N различных сортов. В партию входит a_i конфет i-го сорта.

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

Требуется определить максимально возможное значение M. Например, если изготовлено 15, 19 и 55 конфет трёх разных сортов, то их следует упаковывать в обычные коробки по 4 штуки, после чего останутся конфеты для 3 коробок ассорти.

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

• N = 2

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

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

Ограничения

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

2 
4 9

5

3
7 7 7

7

Задача S. Матрешки ≡

Условие

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

За один такт автомат может взять две матрешки и вложить меньшую в большую, причем если в матрешках уже содержаться другие матрешки, то они все вкладываются в самую большую, при этом номера матрешек остаются прежними. Если матрешка уже вложена в другую, то автомат упаковывает ту матрешку в которую она вложена. Программа автомата состоит из чисел N, K и следующих за ними K пар чисел a_i, b_i — номера матрешек, которые автомат упакует за i-тый такт.

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

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

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

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

Ограничения

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

4 3
1 2
2 3
1 3

1 1 1 4

Задача T. Питание программистов ≡

Условие

Оргкомитет сборов по программированию знает, что важно организовать правильное питание участников. Еда должна быть вкусной, а блюда — разнообразными. Поэтому разработку меню доверили повару тёте Вале.

Тётя Валя умеет готовить несколько разных блюд. Она использует для их обозначения маленькие английские буквы. Всего в течение сборов будет n приёмов пищи. Тётя Валя составила черновик меню — строку s, состоящую из n маленьких английских букв. Символ s_i обозначает блюдо, которое она запланировала для i-го приёма пищи.

Черновик меню полностью сбалансирован по всем питательным компонентам, но тётя Валя не особо заботилась о разнообразии.

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

Если существует несколько решений, выведите любое из них.

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

Входной файл содержит строку s, состоящую из маленьких букв английского алфавита — черновик меню.

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

Выходной файл должен содержать единственную строку — окончательный вариант меню.

Ограничения

1 ≤ n ≤ 100000;

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

olmkoo

moloko

Задача U. Длинный текст и много слов (revisited) ≡

Условие

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

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

Ограничения

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

longlongstring
2
short
string

0 1

Задача V. Роковое число 23 ≡

Условие

К юному программисту Васе обратился человек по имени Уолтер Спэрроу и стал утверждать, что любое заданное число n содержит число 23. Уолтер предлагает получить 23 из числа n путем многократного сложения или вычитания его цифр.

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

Входной файл содержит целое число n.

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

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

Ограничения

1 ≤ n ≤ 10⁵

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

53

Yes

63

No

Задача W. Звёздный путь (ROI-2013) ≡

Условие

Экспедиция готовится отправиться в путь на космическом корабле нового поколения. Планируется последовательно посетить N планет звёздной системы — от планеты Земля до планеты Победа. Планеты пронумерованы от 1 до N в порядке их посещения, Земля имеет номер 1, а Победа — номер N.

Для перелёта между планетами корабль может использовать любой тип топлива, существующий в звёздной системе. Перед началом экспедиции корабль находится на планете Земля, и бак корабля пуст. Существующие типы топлива пронумерованы целыми числами, на планете с номером i можно заправиться только топливом типа a_i. При посещении i-й планеты можно заправиться, полностью освободив бак от имеющегося топлива и заполнив его топливом типа a_i.

На каждой планете станция заправки устроена таким образом, что в бак заправляется ровно столько топлива, сколько потребуется для перелёта до следующей планеты с топливом такого же типа. Если далее такой тип топлива не встречается, заправляться на этой планете невозможно. Иначе говоря, после заправки на i-й планете топлива хватит для посещения планет от (i + 1)-й до j-й включительно, где j — минимальный номер планеты, такой что j > i и a_j = a_i. Для продолжения экспедиции дальше j-й планеты корабль необходимо снова заправить на одной из этих планет.

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

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

В первой строке входного файла записано число N — количество планет.

Во второй строке входного файла записано N целых чисел a₁, a₂, …, a_N — типы топлива на планетах.

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

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

Во второй строке выведите K чисел, разделённых пробелами, — номера планет, на которых требуется заправиться. Номера планет требуется выводить в порядке времени заправок.

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

Ограничения

2 ≤ N ≤ 300 000;

1 ≤ a_i ≤ 300 000;

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

7
1 3 2 1 3 2 3

3
1 3 5

7
4 3 2 4 3 2 1

0

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

Условие

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

На одной из таких тренировок пицца разделена на 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

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

Условие

Учитель математики придумал игру для развития навыков устного счёта. Учитель записывает на доске таблицу 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

Задача Z. Отрезок деревьев ≡

Условие

Данная задача является интерактивной.

После просмотра нескольких документальных фильмов о природе, лесник Шон очень беспокоится о местонахождении деревьев в своём лесу. Дело в том, что в одном из таких фильмов деревья просто так взяли и ушли. Конечно это было необходимо из-за событий, которые происходили в фильме. Но Шон абсолютно уверен, что в реальности такие события не могут случиться по ряду обстоятельств. Поэтому он считает, что у деревьев в его лесу нет никакой уважительной причины, чтобы отлучаться. То есть деревьям нельзя просто так взять и уйти.

В текущий момент у Шона нет никакой информации о том, где растёт каждое из деревьев. Поэтому он не может с полной уверенностью сказать, что деревья в его лесу неподвижны.

Всего в лесу растёт N деревьев. Лес является непрерывным отрезком на прямой от 1 до L. Все деревья растут в разных целочисленных точках.

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

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

Протокол взаимодействия

Сначала на вход программе-решению подаётся целое число L — длина леса.

Для каждого теста жюри зафиксировало числа N и K — количество деревьев и максимальное количество запросов на сканирование участка леса. Гарантируется, что K запросов достаточно, чтобы решить задачу. Эти числа не сообщаются программе-решению. Ограничения на N и K в различных подзадачах приведены в таблице системы оценивания. Если решение делает более K запросов к программе жюри, то на этом тесте оно получает в качестве результата тестирования "Wrong answer".

Чтобы сделать запрос программа-решение должна вывести строку вида "? l r", где l и r (1 ≤ l ≤ r ≤ L) — целые числа, крайние левая и правая точка сканируемого участка леса. В ответ на запрос программа жюри подаёт на вход программе-решению либо строку "Yes", либо строку "No", в зависимости от того, есть ли хотя бы одно дерево в запрашиваемом участке.

Если программа-решение определила ответ на задачу, она должна вывести две строки: в первой "ok?", во второй N целых чисел — список точек, в которых растут деревья в порядке возрастания координат. После этого программа-решение должна завершиться.

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

После каждого запроса и вывода ответа необходимо выполнить сброс буфера. Например, в Pascal необходимо написать flush(output), в C++ — cout.flush().

Ограничения

1 ≤ N ≤ 10³

1 ≤ L ≤ 10⁹

1 ≤ x_i ≤ L

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

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

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

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

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

5

Yes

No

Yes

No


ok

? 1 5

? 1 2

? 3 3

? 4 5

ok?
3

6

Yes

No

Yes

No

Yes

Yes

Yes


ok

? 1 2

? 1 1

? 2 2

? 3 4

? 5 6

? 5 5

? 6 6

ok?
2 5 6