Подразделы

Другие разделы

Дата и время

29/03/2024 13:59:03

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

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

print1. Пробуждение Силы

Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

33691.png
Курсанты академии джедаев часто сбегают в самоволку, перепрыгивая забор с помощью Силы. Такой прыжок имеет форму равнобедренного треугольника со сторонами равными `L`. Чтобы курсанты не могли самовольно покидать академию, мастер Йода решил устроить болото перед забором, но ему необходимо вычислить максимальную ширину болота, которую могут перескочить курсанты при прыжке через забор.
Формат ввода
Первая строка ввода содержит два целых числа: длина прыжка `L` и высота забора `H` (`1\ ≤\ H\ <\ L\ ≤\ 1000`).
Формат вывода
Вывести одно число – максимальную ширину болота, которую могут перепрыгнуть курсанты с точностью `10^{-8}`.

Пример ввода

5 2

Пример вывода

5.33757024

print2. Шоу

Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

За свой блестящий внешний вид и хорошо подвешенный язык 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

print3. Quite prime numbers

Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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.
Input
First line contains one integer `N` (`2\ ≤\ N\ ≤\ 10^{12}`).
Output
Program should print YES, if `N` is a quite prime, and NO otherwise.

Sample Input #1

31

Sample Output #1

NO

Sample Input #2

29

Sample Output #2

YES

print4. Скрытая угроза

Ограничения: время – 2500ms/5000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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

print5. Multigram

Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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.
Input
The first and only line of input contains a word of length at most 300000 lowercase English characters.
Output
If the given word is not a multigram, output "No solution". Otherwise, output the shortest root of the given word in one line.

Sample Input #1

aaaa

Sample Output #1

a

Sample Input #2

ab

Sample Output #2

No solution

Sample Input #3

bbabab

Sample Output #3

bba
Clarification of the first example: Notice that the word "aa" could also be the root, but "a" is shorter.
Clarification of the second example: The word is not a multigram because "a" and "b" are not mutually anagrams.

print6. Золотая система счисления

Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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

print7. Замок

Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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

Пример ввода

1234
0936

Пример вывода

6

print8. Атака клонов

Ограничения: время – 4000ms/8000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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

Пример ввода #1

3 3
S#.
S..
#EE

Пример вывода #1

3 6

Пример ввода #2

3 5
SSSSS
##.##
EEEEE

Пример вывода #2

6 22

print9. Несложные числа

Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

C-3PO кроме простых чисел и совсем простых чисел, может применять еще несложные числа – числа, в разложении которых на простые множители каждый простой множитель встречается не более одного раза.
Подсчитайте количество несложных чисел в диапазоне от `A` до `B`.
Формат ввода
Ввод содержит два целых числа `A` и `B` (`2\ ≤\ A\ ≤\ B\ ≤\ 10^{12}`), задающих диапазон.
Формат вывода
Вывести одно целое число – количество несложных чисел в заданном диапазоне.

Пример ввода

2 11

Пример вывода

7

print10. Новая надежда

Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: интерактивная задача Вывод: интерактивная задача copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

33717.png
Принцесса Лея намерена отправить 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

print11. Пицца

Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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

Пример ввода

4 2 2

Пример вывода

5
Пояснение к примеру: можно сделать следующие начинки: {1,2}, {1,3}, {2,3}, {2,4}, {3,4}.
loading