Задача A. Запертая комната ≡

Условие

Тимофей пытается найти выход из квестовой комнаты и ему осталось пройти последнее испытание - автомат, который блокирует входную дверь. У автомата есть индикатор, на котором светится число 1. Еще у автомата есть три кнопки, первая из которых увеличивает число на индикаторе вдвое, вторая - возводит число на индикаторе в квадрат, третья - стирает у числа последнюю цифру. Индикатор позволяет выводить только k разрядов числа, поэтому если в результате нажатий кнопок получается число большее или равное 10^k, то автомат сбрасывает число на индикаторе снова на 1. То же самое происходит при попытке отбросить последнюю цифру от однозначного числа.

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

Формат входных данных

В единственной строке входного файла через пробел записаны два натуральных числа k и n.

Формат выходных данных

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

Ограничения

2 ≤ n ≤ 100.

2 ≤ k ≤ 6.

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

В первом примере Тимофей может превратить 1 в 4 с помощью двух нажатий первой кнопки. Затем превратить 4 в 256 с помощью двух нажатий второй кнопки. Наконец, получить из 256 число 25 с помощью третьей кнопки. Всего потребуется 5 нажатий. Правильной последовательностью также будет строка 12223, но 11223 лексикографически меньше.

Во втором примере Тимофею придется последовательно получать числа 2, 4, 8, 64, 6, 36, 72, 7, 14, 28, 56, 5, 25.

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

6 25

5
11223

2 25

13
1112321311132

Задача B. Саша и крышки ≡

Условие

Девочка Саша каждый год собирает крышки от газировки, чтобы на новогодней акции получить призы, но ещё ни разу у неё не получилось накопить достаточно.

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

При этом одной крышке текущего года эквивалентны четыре крышки позапрошлого года или две крышки прошлого года.

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

Сколько призов может получить Саша в этом году, если цена одного приза K крышек, а у девочки A крышек текущего года, B крышек прошлого года и C крышек позапрошлого года?

Формат входных данных

В единственной строке через пробел записаны четыре неотрицательных целых числа K, A, B, C — стоимость приза в крышечках, количество крышек текущего, прошлого и позапрошлого годов соответственно.

Формат выходных данных

Выведете одно неотрицательное целое число - количество призов, которое может получить Саша.

Ограничения

1 ≤ K ≤ 10¹²

0 ≤ A, B, C ≤ 10¹²

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

1 1 2 4

3

15 25 18 14

2

100 70 30 80

1

Задача C. Игра на перемене ≡

Условие

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

1. Из кучи можно забрать одну любую монетку;

2. Можно вытащить из кучи одну монетку достоинством в два рубля (если она там есть), разменять ее у друзей и положить в кучу две монетки достоинством в один рубль;

3. Можно вытащить из кучи одну монетку достоинством в пять рублей (если она там есть), разменять ее у друзей и положить в кучу две монетки достоинством в два рубля и одну монетку достоинством в один рубль.

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

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

Формат входных данных

В единственной строке входного файла через пробел записаны неотрицательные числа a, b, c — количества монет достоинством в один, два и пять рублей соответственно. Гарантируется, что a + b + c ≠ 0.

Формат выходных данных

Выведите имя победителя игры — Petya или Vasya.

Ограничения

0 ≤ a, b, c ≤ 10⁹

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

2 0 0

Vasya

1 2 0

Petya

1 1 1

Petya

Problem D. Вася и Суперкомпьютер ≡

Statement

Programmer Vasya decided to become a man, who solved most problems. To make his wish come true he invented a Supercomputer, which could do next tasks: generate a random problem (0) and solve a random problem (1) instead of Vasya (the problem may not be generated by the first task - Vasya already had an unlimited list of problems to solve).

Unfortunately, implementation features didn't allow to keep the Supercomputer on all day long: every day it could do limited number of tasks. Furthermore, every day the supercomputer must start with the task of the same type, which he ended previous day (first day could be started with any task).

So, Supercomputer worked several days and then broke down. In Supercomputer's log Vasya found that all records are shuffled and there are extra records, which don't belong to this log. You should help Vasya to count maximum count of completed tasks that Supercomputer could do before crash.

Input format

The first line of the input file contains one number N - number of records in the log

Following N lines contains number M_i - number of tasks, completed in some day, and a string S_i of M_i characters 0 and 1 - description of tasks, completed in that day.

Log records are not chronologically ordered. Some records could be excess.

Output format

The output file must contain one number - maximum number of tasks, which Supercomputer could do before the crash.

Constraints

Total length of all S_i does not exceed 5 ⋅ 10⁵

Sample tests

6
4 1111
3 100
5 00101
2 00
10 1001010110
2 01

26

6
3 100
5 10100
2 11
6 011101
3 110
2 10

16

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

Условие

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

Формат входных данных

Входные данные содержат одну непустую строку — описание клавиатуры. Белым клавишам соответствует символ 1, а черным — 0.

Формат выходных данных

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

Ограничения

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

0101

4

001101001

8

Задача F. Столы с закусками ≡

Условие

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

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

1) переставлять сразу по два предмета с одного стола на другой — самый быстрый способ исправить всё к приходу гостей;

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

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

Формат входных данных

Входные данные содержат два целых числа: A и B.

Формат выходных данных

Выходные данные должны содержать два целых числа: количество закусок, которые нужно съесть с первого и второго стола соответственно.

Ограничения

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

2 1

0 1

Задача G. Утки и крокодилы ≡

Условие

Парк представляет из себя N полян, соединённых M ненаправленными тропинками одинаковой длинны.

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

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

Формат входных данных

Первая строка входного файла содержит два числа N и M, количество полян и количество тропинок.

Следующие M строк содержат по два числа u_i, v_i  — номера полян, соединенных i-ой тропинкой.

Формат выходных данных

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

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

Ограничения

6 ≤ N ≤ 15

6 ≤ M ≤  N * (N − 1)2

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

8 10
1 2
1 3
2 3
2 4
3 5
4 5
4 6 
5 7
6 8
7 8

2

6 10
1 2
1 3
2 3
2 4
2 5
3 4
3 5
4 5
4 6
5 6

0

Задача H. Почтовый индекс ≡

Условие

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

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

Линии, образующие стороны квадрата, Тимофей называет прямыми, а диагонали квадрата - наклонными. Например, в цифре 9 четыре прямых и одна наклонная линия.

Сегодня Тимофей должен написать письмо-приглашение своему другу, с которым он познакомился в международном лагере юных программистов, да вот беда - Тимофей совсем забыл его почтовый индекс. Все, что он помнит, так это количество прямых и наклонных линий в его индексе, и то, что он является наименьшим натуральным числом из всех подходящих. Помогите Тимофею! Учтите, что длина индекса в других странах может быть произвольной (а не 6, как в России), а также то, что никакой индекс не может начинаться с нуля.

Формат входных данных

В единственной строке через пробел записаны два неотрицательных целых числа a и b — количества прямых и наклонных линий в индексе.

Формат выходных данных

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

Ограничения

0 ≤ a ≤ 10³

0 ≤ b ≤ 10²

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

10 1

28

5 4

Wrong

23 5

100236

Задача Y. Гиперпрыжок ≡

Условие

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

В силу конструктивных особенностей летательного аппарата, он может производить взлет только с оси OX под углом 45^∘, образуя острый угол между прямой траекторией взлета и положительным направлением OX.

Астероидное облако представляет собой N астероидов на плоскости, каждый из которых имеет форму круга радиусом r_i и располагается в координате x_i y_i.

Для эффектного и безопасного взлета нужно подобрать подходящий коридор между астероидами, здесь-то и нужна ваша помощь! Вам нужно найти все коридоры ненулевой ширины в астероидном облаке. Каждый коридор представляет собой полосу, ограниченную сверху и снизу прямыми, наклон которых к оси OX составляет 45^∘, такую, что её ширина максимально возможна, а на самой полосе нет частей астероидов. Шириной коридора считается расстояние между ограничивающими его прямыми.

Формат входных данных

Входные данные содержат два целое число N и затем N троек целых чисел x_i y_i r_i.

Формат выходных данных

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

Ограничения

2 ≤ N ≤ 10⁵

0 ≤ |x_i|, y_i ≤ 10⁵,

1 ≤ r_i ≤ 10³

r_i < y_i

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

2
4 2 1
2 4 1

1
0.828427