Задачи командных соревнований PRIME TIME 2016

Курсанты академии джедаев часто сбегают в самоволку, перепрыгивая забор с помощью Силы. Такой прыжок имеет форму равнобедренного треугольника со сторонами равными `L`. Чтобы курсанты не могли самовольно покидать академию, мастер Йода решил устроить болото перед забором, но ему необходимо вычислить максимальную ширину болота, которую могут перескочить курсанты при прыжке через забор.

Первая строка ввода содержит два целых числа: длина прыжка `L` и высота забора `H` (`1\ ≤\ H\ <\ L\ ≤\ 1000`).

Вывести одно число – максимальную ширину болота, которую могут перепрыгнуть курсанты с точностью `10^{-8}`.

5 2

5.33757024

За свой блестящий внешний вид и хорошо подвешенный язык C-3PO был выбран ведущим галактического шоу "Гурман". В шоу участвует шесть человек. Перед каждым раундом участникам объявляют список продуктов, которые могут быть использованы в текущем раунде (количество вариантов может быть от 4 до 8). Затем ведущий выбирает один из них и дает его попробовать или понюхать каждому из участников, сидящих с завязанными глазами. Участники должны определить название продукта. Если только один участник угадывает правильно, он получает 6 очков, если угадывают два участника – каждый из них получает по 3 очка, если три участника – каждый из них получает по 2 очка, если правильный ответ дают более трех участников – каждый из них получает по 1 очку.

Так как такие математические вычисления слишком сложны для C-3PO, напишите программу, которая поможет C-3PO подводить итоги после каждого раунда.

Первая строка ввода содержит одно число `N` (`1\ ≤\ N\ ≤\ 10`) – количество раундов. Далее следует `N` строк, содержащих по 7 целых чисел – номер правильного варианта и ответы участников.

Вывести `N` строк, в каждой строке вывести 6 целых чисел – суммарное количество очков у участников после соответствующего раунда.

3
1 2 2 1 3 3 2
3 4 3 2 3 1 3
4 4 4 4 4 2 4 

0 0 6 0 0 0
0 2 6 2 0 2 
1 3 7 3 0 3

C-3PO doesn't like numbers, except for the primes, but preferably quite prime numbers. The number is called a quite prime number, if it is a prime number and sum of its digits is a quite prime number. For example, 31 isn't a quite prime, as the sum of its digits `3\ +\ 1\ =\ 4` isn't a prime, but 29 is a quite prime, as it is a prime, `2\ +\ 9\ =\ 11` is a prime and `1\ +\ 1\ =\ 2` is a prime.

First line contains one integer `N` (`2\ ≤\ N\ ≤\ 10^{12}`).

Program should print YES, if `N` is a quite prime, and NO otherwise.

31

NO

29

YES

R2-D2 нужно незаметно провести истребитель Люка к имперской крепости. В начальный момент времени истребитель находится на высоте 1 метр на расстоянии `L` метров от крепости, расположенной на вершине скалы высотой `H` метров. Истребитель не может взлетать выше высоты `H`, чтобы не быть обнаруженным, и не может опускаться до нулевой высоты. За каждую единицу времени истребитель пролетает 1 метр по горизонтали, при этом он может либо сохранить прежнюю высоту полета, либо изменить её на целое число метров, но не более чем на `K` метров.

R2-D2 хочет определить количество различных возможных маршрутов полета, которые приведут истребитель из стартовой позиции в крепость. Так как количество может быть велико, ему достаточно получить остаток от деления результата на `10^9+9`.

Первая строка ввода содержит три целых числа – расстояние до крепости `L` (`1\ ≤\ L\ ≤\ 10^12`), высота `H` (`1\ ≤\ H\ ≤\ 100`) и ограничение изменения высоты `K` (`1\ ≤\ K\ ≤\ H`).

Вывести остаток от деления количества вариантов маршрута на `10^9+9`.

5 4 2

108

C-3PO is a passionate lover of riddles. The newest type of riddles he has come across requires the solver to check whether the given word is a multigram. A multigram is a word that consists of concatenating two or more words that are all mutually anagrams. The first of these words is called the root of the multigram. For instance, the word bbabab is a multigram with the root bba because it consists of anagrams bba and bab.

Help C-3PO solve the riddle by determining whether his word is a multigram and determining its root in case it is. If there are multiple possible roots of the multigram, output the shortest.

Note: Two words are mutually anagrams if one of them can be obtained from the other by changing the letter order.

The first and only line of input contains a word of length at most 300000 lowercase English characters.

If the given word is not a multigram, output "No solution". Otherwise, output the shortest root of the given word in one line.

aaaa

a

ab

No solution

bbabab

bba

C-3PO не слишком силен в математике, но иногда ему нужно хранить в памяти некоторые числовые данные. Чтобы не быть похожим на R2-D2, который использует заурядное двоичное представление чисел, C-3PO решил использовать в качестве основания системы счисления отношение золотого сечения `Phi`, равное `(1+sqrt(5))/2`, свойства которого намекают на его иррациональное мышление и на его золотой корпус.

Любое натуральное число можно представить в виде суммы положительных и отрицательных степеней числа `Phi`, где каждая степень используется не более одного раза. Например, `1=Phi^0`, `2=Phi^0+Phi^{-1}+Phi^{-2}=Phi^1+Phi^{-2}`, `3=Phi^1+Phi^0+Phi^{-2}=Phi^2+Phi^{-2}`. Для упрощения запоминания C-3PO желает найти вариант представления с минимальным числом слагаемых.

Первая строка ввода одно целое число `N` (`1\ ≤\ N\ ≤\ 10^{18}`) – значение, которое нужно представить в золотой системе счисления.

В первой строке вывести одно целое число – минимальное количество слагаемых в золотом представлении числа `N`. Во второй строке вывести использованные в представлении степени в порядке убывания.

3

2
2 -2

Энакину нужно открыть сейф в штаб-квартире джедаев, чтобы похитить секрет изготовления световых мечей. Для открытия замка устанавливается код с помощью несколько колес, на которых нанесены цифры от 0 до 9. Колеса можно вращать только с помощью Силы. За одно воздействие Силой одно из колес можно повернуть на одну позицию по или против часовой стрелки. Чтобы не вызвать тревогу, Энакин должен минимизировать количество воздействий на замок при открытии сейфа.

Ввод содержит две строки одинаковой длины от 1 до 10 символов – текущий код, установленный на замке, и код, который открывает замок.

Вывести одно число – минимальное количество воздействий на замок, чтобы его открыть.

1234
0936

6

Несколько клонов находятся на поле размером `N\ times\ M`, на котором есть некоторое количество препятствий. Клонам необходимо переместиться в новые позиции. Все клоны могут двигаться одновременно, но в каждой клетке может находиться только один клон. Раз в секунду каждый клон может либо перейти в соседнюю клетку, имеющую общую сторону с клеткой, на которой он находится, либо остаться на месте.

Требуется найти способ перемещения клонов за минимальное время в новую позицию. Если существует несколько вариантов с минимальным временем, то нужно найти вариант с минимальным суммарным количеством перемещений клонов.

Первая строка содержит два целых числа `N` и `M` (`1\ ≤\ N,\ M\ ≤\ 15`) – размеры поля. Далее следует `N` строк, содержащих по `M` символов. Символ '#' обозначает клетку с препятствием, '.' – пустую клетку, 'S' – начальную позицию какого-либо клона, 'E' – пустую клетку, конечную позицию для клона. Гарантируется, что клоны могут пройти от начальной позиции до конечной (все связные области содержат одинаковое количество символов 'S' и 'E').

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

3 3
S#.
S..
#EE

3 6

3 5
SSSSS
##.##
EEEEE

6 22

C-3PO кроме простых чисел и совсем простых чисел, может применять еще несложные числа – числа, в разложении которых на простые множители каждый простой множитель встречается не более одного раза.

Подсчитайте количество несложных чисел в диапазоне от `A` до `B`.

Ввод содержит два целых числа `A` и `B` (`2\ ≤\ A\ ≤\ B\ ≤\ 10^{12}`), задающих диапазон.

Вывести одно целое число – количество несложных чисел в заданном диапазоне.

2 11

7

Принцесса Лея намерена отправить R2-D2 с просьбой о помощи на планету Татуин, но R2-D2 не хочет участвовать в столь опасной миссии и пытается от нее всячески ускользнуть. Принцесса и робот перемещаются в помещении трюма корабля по точкам с целыми координатами. Принцесса и робот ходят по очереди, первый ход делает принцесса. При очередном ходе принцесса или робот должны переместиться в соседнюю точку на единичном расстоянии. В точке с координатами (0,0) находится дверь, но она заперта и попасть в эту точку нельзя. Из точки (0,1) можно за 1 ход попасть в точку (1,0) и наоборот. Робот считается пойманным, если после очередного хода принцессы или робота координаты совпадут.

Напишите программу, которая поможет принцессе поймать робота.

Протокол взаимодействия При старте программа получает в первой строка ввода четыре целых числа: начальные координаты принцессы `X_P`, `Y_P` (`0\ ≤\ X_P,\ Y_P\ ≤\ 9`) и начальные координаты робота `X_R`, `Y_R` (`0\ ≤\ X_R,\ Y_R\ ≤\ 9`). Программа должна вывести новые координаты принцессы. После вывода хода программа должна сделать принудительную запись буфера вывода (в C++ это делает endl, в C нужно использовать fflush(stdout), в Pascal – flush(output)). После этого программа получает новые координаты робота и может сделать очередной ход. При совпадении координат принцессы и робота программа должна завершить выполнение программы. Если программа не сможет поймать робота за 100 ходов принцессы, то программа получает вердикт "Неверный ответ".

5 5 8 7
8 6
9 6
9 7
9 8
9 9
8 9

6 5
7 5
8 5
8 6
8 7
8 8
8 9

В пиццерии предлагается `N` топпингов для начинки пиццы. По мнению Люка в начинке хорошей пиццы должно быть ровно `M` ингредиентов, при этом номера этих ингредиентов должны отличаться не больше чем на `K`, иначе они будут плохо сочетаться между собой.

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

Первая строка ввода содержит три целых числа: общее количество топпингов `N` (`3\ ≤\ N\ ≤\ 1000`), количество ингредиентов для начинки `M` (`1\ ≤\ M\ ≤\ min(10,N)`), максимальная разница между номерами ингредиентов `K` (`M-1\ ≤\ K\ ≤\ 20`).

В первой строке вывести одно целое число – количество различных вариантов начинок для пиццы.

4 2 2

5