Задача A. Assignment ≡

Условие

Пусть выражение присваивания описывается следующей грамматикой

Comma = ",", { " " };

Digit = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9";
Number = "0" | ( Digit, { Digit | "0" } );

Letter = "A" | "B" | "C" | "D" | "E" | "F" | "G"
       | "H" | "I" | "J" | "K" | "L" | "M" | "N"
       | "O" | "P" | "Q" | "R" | "S" | "T" | "U"
       | "V" | "W" | "X" | "Y" | "Z" | "a" | "b"
       | "c" | "d" | "e" | "f" | "g" | "h" | "i"
       | "j" | "k" | "l" | "m" | "n" | "o" | "p"
       | "q" | "r" | "s" | "t" | "u" | "v" | "w"
       | "x" | "y" | "z" ;

Variable = Letter, { Letter | Digit | "0" };

Value = Variable | Number | EnclosedValueList | EmptyList;
ValueList = Value, { Comma, Value }, [ Comma ];
EnclosedValueList = "(", ValueList , ")";
EmptyList = "(", { " " }, ")";

Destination = Variable | EnclosedDestinationList;
DestinationList = Destination, { Comma, Destination }, ( [ Comma, "*", Variable ] | [ Comma ] );
EnclosedDestinationList = "(", DestinationList, ")";

Assignment = ( DestinationList | EnclosedDestinationList ), " = ", ( ValueList | EnclosedValueList );

Обе стороны выражения считаются потенциально вложенными списками. Переменной на левой стороне присваивается значение, расположенное на соответствующей позиции справа. Значение может быть числом (Number), переменной (Variable) или списком. Список должен быть заключен в круглые скобки и содержать как минимум одну запятую. Например, (a,) — список, но (a) — то же самое, что просто a. Также скобки могут быть опущены на верхнем уровне с обоих сторон. Присваивание выполняется сверху вниз, слева направо. Таким образом, переменная может является элементом списка справа, если ей уже были присвоено некоторое значение. В случае, если имя переменной начинается с символа *, ей присваивается потенциально пустой список, состоящий из всех оставшихся значений на этом уровне. Присваивание не может быть выполнено в том случае, когда для элемента списка с одной стороны не найдётся соответствующего элемента с другой, или переменная используется в качестве значения до присвоения ей значения.

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

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

Входные данные содержат единственную строку — выражение присваивания.

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

Если присваивание не может быть выполнено, необходимо вывести единственное число -1. Иначе выходные данные должны содержать простое выражение присваивания для каждой переменной в алфавитном порядке по одному в строке. Выражение должно соответствовать следующей грамматике

SimpleAssignment = Variable, " = ", NumberOrList;
NumberOrList= Number | ( "(", NumberOrList, { Comma, NumberOrList }, [ Comma ] ")" ) | EmptyList;

Ограничения

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

Размер входных данных не превосходит 10⁴ символов.

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

a, b, c = 42, 23, (23, 42)

a = 42
b = 23
c = (23, 42)

a, *b = 1, 2, 3, 4, 5

a = 1
b = (2, 3, 4, 5)

a, (b, c) = 42, (23, a)

a = 42
b = 23
c = 42

a, b = 42, 23, 10

-1

Задача B. Mirror for numbers ≡

Условие

В уездном городе N живут натуральные числа. Сегодня у них праздник, поэтому в парке аттракционов установили новое развлечение — числовое зеркало. Работает оно так: запись числа переводится в двоичную систему счисления, в зеркале его цифры отражаются в обратном порядке (если двоичная запись числа оканчивалась на один или несколько нулей, они отбрасываются). Получившаяся двоичная запись переводится обратно в натуральное число. Например, если к зеркалу подойдет число 26, то его двоичная запись 26₁₀ = 11010₂ запишется в обратном порядке 1011₂ (получившийся ведущий ноль отбросится) и в зеркале все увидят число 11.

К зеркалу последовательно подошли все числа, чья запись в двоичной системе счисления состоит ровно из d цифр. Определите, сколько из них увидели свое отражение в зеркале ...

1. меньше, чем исходное число;
2. равным исходному числу;
3. больше, чем исходное число.

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

Входные данные содержат натуральное число d.

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

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

Ограничения

1 ≤ d ≤ 50

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

В примере дано d = 4. К зеркалу подходили числа, чья длина в двоичной системе счисления равна 4, то есть числа из диапазона от 8 до 15.

Число 8 отразилось как 1, 9 как 9, 10 как 5, 11 как 13, 12 как 3, 13 как 11, 14 как 7 и 15 как 15.

Итого пять чисел отразились меньшими, чем исходные (8, 10, 12, 13 и 14), два — не изменились (9 и 15), одно отразились большим, чем исходное (11).

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

4

5
2
1

Задача C. Cell painting ≡

Условие

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

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

Единственная строка входных данных содержит натуральное число n — количество закрашенных клеточек.

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

Выведите одно неотрицательное целое число — количество различных способов закраски. Гарантируется, что ответ не превысит 10¹⁸.

Ограничения

1 ≤ n ≤ 200

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

Смотри рисунок.

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

14

6

Задача D. Decisive throw ≡

Условие

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

Тимофей должен бросить n обычных шестигранных кубиков, на сторонах которых нанесены числа от 1 до 6. Если хотя бы m из них выпадут удачно, то команда друзей победит. Кубик падает удачно, если на его верхней грани выпадает число не меньше a. Например, при a = 5, n = 3 и m = 2 Тимофей для победы должен бросить три кубика таким образом, чтобы по крайней мере на двух из них выпали числа 5 или 6.

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

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

Единственная строка входных данных содержит три целых числа: a, n и m.

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

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

Ограничения

1 ≤ a ≤ 6

1 ≤ m ≤ n ≤ 15

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

В первом примере существует 36 различных исходов выпадения двух кубиков, из них 27 являются успешными - хотя бы на одном кубике из двух выпадает число больше или равное четырем. Таким образом, вероятность успеха равна 27 / 36 или, после сокращения, 3 / 4.

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

4 2 1

3 4

5 3 2

7 27

Задача E. Square coins ≡

Условие

"Сенсационная находка!", "Археологи обнаружили древнюю цивилизацию!", "Ученые поражены развитием древних технологий!" — такими заголовками пестрели новости. Обнаруженные под толщей песка пустыни Сахары артефакты действительно поражали: совершенные приборы и механизмы, манускрипты и пергаменты с непонятными записями, предметы искусства и быта - всё указывало на существовавшую когда-то в этом регионе развитую цивилизацию. Ученые нацелились на долгую и кропотливую работу.

Нумизматов же, конечно заинтересовала денежная система Древнесахарцев (так окрестили обнаруженную цивилизацию). Были найдены золотые монеты разного размера, все исключительно квадратной формы и с квадратным отверстием посередине. Что интересно - все размеры (и сторон монет, и сторон отверстий) были нечетными числами. Было высказано предположение, что стоимость монеты соответствовала её площади: так на монете размером 5 с отверстием 1 было отчеканено 24 точки, на монете размером 5 с отверстием 3 нашлось 16 точек, на монете размером 3 с отверстием 1 отчётливо видно 8 точек. Всё указывало на то, что стоимость монеты равна разности квадратов стороны монеты и стороны отверстия: 5² − 1² = 24, 5² − 3² = 16, 3² − 1² = 8.

По данной стоимости монеты определите все её возможные размеры.

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

Входные данные содержат целое число n — стоимость монеты. Гарантируется, что n кратно восьми.

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

В первой строке выведите целое число k — количество различных возможных размеров монет. В следующих k строках выведите по два числа: размер стороны монеты и размер отверстия. Записи упорядочите по возрастанию сторон монет.

Ограничения

8 ≤ n ≤ 10¹²

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

В примере дана стоимость монеты 72. Ей могут соответствовать три подходящих размера: 9² − 3² = 81 − 9 = 72, 11² − 7² = 121 − 49 = 72 и 19² − 17² = 361 − 289 = 72.

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

72

3
9 3
11 7
19 17

Задача F. New function ≡

Условие

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

Функция Тимофея определена на множестве натуральных чисел следующим образом: f(x) = x + ⌊ x10⌋  + ⌊ x100⌋  + ⌊ x1000⌋  + …, где ⌊ x10ⁿ⌋ означает округление результата деления вниз до целой части. Например, f(404) = 404 + ⌊ 40410⌋  + ⌊ 404100⌋  = 404 + 40 + 4 = 448.

Пока Тимофей оформляет статью в математический журнал, найдите такое число x, что f(x) = n.

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

Входные данные содержат натуральное число n — значение функции.

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

Выведите одно натуральное число — аргумент функции, при котором достигается данное значение. Гарантируется, что такое число единственно.

Ограничения

1 ≤ n ≤ 10¹⁸

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

448

404

Задача G. Siblings ≡

Условие

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

Данные для исследования представляет собой таблицу, в которой n строк и 3 столбца. В первом столбце указан id номер человека. Во втором и третьем столбцах указаны id номера его родителей в произвольном порядке.

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

Первая строка входных данных содержит натуральное число n — количество записей в базе данных, В следующих n строках через пробел расположены три натуральных числа x_i, y_i, z_i — id номера в описанном выше формате.

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

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

Ограничения

2 ≤ n ≤ 10⁵

1 ≤ x_i, y_i, z_i ≤ 10⁹

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

Предложенную в примере таблицу удобно представить в виде графа. По нему видно, что у четырех человек (id номера 207, 208, 411 и 511) общие родители. Остальные группы сиблингов не такие многочисленные.

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

11
104 48 60
511 130 120
111 1 2
112 2 1
208 120 130
120 2 1
130 32 17
207 120 130
170 32 17
191 104 111
411 130 120

4
207 208 411 511

Задача H. Right triangle ≡

Условие

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

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

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

В первой строке входных данных заданы целые числа x₁ и y₁, во второй строке заданы целые числа x₂ и y₂, в третьей строке заданы целые числа x₃ и y₃ — координаты трех точек. Все точка попарно различные.

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

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

Ограничения

 − 10⁴ ≤ x_i, y_i ≤ 10⁴

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

0 0
0 8
6 0

YES

1 2
3 2
4 1

NO

Задача I. Imictcoin ≡

Условие

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

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

Например:

• s = «abababc» — верный хэш;
• s = «aabcabab» — неверный хэш;
• s = «a» — верный хэш.

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

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

В первой строке записано одно целое число T — количество строк. Далее следуют T строк s_i, по одной в строке данных. Строки состоят из строчных букв латинского алфавита.

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

Для каждой строки s_i выведите в отдельной строке:

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

Ограничения

1 ≤ T ≤ 10⁴.

Длина s_i не превышает 5 ⋅ 10⁵. Сумма длин всех строк s во всех наборах входных данных теста не превышает 5 ⋅ 10⁵.

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

2
aabb
aaaabb

abab
-1

1
a

a

Задача J. Chess with obstacles ≡

Условие

Юные программисты Джо и Бо сидели на скучной лекции и решили сыграть в собственную версию шахмат.

На шахматном поле размера 8 × 8 располагается белый король, чёрная пешка и некоторое количество препятствий. Белые ходят первыми. Чёрная пешка ходит сверху вниз ровно на одну клетку, а король может ходить на любую соседнюю клетку (см. изображение):

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

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

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

Входные данные содержат 8 строк, каждая из которых содержит 8 символов. Символы имеют следующие значения:

• '0' — обозначает пустую клетку;
• '1' — обозначает клетку с препятствием;
• 'K' — обозначает белого короля;
• 'P' — обозначает чёрную пешку.

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

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

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

00000001
00000000
00000000
0P00K000
00000000
00100000
00001000
00000000

3

00000000
00000000
00000000
00000000
000K0000
00000000
000P0000
00000000

-1

Задача K. Rock by rock ≡

Условие

Братья Боба и Абоба решили поиграть в известную им с детства игру. В этой игре перед игроками в ряд выложено n камней. Каждый камень может быть маленьким или большим. В свой ход игрок должен взять самый левый камень в ряду и выполнить одно из двух действий:

1. Ударить камень о землю, тем самым разбив его.
2. Ударить камень о ближайший камень справа. В таком случае возможно два исхода:
   • Если размеры камней совпадают, то оба камня разбиваются.
   • Если один камень большой, а другой маленький, то в результате удара большой камень сколется и станет маленьким, а маленький разобьется. Таким образом, вместо двух камней останется только один маленький камень.

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

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

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

Входные данные содержат первой строке целое число n — количество камней в ряду.

Во второй строке содержится n символов через пробел, символ «l» обозначает большой камень, а символ «s» — маленький камень.

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

Выходные данные должны содержать Aboba, если выиграет Абоба, либо Boba в противном случае.

Ограничения

1 ≤ n ≤ 10⁵

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

4
l s l s

Boba

2
l s

Boba