Задачи командных соревнований PRIME TIME 2022
1. Into a prime number
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Given a number `N`.
You have to replace the least amount of digits in the number to get a prime number.
The first line contains a single integer `N` (`1 <= N < 10^9`).
Output the prime number obtained after replacing the digits.
If there are multiple solutions with the same number of digit replacements, print the smallest prime number of them.
```sample Sample Input 1
5
```
```sample Sample Output 1
5
```
```sample Sample Input 2
93
```
```sample Sample Output 2
13
```
2. Делёж
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
У вас есть коробка, в которой `N` печений.
Вы хотите разделить печенье среди `M` друзей так, чтобы каждому досталось хотя бы одно печенье, и не было двух (или более) друзей,
которым бы досталось одинаковое количество печений.
Первая строка ввода содержит одно целое число `T` (`1<= T <= 100`) -- количество тестов. Далее следует `T` строк,
в каждой строке содержатся два целых числа -- количество печений `N` (`1 <= N < 10^9`) и количество друзей `M` (`1 <= M < 10^5`).
Для каждого теста вывести строку, содержащую ``YES``, если такое разделение возможно, иначе вывести ``NO``.
```sample Пример ввода
3
42 6
5 6
909 10
```
```sample Пример вывода
YES
NO
YES
```
3. Изменение последовательности
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Дана последовательность из `N` элементов `A_1, A_2, ..., A_N`.
Необходимо изменить последовательность таким образом, чтобы выполнялось `A_i != i` для всех
`i` от 1 до `N`.
Для изменения последовательности применяется следующая операция:
Выбирается некоторый элемент последовательности и перед ним вставляется число 0. Например, после вставки 0 перед 3-м элементом из
последовательности [3,2,4,2] получается последовательность [3,2,0,4,2].
Первая строка ввода содержит одно целое число `N` (`1<= N <= 10^5`) -- начальное количество элементов в последовательности.
Вторая строка ввода `N` целых чисел в диапазоне от 1 до `10^6` -- элементы последовательности.
Вывести одно целое число -- минимальное количество операций для изменения последовательности.
```sample Пример ввода
4
3 2 4 2
```
```sample Пример вывода
2
```
Можно вставить 0 перед 1-м элементом, получив последовательность [0,3,2,4,2],
а затем перед 4-м элементом последовательности, получив [0,3,2,0,4,2].
4. Самая длинная молекула
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
В химическом реакторе находится `N` элементов.
На каждом шаге в реакторе выбирается два элемента, еще не включенные в один кусочек молекулы,
и они соединяются связью некоторой длины.
Можно прервать процесс и соединить кусочки молекулы в одну, но при этом длина связи между соединяемыми элементами будет равна 0.
Напишите программу, которая определяет максимальную длину молекулы (максимальное расстояние между элементами в молекуле).
Первая строка ввода содержит одно целое число `N` (`1<= N <= 10^4`) -- количество элементов в реакторе.
Далее следует `(N-1)` строка, каждая из которых содержит три целых числа -- номера соединяемых элементов от 1 до `N` и длина связи от 1 до 10.
Вывести два целых числа -- максимальную длину молекулы и номер шага, после которого можно её получить. Если существует несколько вариантов для шага, то вывести минимальный из них.
```sample Пример ввода
6
1 2 2
2 3 3
4 5 2
6 5 3
2 5 1
```
```sample Пример вывода
10 4
```
5. Manhattan distance
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Manhattan distance is the minimum number of moves required to reach `P_2 (x_2,y_2)`
from `P_1 (x1,y1)` if, in each move, you are allowed to travel one unit along the X-axis or one unit along the Y-axis.
Manhattan distance can be calculated by the formula `d(P_1,P_2)=|x_2 - x_1|+|y_2 - y_1|`.
You are given an integer `D`. Find four points `P_1, P_2, P_3, P_4`
with integer coordinates, such that The manhattan distance between any pair of points is `D`. More formally, `d(P_i,P_j)=D` for all `1<=i<j<=4`.
The first line contains a single integer, `D` (`1 <= D <= 10^5`).
If such set of points do not exist, print in a single line the integer `-1`.
Otherwise print 4 lines. The `i`th line, should contain two space separated integers, `X_i Y_i`, the coordinates of the point `P_i`,
such that `-10^9<= X_i, Y_i <= 10^9`.
If there are multiple solutions, you may print any.
Note: It is guaranteed that whenever there exists a solution, there exists one in which all points have coordinates with absolute values not more than `10^9`.
```sample Sample Input 1
2
```
```sample Sample Output 1
0 1
1 0
1 2
2 1
```
```sample Sample Input 2
1
```
```sample Sample Output 2
-1
```
6. Игра в камешки
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Двое играют в следующую игру с помощью камней черного и белого цвета.
Камни выстраиваются в цепочку. Игроки ходят по очереди, беря по одному камню с любого края цепочки.
Игра заканчивается, когда камней не остается.
Выигрывает игрок, получивший больше белых камней.
Напишите программу, которая определяет выигрывающего игрока при оптимальной игре обоих для заданной начальной цепочки камней.
Первая строка ввода содержит последовательность символов ``B`` (чёрный камень) и ``W`` (белый камень) длиной от 1 до 1000 -- начальная цепочка камней.
Вывести одно целое число -- 1, если выигрывает игрок, делающий первый ход, или 2, если выигрывает второй, или 0, если получается ничья.
```sample Пример ввода 1
BWB
```
```sample Пример вывода 1
2
```
```sample Пример ввода 2
BW
```
```sample Пример вывода 2
1
```
7. Гирлянда
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Гирлянда считается красивой, если количество ламп для разных цветов одинаково или все лампы имеют один цвет.
В старой гирлянде перегорели некоторые лампы, и теперь количество ламп разных цветов может не совпадать.
Можно убрать из неё еще несколько ламп, чтобы гирлянда стала красивой.
Определите минимальное количество выкрученных ламп для достижения указанной цели.
Первая строка ввода содержит два целых числа -- количество работающих ламп в гирлянде `N` (`1<= N <= 10^5`) и количество различных цветов
`K` (`1<= K <= 10^5`).
Вторая строка ввода содержит `N` целых чисел в диапазоне от 1 до `K` -- цвета работающих ламп в гирлянде.
Вывести одно целое число -- минимальное количество выкрученных ламп, чтобы лампы всех оставшихся цветов были в одинаковом количестве.
```sample Пример ввода
10 5
3 2 4 2 3 5 3 3 4 2
```
```sample Пример вывода
4
```
Можно выкрутить, например, 1 лампу цвета 3, 2 лампы цвета 4 и 1 лампу цвета 5. Останется по 3 лампы цвета 2 и 3.
Новая гирлянда содержала лампы пяти цветов, но все лампы цвета 1 перегорели, поэтому среди цветов работающих ламп нет 1.
8. Телетайп
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Телетайп может передавать только прописные латинские буквы.
При этом телетайп может переставить буквы слова в случайном порядке. Например, при передаче
слова TEXT приемное устройство может получить XTTE или ETXT или XETT и т.д.
К счастью, меняется только порядок, и буквы не заменяются на другие и не исчезают.
Напишите программу, которая кодирует слова длиной от 1 до 32 букв так, что их можно будет декодировать в приемном устройстве, и программу
для их декодирования. Длина кодирующей последовательности не должна превышать 1000.
Первая строка ввода содержит два целых числа -- количество передаваемых слов `N` (`1 <= N <= 1000`) и
флаг 0 (передача) или 1 (приём).
Далее следует `N` строк, содержащих последовательности из прописных латинских букв.
При передаче указываются слова длиной от 1 до 32.
Для проверки приёма программе даются закодированные ею же строки с переставленными буквами.
Для каждого слова из ввода вывести кодирующее его слово в случае передачи или переданное слово в случае приёма.
```sample Пример ввода 1
3 0
ABC
CAB
E
```
```sample Пример вывода 1
ABBCCC
AAABCC
AAAAA
```
```sample Пример ввода 2
3 1
ABBCCC
AAABCC
AAAAA
```
```sample Пример вывода 2
ABC
CAB
E
```
Программа запускается дважды, сначала с 0, а потом с 1, где в качестве строк используется ваш вывод, в котором переставлены буквы. После второго запуска на выходе должны быть строки из начального ввода.
9. Игра в классики
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Для получения приза нужно победить в следующей модификации игры в классики.
Игра проходит на прямоугольном поле из `N xx M` клеток.
При прыжке в клетку она меняет цвет с черного на белый и наоборот.
Некоторые клетки на поле первоначально имеют черный цвет.
Цель игры -- пропрыгать из начальной клетки A в конечную клетку B
так, чтобы после завершения прыжков все клетки стали белыми.
Начальная и конечная клетки белые и не меняют цвет при прыжке в них.
Любую клетку можно проходить несколько раз, включая начальную и конечную.
Найдите последовательность прыжков, которая позволит достичь цели игры.
При этом не требуется минимизировать количество прыжков.
Первая строка ввода содержит два целых числа -- размеры поля `N` и `M` (`2<= N, M <= 10`).
Далее следует `N` строк, содержащих по `M` символов. Символ '``.``' означает белую клетку,
символ '``#``' -- черную, символ '``A``' -- начальную позицию, символ '``B``' -- конечную позицию.
Гарантируется, что на поле будет ровно один символ ``A`` и один символ ``B``.
Вывести в первой строке последовательность прыжков.
Использовать следующие обозначения для прыжков: ``N`` -- прыжок на соседнюю клетку в северном направлении (вверх),
``S`` -- на юг (вниз), ``E`` -- на восток (вправо), ``W`` -- на запад (влево)
Можно вывести любой вариант, но количество прыжков не должно превышать 2000.
```sample Пример ввода
2 3
..#
A#B
```
```sample Пример вывода
EENS
```
10. Гиперкуб
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: интерактивная задача Вывод: интерактивная задача
Послать решение Blockly Посылки Темы Где Обсудить (0)
Гиперкуб состоит из 8 кубов, соединенных случайным образом с помощью 6 двухсторонних переходов в гранях кубов. Гарантируется, что из любого куба можно попасть в любой другой куб.
Первоначально робот, которым управляет ваша программа, находится в кубе номер 1,
который отличается по цвету от остальных кубов.
Можно выбрать один из 6 переходов. После перехода робот получает информацию о номере перехода,
через который он оказался в новом кубе. Также робот получает информацию о том, является ли этот куб кубом номер 1.
Цель робота определить, в какие кубы ведут все переходы в каждом из 8 кубов, сделав не более 1000 перемещений
из одного куба в другой.
*Протокол взаимодействия*
Программа должна вывести строку, содержащую число от 1 до 6 -- номер перехода.
В ответ программа получает число от 1 до 6 -- номере перехода,
через который он оказался в новом кубе.
Когда информация о всех переходах будет установлена, программа должна вывести число 0, а затем 8 строк
по 6 целых чисел от 1 до 8 в каждой строке. `j`-е в строке означает номер куба, в который ведет `j`-й переход.
`i`-я строка соответствует `i`-му кубу. Нумерация кубов может быть любой, кроме куба номер 1.
```sample Пример вывода
1
2
2
0
2 3 4 5 6 7
3 1 4 5 6 7
8 5 2 1 7 3
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
```
```sample Пример ввода
2 0
1 1
4 0
```
Выйдя из куба 1 через переход 1 робот попадает в куб 2 через переход 2, затем возвращается через переход 2 в куб 1 через переход 1.
Затем через переход 2 робот попадает в другой куб через переход 4. Возможно это снова куб 2.
Далее показан пример вывода результатов.
11. Удаление буквы
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Рассмотрим строку ``ABBC``.
Удаляя из неё ровно одну букву, можно получить следующие *различные* строки ``ABB``, ``ABC`` и ``BBC``.
Дана строка `S`. Найдите количество *различных* строк, которые можно получить из части
строки `S` с `i`-го по `j`-й символ включительно.
Первая строка ввода содержит непустую строку `S` (`2 <= |S| <= 10^6`),
состоящую из прописных латинских букв.
Вторая строка ввода содержит одно целое число `N` (`1 <= N <= 10^4`) - количество запросов.
Далее следует `N` строк, каждая строка содержит два целых числа `i` и `j` (`1 <= i < j <= |S|`).
Для каждого запроса вывести одно целое число на отдельной строке -- количество *различных* строк, которые можно получить из части
строки `S` с `i`-го по `j`-й символ включительно.
```sample Пример ввода
ABBCCC
3
1 4
4 6
1 2
```
```sample Пример вывода
3
1
2
```
Начало
Соревнования
Простые числа, разложение на множители