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

Задача A. Горсть монет

Вчера честный майнер Вася добыл «горсть» криптомонет – новой криптовалюты GoldCoin. Особенности технологии таковы, что каждая монета «весит» W байт. К сожалению, ночью на Васю напали хакеры, и утром он обнаружил, что его кошелек стал «легче» в K раз. Хакеры украли целых N монет!

Помогите Васе вспомнить, сколько монет он добыл.

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

Входной файл INPUT.TXT содержит целые числа N, W и K (1 ≤ N, W, K ≤ 10⁹), где N – количество монет, которые украли хакеры, W – «вес» одной монеты в байтах, K – во сколько раз полегчал Васин криптокошелек.

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

В выходной файл OUTPUT.TXT выведите единственное число X – количество монет, которые добыл Вася. Гарантируется, что X – целое число.

Пример

Задача B. Количество байт

В некоторой стране автомобильный номер длиной N символов составляют из заглавных букв (используются только K различных букв) и десятичных цифр в любом порядке. Каждый такой номер в компьютерной программе записывается минимально возможным и одинаковым целым количеством байтов (при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством битов). Определите объём памяти, отводимый этой программой для записи M номеров.

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

Входной файл INPUT.TXT содержит целые числа N, K и M (1 ≤ N, K, M ≤ 20 000).

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

В выходной файл OUTPUT.TXT выведите объём памяти в байтах, отводимый программой для записи M номеров.

Примеры

Задача C. Вложенные рамки

Недавно Денис пересматривал фильм «Начало» и решил нарисовать картину, на которой нарисована картина с картиной (а нам нужно глубже!). И конечно, у каждой картины должна быть рамка.

Помогите Денису нарисовать K рамок, вложенных друг в друга на полотне размером N×N, где N = 4×K - 1.

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

Входной файл INPUT.TXT содержит целое число N – размер полотна. Гарантируется, что существует такое целое число K, что N = 4×K - 1 (1 ≤ K ≤ 125).

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

В выходной файл OUTPUT.TXT выведите квадрат N×N, состоящий из символов «#» и «.», такой что символы «#» образуют K вложенных друг в друга рамок (см. пример).

Пример

Задача D. Муравей

На полу находится источник света, который освещает всё вокруг. Так же на полу находится муравей и ветка. Действие происходит на плоскости. Источник света и муравей считаются точками, ветка – отрезок нулевой толщины.

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

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

Первая строка входного файла INPUT.TXT содержит координаты источника света (x₀,y₀). Вторая и третья строки содержат координаты (x_a,y_a) и (x_b,y_b) – концы отрезка, образующего ветку. В четвёртой строке находятся координаты муравья (x_m,y_m). Все числа целые и не превосходят 10⁹ по абсолютному значению.

Гарантируется, что муравей не находится на ветке а также то, что источник света и ветка не лежат на одной прямой.

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

В выходной файл OUTPUT.TXT выведите «YES», если муравей в тени и «NO» в противном случае.

Примеры

№	INPUT.TXT	OUTPUT.TXT	Пояснение
1	0 0 0 1 1 0 1 1	YES
2	0 0 0 1 1 0 -1 -1	NO
3	0 0 0 1 1 0 2 0	YES

Задача E. День рождения

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

Вы должны считать, что коробка пройдет, если у неё существует грань, высота которой будет не больше высоты проёма, а ширина – не больше ширины проёма.

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

Первая строка входного файла INPUT.TXT содержит три целых числа H_b, W_b, L_b (1 ≤ H_b, W_b, L_b ≤ 10⁹) – высота, ширина и длина коробки соответственно. На второй строке заданы два целых числа H_d, W_d (1 ≤ H_d, W_d ≤ 10⁹) – высота и ширина дверного проёма соответственно.

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

В выходной файл OUTPUT.TXT выведите «YES» (без кавычек), если коробка пройдет в дверь, в противном случае выведите «NO» (без кавычек).

Примеры

Задача F. Огонь и лёд

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

На поле есть ровно одна стартовая клетка и ровно одна целевая (конечная) клетка. Остальные клетки имеют один из трёх типов:

F – клетка охвачена пламенем;

I – клетка покрыта холодом;

X – стена, непроходимая клетка.

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

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

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

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

Первая строка входного файла INPUT.TXT содержит целые числа N, M и H – размеры поля и максимальное здоровье героя соответственно (1 ≤ N, M, H ≤ 100).

Следующие N строк содержат по M символов в каждой – описание карты. Символ F обозначает клетку с огнём, I – клетку со льдом, X – стену, A и B – стартовая и конечная клетки соответственно.

Следующие N строк содержат по M целых чисел – силы соответствующих клеток. Гарантируется, что силы стартовой и конечной клеток равны нулю. Остальные силы являются целыми числами от 1 до 100.

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

В первой строке выходного файла OUTPUT.TXT выведите ответ для стихии огня, во второй – для стихии льда. В тех случаях, когда герой не может добраться до конечной клетки, следует вывести «impossible» (без кавычек).

Примеры

Задача G. Скучные запросы

Эта задача настолько скучна, что никакая легенда её не украсит.

Вам дан массив из n целых чисел a_i. От вас требуется ответить на m запросов, которые задаются числами l, r и x: найти количество таких i, что l ≤ i ≤ r и a_i взаимно просто с x.

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

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

Первая строка входного файла INPUT.TXT содержит целое число n – количество чисел (1 ≤ n ≤ 200 000). Во второй строке записаны n целых чисел a_i, разделённые пробелами (1 ≤ a_i ≤ 10⁶). В третьей строке содержится целое число m – количество запросов (1 ≤ m ≤ 200 000). Следующие m строк содержат тройки чисел l_i, r_i и x_i (1 ≤ l_i ≤ r_i ≤ n; 1 ≤ x_i ≤  10⁶).

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

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

Пример

Задача H. Мотивация

В одном спортивном кружке числятся N спортсменов. Все обладают разными умениями и знаниями, кто-то способен, а кто-то нет, но тренер считает, что из-за разной мотивации не понятно кто чего стоит. Мотивацию i-го человека он оценил натуральным числом A_i.

Тренер может провести речь, после которой все ученики с мотивацией, равной K, получат  +1 к мотивации. Так как тренер опытный профессионал в своём деле, он может и наоборот, провести речь, после которой все ученики с мотивацией, равной K, получат -1 к мотивации. Число K тренер выбирает каждый раз перед началом речи.

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

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

Первая строка входного файла INPUT.TXT содержит целое число N – количество человек в кружке (1 ≤ N ≤ 10⁵). Вторая строка содержит N целых чисел A_i, разделённых пробелами (1 ≤ A_i ≤ 10⁹). В третьей строке содержится число M (1 ≤ M ≤ 10⁹).

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

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

Пример

Задача I. Сыграешь с Денисом?

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

Денису скучно и он хочет сыграть с вами в одну игру. Он загадал некоторое натуральное число N (1 ≤ N ≤ 10⁹), и хочет, чтобы вы его угадали. Вы можете задавать Денису вопросы вида «? X», где X – натуральное число (1 ≤ X ≤ 10⁹). После этого Денис сообщает вам остаток от деления числа X на N.

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

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

После каждого запроса вида «? X» вашей программе в новой строке будет сообщен остаток от деления вашего числа на загаданное число.

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

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

Пример

Примечание

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

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

Задача J. Космический мусор

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

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

Каждый объект зафиксирован и внесён в реестр в виде координат (x, y, z). Считается, что станция находится в начале координат (0, 0, 0). Размером объектов и станции нужно пренебречь, лазерный луч выходит из начала координат.

Подготовка луча – дело долговременное, поэтому вам нужно вычислить минимальное количество выстрелов, необходимое для уничтожения всех объектов.

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

Первая строка входного файла INPUT.TXT содержит целое число N – количество объектов в космосе (1 ≤ N ≤ 200 000). В каждой из следующих N строк содержатся координаты объектов в виде чисел x, y, z (|x|, |y|, |z| ≤ 10⁹). Координаты объектов могут совпадать. Гарантируется, что не существует объектов в начале координат.

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

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

Примеры