Задачи командных соревнований PRIME TIME 2023
1. Spell Combos
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Basic Cast reduces enemy health by 1, while Diffindo take away the smallest prime factor of current enemy health.
Determine the minimum length of a sequence of spells after which the enemy's health will become 0.
The first line contains a single integer `N` (`1 <= N < 10^9`) -- the enemy's health.
Output the the minimum length of spell combo.
```sample Sample Input 1
5
```
```sample Sample Output 1
1
```
```sample Sample Input 2
10
```
```sample Sample Output 2
3
```
Use Diffindo (10-2=8), Basic Cast (8-1=7), and Diffindo again (7-7=0).
2. Распределение студентов
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
В начале учебного года каждый студент Хогвартса может выбрать дополнительных 5 предметов, которые он хотел бы изучать.
Но так как есть ограничение на количество студентов на занятии, то не все пожелания студентов могут быть учтены.
Распределяющая Шляпа должна записать каждого студента на как можно большее из 5 выбранных им предметов,
соблюдая ограничения на количество. Определим уровень "счастья" студента как количество выбранных предметов, на которые он был зачислен.
Вычислите какой максимум суммы уровней счастья по всем студентам может получить Распределяющая Шляпа.
Первая строка ввода содержит два целых числа, разделенных пробелом, количество предметов `P` (`5 <= P <= 1000`) и
количество студентов `S` (`1 <= S <= 10000`). Далее следуют `P` строк, каждая строка содержит одно
целое число `M_i` (`1 <= M_i <= 10000`) -- максимальное количество студентов, которых можно записать на `i`-й предмет.
Далее следуют еще `S` строк, по одной на каждого студента, содержащих по пять различных целых чисел в диапазоне от 1 до `P` --
номера предметов, которые студент хотел бы изучать.
Вывести единственное целое число -- максимальную сумму уровней счастья.
```sample Пример ввода
6 3
1
2
3
1
1
5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 6
```
```sample Пример вывода
9
```
3. Алохомора 1
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
 Опытный волшебник, знающий заклинание Алохомора, может легко разбогатеть.
Механизм всех замков в Хогвартсе состоит из двух дисков, в каждом из которых есть прорези и выступы.
Для отпирания замка нужно ключом или заклинанием повернуть внутренний диск так, чтобы его прорези
были напротив выступов внешнего диска, а выступы -- напротив прорезей.
Первая строка ввода описывает внешний диск, вторая -- внутренний.
Обе строки имеют одинаковую длину `L` от 1 до 1000 и состоят из символов 0 и 1, где
0 означает прорезь, а 1 -- выступ. Положение прорезей и выступов указано по часовой стрелке.
Гарантируется, что существует такой способ повернуть внутренний диск, чтобы замок открылся.
Вывести единственное целое число от 0 до `L-1` -- минимальное количество поворотов по часовой стрелке на 1 позицию для открытия замка.
```sample Пример ввода (см. рисунок)
01001110
10001101
```
```sample Пример вывода
3
```
4. Трансфигурация
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Среди студентов Хогвартса популярна следующая игра.
Игрок получает несколько карточек с буквами от A до Z
и может несколько букв с помощью трасфигурации превратить в другие,
но не более `K` букв. Затем он подсчитывает очки.
За каждую букву от A до Z игрок получает количество очков, равное квадрату их количества.
Игрок получает дополнительные очки за количество слов "PRIME", которые он может выложить
из своих карточек. Дополнительные очки рассчитываются как квадрат количества таких слов,
умноженный на `M`.
Определите максимальное количество очков, которые игрок может получить.
Первая строка ввода содержит два целых числа -- ограничение на количество трансфигураций `K` (`0 <= K <= 10000`)
и множитель для дополнительных очков `M` (`1 <= M <= 1000`). Вторая строка ввода
содержит от 1 до 10000 прописных латинских букв от A до Z -- буквы на карточках.
Вывести одно целое число -- максимальное количество очков.
```sample Пример ввода 1
1 10
PRIMERAAAAA
```
```sample Пример вывода 1
51
```
```sample Пример ввода 2
6 100
PRIMERAAAAA
```
```sample Пример вывода 2
425
```
Пояснение к примеру: После трансфигурации 5 букв получаем PRIMERIMEPR `100*2^2` (PRIME) `+2^2` (P) `+3^2` (R) `+2^2` (I) `+2^2` (M) `+2^2` (E)=425
5. Dueling Club
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Astoria Crickett, Bella Jenkins, and Constance Dagworth reached the final of the club tournament.
To determine the winner, each player must fight with others. Each pair of players fight exactly once.
The fights are held by lot in random order.
Let the initial mana of the players be `X` and `Y`, then, after the fight, the mana of both the players reduces by `min(X,Y)`.
The winner is the one who will have non-zero mana after three fights.
Determine if Astoria can win the tournament.
The first line of input contains three space-separated integers
`A`, `B`, and `C` (`1 <= A, B, C <= 1000`) -- the initial mana of Astoria, Bella, and Constance respectively.
Print "Sure" if Astoria wins regardless of the order of the fights,
print "Maybe" if there is an order of fights in which Astoria will win,
otherwise print "Never".
```sample Sample input #1
5 1 4
```
```sample Sample output #1
Maybe
```
Explanation: Constance defeats Bella, then Astoria defeats Bella and Constance,
she has 2 mana remaining. If the order of fights is Astoria-Constance, Astoria-Bella, Bella-Constance, then
Astoria will have 0 mana.
```sample Sample input #2
5 1 1
```
```sample Sample output #2
Sure
```
```sample Sample input #3
1 2 4
```
```sample Sample output #3
Never
```
6. Нумерология
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
В магловском домино на половинках каждой из костей расположены числа от 0 до 6, и каждая пара чисел встречается в наборе ровно 1 раз.
А маги-нумерологи используют наборы волшебного домино с числами от 0 до `N`. Например, для `N=2` набор
состоит из 6 костей: 0-0, 0-1, 0-2, 1-1, 1-2, 2-2.
Чтобы открыть запечатанную дверь в кабинете нумерологии, перед ней нужно выложить в цепочку набор
волшебного домино (по обычным магловским правилам: соседние половинки совпадают).
Причем суммы чисел на костях должны совпасть с числами, записанными на двери.
Сможете ли вы проникнуть в таинственную запечатанную комнату?
Первая строка ввода содержит целое число 'N' (максимальное число на костях, `1 <= N <= 10^3`).
Вторая строка содержит `M = (N+1)(N+2)//2` целых чисел -- требуемые суммы на каждой из костей в порядке их выкладки в цепочке.
Выведите `M` строк, по 2 целых числа на каждой: числа на костях в порядке, соответствующем порядку входных сумм.
Половинка, ближайшая к началу цепочки, должна выводиться первой. Гарантируется, что хотя бы одно решение существует.
Можно вывести любую подходящую последовательность.
```sample Пример ввода
2
2 3 4 2 0 1
```
```sample Пример вывода
1 1
1 2
2 2
2 0
0 0
0 1
```
7. Горный тролль
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Против горного тролля действуют только воспламеняющие заклинания Инсендио и Конфринго.
Каждое из этих заклинаний наносит троллю фиксированный урон, но требуется
время перед их повторным применением.
Если Инсендио наносит урон 10 с откатом 2 секунды, а Конфринго -- урон 25 с откатом 3 секунды, то
для уничтожения тролля с уровнем здоровьем 100 нужно 6 секунд.
В момент `t=0` можно нанести урон 35 (10+25), применив оба заклинания, затем в момент `t=2` можно снова применить Инсендио (10),
а в момент `t=3` -- Конфринго (25), в `t=4` будет сново готово к применению Инсендио, и в
момент `t=6` тролля можно добить, применив оба заклинания.
Первая строка ввода содержит пять целых чисел -- уровень здоровья тролля `H` (`1 <= H <= 10^9`),
урон `X_1` и время отката `Y_1` для заклинания Инсендио,
урон `X_2` и время отката `Y_2` для заклинания Конфринго (`1 <= X_1 <= X_2 <= 10^9`, `1 <= Y_1 <= Y_2 <= 10`)
Вывести одно целое число -- минимальное время для победы над троллем, если заклинания применяются сразу после их отката.
```sample Пример ввода
100 10 2 25 3
```
```sample Пример вывода
6
```
Результат вычислений может быть больше `2^31`, поэтому используйте тип int64_t или double.
8. Зельеделие
Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Профессор зельеделия Эзоп Шарп страдает от бессонницы и вынужден каждый день готовить себе сонное зелье.
Сила зелья равна сумме сил добавленных в него ингредиентов и должна быть не меньше `L` (чтобы заснуть вечером), но и не
больше `U` (чтобы вовремя проснуться утром).
К счастью, в кладовой Хогвартса найдутся в изобилии ингредиенты с любой силой от 1 до `10^5`, причем любые 2 разных вида ингредиентов
имеют разную силу.
Во избежание побочных эффектов от передозировки, один и тот же ингредиент нельзя добавлять в одно зелье более чем дважды.
К сожалению, зелья вызывают привыкание: если выпить зелье с тем же составом ещё раз, оно не подействует.
Сколько же дней профессор Шарп сможет справляться с бессоницей?
Если число слишком большое, достаточно найти остаток от его деления на `10^9+9`.
В единственной строке ввода содержатся два целых числа `L` и `U` (`1 <= L <= U <= 10^5`) -- минимальная и максимальная сила зелья.
Вывести одно целое число -- остаток от деления количества подходящих сонных зелий на `10^9+9`.
```sample Пример ввода
3 4
```
```sample Пример вывода
6
```
Пояснение к примеру: Можно составить два зелья силы 3: из одного ингредиента силы 3, либо двух ингредиентов с силами 1 и 2.
Также можно составить четыре зелья силы 4 из таких наборов ингредиентов: 4; 1+3; 1+1+2; 2+2.
Зелья 1+1+1 и 1+1+1+1 использовать нельзя из-за передозировки ингредиента с силой 1.
9. Флипендо
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
После демонстрации заклинания Флипендо профессор Мирабель Чесноук выдала вам для тренировки последовательность из открывающихся и закрывающихся скобок и
предложила превратить её в правильную. Правильная скобочная последовательность (ПСП) определяется следующим образом:
* пустая строка является ПСП;
* если `S` -- ПСП, тогда `(S)` тоже ПСП;
* если `S_1` и `S_2` -- ПСП, тогда `S_1 S_2` является ПСП.
Заклинание Флипендо можно применить к любому символу строки и превратить открывающуюся скобку в закрывающуюся, а закрывающуюся -- в открывающуюся.
Вы хотите выполнить порученную задачу за наименьшее количество действий, чтобы перейти к другим, более интересным квестам.
Ввод содержит строку из символов '(' и ')' длиной `L` (`2 <= L <= 10^5`, `L` четное число).
В первой строке вывести одно целое число `N` -- минимальное количество применений заклинаний Флипендо.
Далее вывести `N` строк, содержащих по одному целому числу от 1 до `L` -- номера символов в строке,
к которым нужно применить Флипендо. Можно вывести номера в любом порядке.
```sample Пример ввода
)(())(((
```
```sample Пример вывода
3
1
6
8
```
После переворачиваний получится строка "((()))()".
10. Дьявольские силки
Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Весь пол в потайном коридоре травологии покрыт "дьявольскими силками", мешающими пройти мимо и добыть лист гиганской тентакулы.
К счастью, в коридоре есть несколько светильников, которые можно зажечь с помощью заклинания "Инсендио". Каждый из них освещает пол
в радиусе `R` вокруг себя, полностью очищая освещенную область от "дьявольских силков".
Какова общая площадь освещенной части пола?
В первой строке ввода четыре целых числа --
длина `L` и ширина `W` коридора (`1 <= L,W <= 100`), количество светильников `N` (`1 <= N <= 10`) и радиус их действия `R` (`1 <= R <= 100`).
Затем идут `N` строк, по 2 целых числа в каждой, задающие координаты светильников: `X_i` (`0 <= X_i <= L`) и `Y_i` (`0 <= Y_i <= W`).
Выведите одно вещественное число -- площадь освещенной части пола. *Относительная погрешность* ответа не должна превышать `10^{-6}`.
```sample Пример ввода
10 10 1 1
5 5
```
```sample Пример вывода
3.141593
```
11. Хранилище Древней магии
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Гоблин Ранрок хочет добраться до хранилища с Древней магией,
но магический бур, который он использует для прокладки туннеля в хранилище может пробурить ограниченное
количество прямых участков туннеля и участков с поворотом.
Хранилище находится в клетке (0,0), бур в шахте в клетке `(X,Y)`.
Хранилище и шахта занимают всю клетку, поэтому можно начинать и заканчивать туннель с любой стороны этих клеток.
Определите, сможет ли Ранрок добраться до хранилища.
В первой строке ввода находятся 4 числа -- координаты клетки с шахтой `X, Y` (`-10^9 <= X, Y <= 10^9`, `(X,Y)!=(0,0)`), где находится магический бур,
количество поворотов `T` и прямых участков `L` (`0 <= T, L <=10^9`), которые может сделать бур.
Вывести "Yes", если прокладка туннеля до хранилища возможна, иначе вывести "No".
```sample Пример ввода 1
-6 4 3 6
```
```sample Пример вывода 1
Yes
```
```sample Пример ввода 1
6 4 1 7
```
```sample Пример вывода 1
No
```
Начало
Соревнования
Простые числа, разложение на множители