Полуфинал XVII Всероссийской командной олимпиады школьников по программированию (Восточно-Сибирский регион)

Задача A. Яблоки

Маленький Вася всё ещё не научился считать, поэтому ему снова нужна Ваша помощь. На этот раз перед ним стоит задача куда более сложная! Нужно посчитать максимально возможное количество полностью заполненных вагонов, если известно, что в один ящик помещается 10 яблок, а в 1 вагон – 10 ящиков. Именно такие объемы, как считает Вася, используются в реальной жизни, ведь 10 – это очень большое число!

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

Входной файл INPUT.TXT содержит целое число N – общее количество яблок (100 ≤ N < 1000).

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

В выходной файл OUTPUT.TXT выведите искомое количество вагонов.

Пример

Задача B. Пирамида

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

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

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

Входной файл INPUT.TXT содержит нечетное натуральное число N (N < 1000) – основание пирамиды.

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

В выходной файл OUTPUT.TXT выведите пирамиду с основанием N. Вместо кубиков используйте символ 'A' (заглавная латинская буква). В начале строки для форматирования выведите необходимое количество символов '.' (точка).

Пример

Задача C. Маги

Каждый из N выпускников школы чародейства и волшебства получает посох силы a_i и кольцо силы b_i. При этом сила i-го выпускника определяется соотношением a_i / b_i.

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

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

Первая строка входного файла INPUT.TXT содержит натуральное число N (N ≤ 1000) – количество выпускников школы чародейства и волшебства. Вторая строка содержит N чисел a_i (1 ≤ a_i < 2³¹) – силы посохов. Третья строка содержит N чисел b_i (1 ≤ b_i ≤ 2³¹) – силы колец.

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

В первой строке выходного файла OUTPUT.TXT выведите N чисел от 1 до N – распределение посохов между выпускниками. Число k на позиции i обозначает, что i-й выпускник получит k-й посох. Во второй строке выведите N чисел от 1 до N – распределение колец между выпускниками. Число m на позиции i обозначает, что i-й выпускник получит m-е кольцо. Если существует несколько решений, выведите любое из них.

Примеры

Задача D. Зубры

Это задача про зубров и любые совпадения с бизонами считайте случайными. Страна зубров состоит из N городов, которые соединены M двусторонними дорогами (между двумя города есть только одна дорога). Известно, что дороги были построены так, что из любого города по дорогам можно добраться до любого другого города.

Зубры Виталя и Рома постоянно играют в одну и ту же игру: Рома загадывает число L, а Виталя должен проверить можно ли из какого-нибудь города добраться до K других городов, если проходить только по дорогам, длина которых не меньше L.

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

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

Первая строка входного файла INPUT.TXT содержит три целых числа: N (2 ≤ N ≤ 10⁵), M (N-1 ≤ M ≤ min(N*(N-1)/2, 10⁵)) и K (1 ≤ K < N) – общее число городов, число дорог и число городов, до которых нужно добраться.

Следующие M строк содержат по три натуральных числа: a_i, b_i (1 ≤ a_i, b_i ≤ N) и l_i (l_i ≤ 10⁹) – первые два числа задают номера городов, которые соединяет дорога, а третье число – длину дороги.

Гарантируется, что любые два города соединяются не более чем одной дорогой, а так же, что нет дорог, которые соединяют город сам с собой.

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

В выходной файл OUTPUT.TXT выведите единственное целое число – ответ на задачу.

Примеры

Задача E. Коллекция

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

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

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

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

Первая строка входного файла INPUT.TXT содержит одно натуральное число N (N ≥ 2). Во второй строке содержатся N натуральных чисел A_i – список всех делителей искомого числа K.

Гарантируется, что K – составное число, не превышающее 10⁹.

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

В выходной файл OUTPUT.TXT выведите единственное целое число K – восстановленное по своим делителям число.

Примеры

Задача F. За стол!

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

Как это обычно бывает, после занятий все пришедшие садятся за круглый стол, который подготовила хранительница центра. Садится каждый, иначе это покажется неприличным. По краю стола расположены N разнообразных блюд, каждое блюдо имеет свою калорийность Ci. Когда гость садится за стол, ему достаются какие-то расположенные подряд блюда. Гости должны сесть так, чтобы не обидеть друг друга, то есть сумма калорийностей выбранных блюд должна у всех совпадать. И при этом не обидеть хранительницу, съев все блюда на столе.

К сожалению, это не всегда возможно, и если гости не смогут рассадиться по заданным критериям, они могут потерять контроль над собой и забудут про все правила приличия! Известно, что сегодня придёт от 1 до N человек. Хранительница попросила Вас написать программу, которая сообщит: для каких количеств такая рассадка будет возможна, а для каких нет.

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

В первой строке входного файла INPUT.TXT содержится натуральное число N – количество блюд на столе (1 ≤ N ≤ 10⁵).

Во второй строке перечислены калорийности блюд C_i в порядке обхода стола по часовой стрелке.

Калорийность – неотрицательное целое число, сумма всех калорийностей не превосходит 10⁹.

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

В выходной файл OUTPUT.TXT выведите строку из N символов: K-ый символ (1 ≤ K ≤ N) должен быть равен «1», если возможно рассадить K гостей за столом и «0» – иначе.

Примеры

Задача G. Фермер Тетракарп

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

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

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

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

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

На каждой из трех строк входного файла INPUT.TXT через пробел заданы по четыре целых числа x1_i, y1_i, x2_i и y2_i – координаты противоположных вершин прямоугольника, который был засеян в i-ый день.

Все координаты по абсолютной величине не больше 10⁹, а стороны прямоугольников параллельны осям координат.

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

В выходной файл OUTPUT.TXT выведите одно целое число – площадь засеянной области.

Примеры

Задача H. Саша и массив

Маленький Саша любит играть с массивами. Недавно ему как раз подарили прекрасный массив из N натуральных чисел (a₁, a₂, ..., a_n, 1 ≤ a_i ≤ 10⁹). Вчера Саша придумал игру: он выбирает два числа l и r (1 ≤ l ≤ r ≤ N), записывает в тетрадочку их и максимальный элемент a_i, где l ≤ i ≤ r.

За день Саша сделал M записей. Но случилось страшное: утром Саша обнаружил, что массив пропал! Помогите Саше восстановить массив, пользуясь его записями!

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

В первой строке входного файла INPUT.TXT находятся два числа N и M (1 ≤ N, M ≤ 1000), разделенных пробелом, – размер массива и число записей, сделанных Сашей. Следующие M строк описывают запросы. В каждой строке находится три числа, l_j, r_j и q_j (1 ≤ l_j ≤ r_j ≤ N, 1 ≤ q_j ≤ 10⁹), разделенных пробелами, — левая и правая границы отрезка и максимум на нем.

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

Если существует массив, удовлетворяющий всем записям, то в первой строке выходного файла OUTPUT.TXT выведите слово «EASY» без кавычек, а во второй – сам массив, разделенный пробелами. Если таких массивов может быть несколько, выведите любой из них. Если такого массива нет, выведите единственное слово «FAIL» без кавычек.

Примеры

Задача I. Гена атакует

Это интерактивная задача.

Программа-троян по имени Гена заразила ваш компьютер, и теперь хочет поиграть с вами в игру. Гена загадал некоторое целое число X (0 ≤ X < 2¹⁶), и хочет, чтобы вы его угадали, иначе вирус распространится по сети. Вы можете задавать Гене вопросы вида «? Y», где Y — целое число (0 ≤ Y < 2¹⁶). После этого Гена выписывает своё и ваше числа в двоичном представлении, считает количество разрядов, в которых числа различаются и сообщает это количество вам.

Как только вы посчитали, что знаете загаданное число, выведите сообщение «! Y», означающее, что Y — и есть это число. После вывода этого запроса общение с Геной прекращается. Также, не забываете, что Гена ответит не более чем на 20 вопросов.

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

Используется стандартный ввод и вывод. После каждого запроса «?» вашей программе будет сообщено в новой строке количество разрядов (в двоичном представлении), в которых ваше число отличается от загаданного.

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

Ваша программа должна произвести не больше 20-ти запросов типа «?». Обратите внимание, что последний запрос, выводящий ответ, не входит в данные 20 запросов.

Пример

Примечание

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

• В языке Pascal: flush(output);
• В С/С++: fflush(stdout) или cout.flush();
• В Java: System.out.flush();
• В Python: sys.stdout.flush() из библиотеки sys;
• В C#: Console.Out.Flush();

Задача J. Длина числа

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

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

Входной файл INPUT.TXT содержит целое число N (1 ≤ N ≤ 10⁹).

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

В выходной файл OUTPUT.TXT выведите длину числа N.

Пример