Входной файл: | Стандартный вход | Ограничение времени: | 5 сек | |
Выходной файл: | Стандартный выход | Ограничение памяти: | 512 Мб |
Пусть выражение присваивания описывается следующей грамматикой
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;
Гарантируется, что исходное выражение соответствует грамматике.
Размер входных данных не превосходит 104 символов.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
2 |
|
|
3 |
|
|
4 |
|
|
Автор: | Anton Karabanov | Ограничение времени: | 1 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 512 Мб | |
Выходной файл: | Стандартный выход |
В уездном городе N живут натуральные числа. Сегодня у них праздник, поэтому в парке аттракционов установили новое развлечение — числовое зеркало. Работает оно так: запись числа переводится в двоичную систему счисления, в зеркале его цифры отражаются в обратном порядке (если двоичная запись числа оканчивалась на один или несколько нулей, они отбрасываются). Получившаяся двоичная запись переводится обратно в натуральное число. Например, если к зеркалу подойдет число 26, то его двоичная запись 2610 = 110102 запишется в обратном порядке 10112 (получившийся ведущий ноль отбросится) и в зеркале все увидят число 11.
К зеркалу последовательно подошли все числа, чья запись в двоичной системе счисления состоит ровно из d цифр. Определите, сколько из них увидели свое отражение в зеркале ...
Входные данные содержат натуральное число 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).
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
Автор: | Anton Karabanov | Ограничение времени: | 1 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 512 Мб | |
Выходной файл: | Стандартный выход |
Тимофей на скучном уроке закрашивает клеточки на полях тетрадки. В первой строке он закрасил одну клеточку, во второй — две, а в каждой следующей — на одну больше или меньше, чем в предыдущей. Когда урок завершился, оказалось, что Тимофей замазал ровно n клеточек. Сколько способов у него было это сделать? Поля узкие, поэтому больше трех клеточек в одной строке Тимофей не закрашивал.
Единственная строка входных данных содержит натуральное число n — количество закрашенных клеточек.
Выведите одно неотрицательное целое число — количество различных способов закраски. Гарантируется, что ответ не превысит 1018.
1 ≤ n ≤ 200
Смотри рисунок.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
Автор: | Антон Карабанов | Ограничение времени: | 1 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 512 Мб | |
Выходной файл: | Стандартный выход |
Тимофей с друзьями увлекся настольными ролевыми играми. Все карманные деньги они тратят на фигурки персонажей, карты подземелий, красивые кубики и, конечно, интересные игры. Сегодня компания друзей впервые собралась за новой игрой "Олимп". По прошествии четырех часов наступила кульминация — исход игры зависит от завершающего хода Тимофея.
Тимофей должен бросить 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.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
2 |
|
|
Автор: | Anton Karabanov | Ограничение времени: | 1 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 512 Мб | |
Выходной файл: | Стандартный выход |
"Сенсационная находка!", "Археологи обнаружили древнюю цивилизацию!", "Ученые поражены развитием древних технологий!" — такими заголовками пестрели новости. Обнаруженные под толщей песка пустыни Сахары артефакты действительно поражали: совершенные приборы и механизмы, манускрипты и пергаменты с непонятными записями, предметы искусства и быта - всё указывало на существовавшую когда-то в этом регионе развитую цивилизацию. Ученые нацелились на долгую и кропотливую работу.
Нумизматов же, конечно заинтересовала денежная система Древнесахарцев (так окрестили обнаруженную цивилизацию). Были найдены золотые монеты разного размера, все исключительно квадратной формы и с квадратным отверстием посередине. Что интересно - все размеры (и сторон монет, и сторон отверстий) были нечетными числами. Было высказано предположение, что стоимость монеты соответствовала её площади: так на монете размером 5 с отверстием 1 было отчеканено 24 точки, на монете размером 5 с отверстием 3 нашлось 16 точек, на монете размером 3 с отверстием 1 отчётливо видно 8 точек. Всё указывало на то, что стоимость монеты равна разности квадратов стороны монеты и стороны отверстия: 52 − 12 = 24, 52 − 32 = 16, 32 − 12 = 8.
По данной стоимости монеты определите все её возможные размеры.
Входные данные содержат целое число n — стоимость монеты. Гарантируется, что n кратно восьми.
В первой строке выведите целое число k — количество различных возможных размеров монет. В следующих k строках выведите по два числа: размер стороны монеты и размер отверстия. Записи упорядочите по возрастанию сторон монет.
8 ≤ n ≤ 1012
В примере дана стоимость монеты 72. Ей могут соответствовать три подходящих размера: 92 − 32 = 81 − 9 = 72, 112 − 72 = 121 − 49 = 72 и 192 − 172 = 361 − 289 = 72.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
Автор: | Anton Karabanov | Ограничение времени: | 1 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 512 Мб | |
Выходной файл: | Стандартный выход |
Тимофей придумал новую функцию и назвал её своим именем. Теперь его имя гордо красуется рядом с именами Эйлера, Мёбиуса и Римана — в их честь тоже названы функции. Правда практического применения своего открытия Тимофей ещё не придумал, но активно работает в этом направлении.
Функция Тимофея определена на множестве натуральных чисел следующим образом: f(x) = x + ⌊ x10⌋ + ⌊ x100⌋ + ⌊ x1000⌋ + …, где ⌊ x10n⌋ означает округление результата деления вниз до целой части. Например, f(404) = 404 + ⌊ 40410⌋ + ⌊ 404100⌋ = 404 + 40 + 4 = 448.
Пока Тимофей оформляет статью в математический журнал, найдите такое число x, что f(x) = n.
Входные данные содержат натуральное число n — значение функции.
Выведите одно натуральное число — аргумент функции, при котором достигается данное значение. Гарантируется, что такое число единственно.
1 ≤ n ≤ 1018
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
Автор: | Anton Karabanov | Ограничение времени: | 1 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 512 Мб | |
Выходной файл: | Стандартный выход |
Сиблинги — термин, используемый в социальной антропологии и других науках, который обозначает детей одних родителей. Различают полнородных сиблингов, имеющих общих мать и отца, и неполнородных, у которых общим является только один родитель. В руки психологов, изучающих проблему сиблингового соперничества, попала таблица базы данных людей, проживающих в одном доме. Помогите учёным выделить наиболее многочисленную группу полнородных сиблингов для дальнейшего исследования.
Данные для исследования представляет собой таблицу, в которой n строк и 3 столбца. В первом столбце указан id номер человека. Во втором и третьем столбцах указаны id номера его родителей в произвольном порядке.
Первая строка входных данных содержит натуральное число n — количество записей в базе данных, В следующих n строках через пробел расположены три натуральных числа xi, yi, zi — id номера в описанном выше формате.
Выведите в первой строке одно натуральное число — наибольшее количество полнородных сиблингов (гарантируется, что такое количество единственно). Во второй строке в порядке возрастания выведите их id номера.
2 ≤ n ≤ 105
1 ≤ xi, yi, zi ≤ 109
Предложенную в примере таблицу удобно представить в виде графа. По нему видно, что у четырех человек (id номера 207, 208, 411 и 511) общие родители. Остальные группы сиблингов не такие многочисленные.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
Автор: | А. Лепёха | Ограничение времени: | 1 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 512 Мб | |
Выходной файл: | Стандартный выход |
Саша закончил школу и решил поступить на программиста в местный университет. Одним из первых предметов в его курсе стала «Геометрия и топология чисел». На первом же занятии всей группе задали вывести и доказать теорему, которая бы позволила по трем точкам на плоскости определить, является ли треугольник образованный ими прямоугольным.
Саша смог придумать несколько теорем, но его теоремы почему-то дают разные ответы. Напишите программу, которая по координатам трех точек сможет верно определить, образуют это точки прямоугольный треугольник.
В первой строке входных данных заданы целые числа x1 и y1, во второй строке заданы целые числа x2 и y2, в третьей строке заданы целые числа x3 и y3 — координаты трех точек. Все точка попарно различные.
Выходные данные должны содержать YES
, если данные точки образуют прямоугольный треугольник, или NO
в противном случае.
− 104 ≤ xi, yi ≤ 104
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
2 |
|
|
Входной файл: | Стандартный вход | Ограничение времени: | 1 сек | |
Выходной файл: | Стандартный выход | Ограничение памяти: | 512 Мб |
В связи с образованием нового института в одном небезызвестном университете, его лучшие программисты решили создать свою крипто монету «Имикткоин». Но главный специалист по компьютерной безопасности Сергей придумал специальные правила по которым должен подбираться хэш для каждого следующего блока в блокчейне.
Хэш должен представлять из себя строку, состоящую из строчных букв латинского алфавита, которая должна удовлетворять одному единственному условию — ни один символ не встречается два раза подряд.
Например:
Требуется написать программу, которая преобразует входную строку в верный хэш путём перестановок символов в ней либо определит, что сделать это невозможно.
В первой строке записано одно целое число T — количество строк. Далее следуют T строк si, по одной в строке данных. Строки состоят из строчных букв латинского алфавита.
Для каждой строки si выведите в отдельной строке:
1 ≤ T ≤ 104.
Длина si не превышает 5 ⋅ 105. Сумма длин всех строк s во всех наборах входных данных теста не превышает 5 ⋅ 105.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
2 |
|
|
Входной файл: | Стандартный вход | Ограничение времени: | 1 сек | |
Выходной файл: | Стандартный выход | Ограничение памяти: | 512 Мб |
Юные программисты Джо и Бо сидели на скучной лекции и решили сыграть в собственную версию шахмат.
На шахматном поле размера 8 × 8 располагается белый король, чёрная пешка и некоторое количество препятствий. Белые ходят первыми. Чёрная пешка ходит сверху вниз ровно на одну клетку, а король может ходить на любую соседнюю клетку (см. изображение):
Некоторые клетки заняты препятствиями. Если на клетке находится препятствие, то король не может ходить на эту клетку. Если король ходит на клетку, на которой находится пешка, то он её "съедает". Цель белых "съесть" чёрную пешку до того как она дойдёт до самой нижней горизонтали. Цель же чёрных добраться до нижней горизонтали, не оказавшись до этого "съеденными" белым королём.
Джо и Бо хотят определить по начальному положению фигур, кто выиграет и, если выиграют белые, то какое минимальное количество ходов для этого потребуется. Гарантируется, что на пути пешки не будет препятствий. Белые всегда ходят первые. Пропуск хода возможен только при отсутствии доступных клеток для хода.
Входные данные содержат 8 строк, каждая из которых содержит 8 символов. Символы имеют следующие значения:
0
' — обозначает пустую клетку;1
' — обозначает клетку с препятствием;K
' — обозначает белого короля;P
' — обозначает чёрную пешку.Выведите минимальное количество ходов, необходимое королю, чтобы "съесть" пешку, либо − 1, если белый король не успеет "съесть" чёрную пешку до того, как она дойдёт до нижней горизонтали.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
2 |
|
|
Автор: | А. Лепёха | Ограничение времени: | 1 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 512 Мб | |
Выходной файл: | Стандартный выход |
Братья Боба и Абоба решили поиграть в известную им с детства игру. В этой игре перед игроками в ряд выложено n камней. Каждый камень может быть маленьким или большим. В свой ход игрок должен взять самый левый камень в ряду и выполнить одно из двух действий:
После этого ход переходит к другому игроку. Выигрывает тот игрок, который своим ходом разобьет последний камень (или последние два камня).
Требуется написать программу, которая определит, кто из братьев выиграет, если первым ходит Абоба.
Входные данные содержат первой строке целое число n — количество камней в ряду.
Во второй строке содержится n символов через пробел, символ «l
» обозначает большой камень, а символ «s
» — маленький камень.
Выходные данные должны содержать Aboba
, если выиграет Абоба,
либо Boba
в противном случае.
1 ≤ n ≤ 105
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
2 |
|
|