Открытое личное первенство ИКИТ СФУ по программированию 2018. Студенты
A. Обед
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мебибайт
ввод
стандартный ввод или input.txt
вывод
стандартный вывод или output.txt

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

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

В одной строке записаны три целых числа: N — количество участников, X — стоимость одного банана и Y — стоимость одной бутылочки с минералкой (1 ≤ N, X, Y ≤ 1000).

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

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

Пример
Входные данные
100 20 35
Выходные данные
5500

B. Страшный сон Егора
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мебибайт
ввод
стандартный ввод или input.txt
вывод
стандартный вывод или output.txt

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

Накануне перед олимпиадой ему приснился страшный сон: Егор не набрал необходимые T проходных баллов по итогу олимпиады, а значит на заключительный этап он поедет только по квоте! Об отношении к квотникам на заключительном этапе Егор знает не понаслышке, поэтому он просит вас о помощи.

Помимо проходного балла T — минимального количества баллов, которое нужно набрать, ему приснилось, что на олимпиаде будет N задач, по каждой можно набрать целый балл от 0 до 100, при этом в i-й задаче можно будет набрать только балл, кратный ki.

Егору не приснились сами задачи, но приснились затраты энергии si — сколько требуется энергии на прочтение задачи, и ci — сколько потребуется энергии чтобы набрать по задаче один балл. Естественно, нельзя набирать баллы по задаче, не прочитав её.

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

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

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

В первой строке содержатся два целых числа N и T (1 ≤ N ≤ 100; 1 ≤ T ≤ 100 × N).

В следующих N строках содержится по три числа si, ci и ki для каждой задачи (1 ≤ si, ci ≤ 105; 1 ≤ ki ≤ 100; ki — делитель числа 100).

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

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

Во второй строке выведите N чисел bi через пробел — баллы, которые нужно набирать по каждой задаче. Каждое bi должно делиться на ki, а также должно выполняться неравенство 0 ≤ bi ≤ 100.

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

Пример
Входные данные
3 166
10 5 1
1 1 10
15 4 25
Выходные данные
406
16 100 50

C. Виталя и кубик
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мебибайт
ввод
стандартный ввод или input.txt
вывод
стандартный вывод или output.txt

У Витали есть белый кубик с одной красной гранью. Кубик стоит в левом верхнем углу шахматной доски красной гранью вверх.

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

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

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

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

В единственной строке содержатся два целых числа N и M (1 ≤ N, M ≤ 100)  — количество строк и столбцов шахматной доски.

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

Если решения не существует, то в единственной строке выведите «no solution» (без кавычек), в противном случае выведите искомую последовательность ходов, по одному ходу в каждой строке. Для перекатывания кубика влево, вправо, вверх и вниз используйте команды LEFT, RIGHT, UP и DOWN соответственно.

Примеры
Входные данные
2 2
Выходные данные
DOWN
RIGHT
UP
Входные данные
2 3
Выходные данные
DOWN
RIGHT
RIGHT
UP
LEFT
RIGHT

D. Удаление чисел
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мебибайт
ввод
стандартный ввод или input.txt
вывод
стандартный вывод или output.txt

Василий в этом году заканчивает 9 класс и мечтает поступить в Физико-математическую школу СФУ (ФМШ). Для подготовки к вступительному экзамену он прорешивает задания прошлых лет. Одно задание показалась Василию особенно сложным, но очень интересным. Василий всё-таки смог решить это задание. А вы сможете?

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

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

Два целых числа: N — количество чисел и A — число, которое должно остаться после всех операций (1 ≤ A ≤ N ≤ 1018).

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

Выведите последовательность операций в одной строке. Для удаления всех чисел на чётных позициях выведите 0, для удаления чисел на нечётных позициях выведите 1.

Пример
Входные данные
10 5
Выходные данные
0 0 1 

E. Шоколадка
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мебибайт
ввод
стандартный ввод или input.txt
вывод
стандартный вывод или output.txt

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

Вот и вы проспорили своему другу Тессекарпу очередную шоколадку. А так как ваш друг четырёхмерный, он признаёт только трёхмерные плитки шоколада. Вы смогли найти такую шоколадку, а именно, подарили ему шоколадный параллелепипед размера A на B на C долек. Введём координатную сетку на этой шоколадке: оси Ox, Oy и Oz направлены соответственно вдоль измерений A, B и C, а каждая долька имеет размер 1 × 1 × 1. Сам параллелепипед имеет углы (0, 0, 0) и (A, B, C).

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

После каждого удара от вас требуется вычислить объём наибольшего из новых восьми кусков и вывести остаток от деления полученного значения на 109 + 7.

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

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

Первая строка содержит три целых числа A, B и C — размеры шоколадки (2 ≤ A, B, C ≤ 109).

Во второй строке содержится целое число N — количество ударов (1 ≤ N ≤ 150 000).

В следующих N строках содержится по три целых числа xi, yi и zi (1 ≤ xi ≤ A - 1, 1 ≤ yi ≤ B - 1, 1 ≤ zi ≤ C - 1). i-е из этих чисел задаёт координаты i-й точки удара. Гарантируется, что в момент нанесения удара точка находится строго внутри одного из существующих кусков шоколадки (не обязательно наибольшего!).

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

Выведите N строк, в каждой из которых содержится остаток от деления объёма наибольшего нового куска, образовавшегося после очередного разлома, на 109 + 7.

Примеры
Входные данные
10 10 10
5
4 4 7
2 2 2
6 3 3
7 8 9
8 2 5
Выходные данные
252
20
48
24
8
Входные данные
1000000000 999999999 999999998
1
1 1 1
Выходные данные
999999287

F. Условие Фано
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мебибайт
ввод
стандартный ввод или input.txt
вывод
стандартный вывод или output.txt

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

Вам нужно ответить на следующий вопрос: какое минимальное количество кодовых слов (любой длины) нужно добавить в это множество, чтобы:

  • Сохранилось выполнение условия Фано.
  • Если добавить любое кодовое слово в полученное множество, то нарушится условие Фано.
Входные данные

В первой строке содержится целое положительное число N  — количество известных кодовых слов.

Далее в N строках содержатся кодовые слова, по одному на строке.

Гарантируется, что суммарная длина кодовых слов не превышает 106, и что все кодовые слова имеют ненулевую длину.

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

В единственной строке выведите одно целое число  — ответ на задачу.

Примеры
Входные данные
2
010
001
Выходные данные
3
Входные данные
3
1
01
00
Выходные данные
0

G. Едем в соседнее село
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мебибайт
ввод
стандартный ввод или input.txt
вывод
стандартный вывод или output.txt

Поликарп и его компания решили съездить в соседнее село на дискотеку.

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

Поликарп и компания выезжают из села s и направляются в село t по кратчайшему пути. Так как они едут со своей фонотекой, они включили музыку во время поездки. Музыка из машины Поликарпа распространяется до всех сёл, расстояние до которых не более D. Расстоянием между сёлами является минимальное количество дорог на пути из одного села в другое.

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

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

Первая строка содержит целое число n — количество сёл (1 ≤ n ≤ 2 × 105).

В следующих n - 1 строках идёт описание дорог в виде двух чисел ai и bi, означающих, что сёла с номерами ai и bi соединены дорогой (1 ≤ ai, bi ≤ n).

Следующая строка содержит два целых числа m и D (1 ≤ m ≤ 5 × 105; 0 ≤ D ≤ 2 × 105).

В следующих m строках идут пары чисел sk и tk (1 ≤ sk, tk ≤ n).

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

Для каждой пары sk и tk выведите в отдельной строке искомое количество сёл.

Пример
Входные данные
14
1 2
1 3
2 6
2 7
3 4
3 5
6 8
8 9
8 10
7 11
7 12
7 13
12 14
5 2
2 13
12 6
10 5
7 7
9 10
Выходные данные
10
12
13
8
5

H. Великая Таблица Умножения
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мебибайт
ввод
стандартный ввод или input.txt
вывод
стандартный вывод или output.txt

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

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

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

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

В первой строке входных данных содержатся два целых числа N и M — размеры таблицы (1 ≤ N, M ≤ 500).

В следующих N строках содержится по M чисел ai, j, записанных через пробел — элементы таблицы (1 ≤ ai, j ≤ 1018).

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

Выведите «true», если Поликарпу достался кусок настоящего сокровища, и «false» иначе.

Примеры
Входные данные
2 2
1 2
2 4
Выходные данные
true
Входные данные
3 3
3 4 5
4 5 6
5 6 7
Выходные данные
false

I. Бизоново сложение
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мебибайт
ввод
стандартный ввод или input.txt
вывод
стандартный вывод или output.txt

А вы знаете, как задаются двоичные числа в бизоновом формате?

Двоичное число в бизоновом формате задается последовательностью целых положительных чисел: a1, a2, ..., an. Данная запись обозначает, что в двоичном числе слева направо сначала записаны a1 цифр 1, затем a2 цифр 0, затем a3 цифр 1, затем a4 цифр 0, затем a5 цифр 1 и т. д.

Вот несколько примеров перевода двоичных чисел из бизонового формата в обычный:

  • 2, 3, 1, 4 переводится в 1100010000.
  • 4, 1, 2, 1, 1 переводится в 111101101.
  • 1 переводится в 1.
  • 2, 3 переводится в 11000.

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

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

Первая строка содержит 4 целых положительных числа, не превосходящих 1018  — первое число в бизоновом формате. Вторая строка содержит 4 целых положительных числа, не превосходящих 1018  — второе число в бизоновом формате.

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

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

Примеры
Входные данные
1 2 3 4
4 3 2 1
Выходные данные
2 3 2 1 2 1 
Входные данные
10 1 2 3
3 2 3 1
Выходные данные
1 7 2 1 1 2 2 1 

J. Юбилей
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мебибайт
ввод
стандартный ввод или input.txt
вывод
стандартный вывод или output.txt

Ромка недавно вернулся с юбилея своего друга Сашки. Праздник отмечался с размахом и Ромка подумал: а что, если бы юбилеи были чаще? Можно же не ограничиваться десятичной системой счисления.

Ромка ввёл понятие юбилейности числа, равное максимальному количеству нулей в конце записи этого числа в какой-то системе счисления с основанием B, где B — целое число, большее единицы.

Например, юбилейность числа 256 равна 8, так как в двоичной системе счисления оно оканчивается на 8 нулей.

Ромка хочет узнать, когда его ближайший следующий значимый юбилей, если сейчас ему X лет? Значимым юбилеем он считает количество лет, которое обладает юбилейностью как минимум L.

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

Единственная строка ввода содержит два целых числа X и L (1 ≤ X ≤ 1012; 1 ≤ L ≤ 50).

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

Выведите единственное число — ответ на задачу.

Примеры
Входные данные
9990 4
Выходные данные
10000
Входные данные
100 8
Выходные данные
256
Входные данные
100 2
Выходные данные
104

K. Чародейские стрелы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мебибайт
ввод
стандартный ввод или input.txt
вывод
стандартный вывод или output.txt

Ваня играет в коллекционную карточную игру.

Сейчас у его соперника на столе находится N существ, каждое из которых имеет определенный количественный показатель здоровья. Кроме того, в игре участвует N + 1-й персонаж — герой противника.

У Вани в руке есть одна карта, которой он собирается сходить. Это заклинание "Чародейские стрелы", которое выпускает три чародейских стрелы в случайных персонажей противника. Каждая стрела выбирает целью случайный персонаж противника и после попадания в него отнимает у него 1 единицу здоровья. Если после этого у него остается 0 единиц здоровья, то персонаж мгновенно умирает, и следующие стрелы в него попасть уже не могут.

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

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

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

Первая строка содержит единственное число N - количество существ противника (1 ≤ N ≤ 2). Вторая строка содержит N целых чисел hpi - значения здоровья для каждого из существ противника (1 ≤ hpi ≤ 100).

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

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

Примеры
Входные данные
1
3
Выходные данные
0.1250000000
Входные данные
2
1 2
Выходные данные
0.7222222222 0.3240740741
Примечание

В первом примере каждая стрела может попасть либо в единственное существо, либо в героя противника. Чтобы существо погибло, все три стрелы должны попасть именно в него, вероятность этого

L. Постеры
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
1024 мебибайта
ввод
стандартный ввод
вывод
стандартный вывод

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

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

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

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

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

В первой строке программа жюри передаёт программе участника четыре целых числа r, c, n, q (1 ≤ r, c ≤ 109, 0 ≤ n, q ≤ 50 000) — соответственно высоту и ширину стены, количество постеров и количество запросов.

В каждой из последующих n строк передаются по четыре целых числа x1, y1, x2, y2 (0 ≤ x1, x2 ≤ r, 0 ≤ y1, y2 ≤ c) — коолдинаты противоположных углов очередного постера. Гарантируется, что постеры не перекрываются.

После этого программа жюри выводит запросы. Каждый запрос состоит из четырёх целых чисел x1, y1, x2, y2 — координат противоположных углов очередного прямоугольника (0 ≤ x1, x2 ≤ r, 0 ≤ y1, y2 ≤ c).

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

После каждого запроса выведите одно число — ответ на соответствующий запрос.

Пример
Входные данные
8 11 3 4
1 1 5 5
7 7 5 4
4 6 2 7
1 1 7 8
2 2 4 3
3 4 6 7
2 9 3 10
Выходные данные
24
2
6
0
Примечание

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

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

M. Простая задача
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мебибайт
ввод
стандартный ввод или input.txt
вывод
стандартный вывод или output.txt

Эта задача проще, чем может показаться на первый взгляд.

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

Даны значения выражений и . Оба этих числа, а также сами числа a и b целые, неотрицательные и не превышают 10 000.

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

Мы не просим вас найти значения a и b. Нам будет достаточно, если вы выведете произведение этих чисел (a × b).

Примеры
Входные данные
81 25
Выходные данные
56
Входные данные
81 49
Выходные данные
32
Входные данные
100 64
Выходные данные
36
Примечание

В первом примере a = 14, b = 4 или наоборот. 14 × 4 = 56.

Во втором примере a = 16, b = 2 или наоборот. 16 × 2 = 32.

В третьем примере a = 18, b = 2 или наоборот. 18 × 2 = 36.