Организаторы чемпионата мира по программированию ACM ICPC приготовили для всех участников финала вкусный и питательный перекус, который они получат прямо во время соревнований. Каждый участник получит сладкий банан, так как сладкое помогает работе мозга и решению задач, и бутылочку минеральной воды, которая способствует быстрому усвоению этого банана. Ваша задача - помочь организаторам финала рассчитать, сколько будет стоить перекус для всех участников.
В одной строке записаны три целых числа: N — количество участников, X — стоимость одного банана и Y — стоимость одной бутылочки с минералкой (1 ≤ N, X, Y ≤ 1000).
Выведите одно целое число — суммарную стоимость перекуса на всех участников.
100 20 35
5500
Егор — школьник. 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
У Витали есть белый кубик с одной красной гранью. Кубик стоит в левом верхнем углу шахматной доски красной гранью вверх.
Кубик можно перекатывать по граням в любую клетку, имеющую общую сторону с той, в которой в данный момент находится кубик. При этом кубик перекатывается через соответствующее ребро. Выкатывать кубик за пределы доски запрещено.
Придумайте последовательность ходов перемещающую кубик в правый верхний угол так, чтобы он ни разу не касался поля доски красной гранью, а по завершении своего маршрута остался стоять красной гранью вверх.
В каждой клетке поля кубик должен побывать хотя бы один раз, а количество ходов должно быть не больше 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
Василий в этом году заканчивает 9 класс и мечтает поступить в Физико-математическую школу СФУ (ФМШ). Для подготовки к вступительному экзамену он прорешивает задания прошлых лет. Одно задание показалась Василию особенно сложным, но очень интересным. Василий всё-таки смог решить это задание. А вы сможете?
В ряд выписаны все целые числа от 1 до N. За одну операцию можно удалить либо все числа на чётных позициях, либо на нечётных. Оставшиеся числа образуют новый ряд. Позиции пронумерованы с единицы, слева направо. Необходимо вывести последовательность операций, после которых в ряду останется единственное число A.
Два целых числа: N — количество чисел и A — число, которое должно остаться после всех операций (1 ≤ A ≤ N ≤ 1018).
Выведите последовательность операций в одной строке. Для удаления всех чисел на чётных позициях выведите 0, для удаления чисел на нечётных позициях выведите 1.
10 5
0 0 1
В нашей повседневной жизни шоколадки дарят по праздникам, просто покупают для посиделок, а иногда на них спорят. Обычная шоколадная плитка представляет собой прямоугольник из долек, который иногда приятнее ломать, чем наслаждаться самой шоколадкой.
Вот и вы проспорили своему другу Тессекарпу очередную шоколадку. А так как ваш друг четырёхмерный, он признаёт только трёхмерные плитки шоколада. Вы смогли найти такую шоколадку, а именно, подарили ему шоколадный параллелепипед размера 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
Вам дано N кодовых слов ненулевой длины, состоящих из 0 и 1, причём известно, что для этих слов выполняется условие Фано: никакое кодовое слово не может быть началом другого кодового слова.
Вам нужно ответить на следующий вопрос: какое минимальное количество кодовых слов (любой длины) нужно добавить в это множество, чтобы:
В первой строке содержится целое положительное число N — количество известных кодовых слов.
Далее в N строках содержатся кодовые слова, по одному на строке.
Гарантируется, что суммарная длина кодовых слов не превышает 106, и что все кодовые слова имеют ненулевую длину.
В единственной строке выведите одно целое число — ответ на задачу.
2
010
001
3
3
1
01
00
0
Поликарп и его компания решили съездить в соседнее село на дискотеку.
Всего в области, в которой они живут, находится 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
Поликарп приобрёл на барахолке кусок каменной плиты. Старик, показавший ему этот камень, утверждал, что это кусок Великой Таблицы Умножения — монумента, которому поклонялось племя коммутативных инков. Таблицу не зря называли великой — она была таблицей умножения размера 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
А вы знаете, как задаются двоичные числа в бизоновом формате?
Двоичное число в бизоновом формате задается последовательностью целых положительных чисел: a1, a2, ..., an. Данная запись обозначает, что в двоичном числе слева направо сначала записаны a1 цифр 1, затем a2 цифр 0, затем a3 цифр 1, затем a4 цифр 0, затем a5 цифр 1 и т. д.
Вот несколько примеров перевода двоичных чисел из бизонового формата в обычный:
Вам дано два числа в бизоновом формате, необходимо сложить их и вывести сумму в бизоновом формате.
Первая строка содержит 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
Ромка недавно вернулся с юбилея своего друга Сашки. Праздник отмечался с размахом и Ромка подумал: а что, если бы юбилеи были чаще? Можно же не ограничиваться десятичной системой счисления.
Ромка ввёл понятие юбилейности числа, равное максимальному количеству нулей в конце записи этого числа в какой-то системе счисления с основанием B, где B — целое число, большее единицы.
Например, юбилейность числа 256 равна 8, так как в двоичной системе счисления оно оканчивается на 8 нулей.
Ромка хочет узнать, когда его ближайший следующий значимый юбилей, если сейчас ему X лет? Значимым юбилеем он считает количество лет, которое обладает юбилейностью как минимум L.
Единственная строка ввода содержит два целых числа X и L (1 ≤ X ≤ 1012; 1 ≤ L ≤ 50).
Выведите единственное число — ответ на задачу.
9990 4
10000
100 8
256
100 2
104
Ваня играет в коллекционную карточную игру.
Сейчас у его соперника на столе находится 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
В первом примере каждая стрела может попасть либо в единственное существо, либо в героя противника. Чтобы существо погибло, все три стрелы должны попасть именно в него, вероятность этого 
Это интерактивная задача.
Таня постоянно участвует в различных сборах по программированию. Каждый раз, приехав с очередных сборов, она вешает прямоугольный постер с этих сборов таким образом, что постеры не перекрываются друг с другом, а их стороны направлены по горизонтали и вертикали.
Сейчас Таня приехала с нескольких подряд поездок на сборы, и у неё набралось некоторое количество новых постеров. Для того, чтобы найти лучшее место для этих постеров, Таня рисует воображаемый прямоугольник со сторонами, параллельными сторонам существующих постеров, и смотрит, какова площадь той части прямоугольника, которая перекрывается с каким-либо постером.
Ваша задача — помочь Тане с подсчётами. Так как варианты перебираются один за другим, то ответ на каждый запрос необходимо выдавать до того, как поступил следующий.
В первой строке программа жюри передаёт программе участника четыре целых числа 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
Для корректной работы программы после каждой операции вывода данных вам необходимо очищать буфер вывода, то есть делать следующие операции:
Эта задача проще, чем может показаться на первый взгляд.
Даны значения выражений
и
. Оба этих числа, а также сами числа 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.