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

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.

5

5

93

13

У вас есть коробка, в которой `N` печений. Вы хотите разделить печенье среди `M` друзей так, чтобы каждому досталось хотя бы одно печенье, и не было двух (или более) друзей, которым бы досталось одинаковое количество печений.

Первая строка ввода содержит одно целое число `T` (`1<= T <= 100`) – количество тестов. Далее следует `T` строк, в каждой строке содержатся два целых числа – количество печений `N` (`1 <= N < 10^9`) и количество друзей `M` (`1 <= M < 10^5`).

Для каждого теста вывести строку, содержащую YES, если такое разделение возможно, иначе вывести NO.

3
42 6
5 6
909 10

YES
NO
YES

Дана последовательность из `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` – элементы последовательности.

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

4
3 2 4 2

2

Можно вставить 0 перед 1-м элементом, получив последовательность [0,3,2,4,2], а затем перед 4-м элементом последовательности, получив [0,3,2,0,4,2].

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

Напишите программу, которая определяет максимальную длину молекулы (максимальное расстояние между элементами в молекуле).

Первая строка ввода содержит одно целое число `N` (`1<= N <= 10^4`) – количество элементов в реакторе. Далее следует `(N-1)` строка, каждая из которых содержит три целых числа – номера соединяемых элементов от 1 до `N` и длина связи от 1 до 10.

Вывести два целых числа – максимальную длину молекулы и номер шага, после которого можно её получить. Если существует несколько вариантов для шага, то вывести минимальный из них.

6
1 2 2
2 3 3
4 5 2
6 5 3
2 5 1

10 4

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`.

2

0 1
1 0
1 2
2 1

1

-1

Двое играют в следующую игру с помощью камней черного и белого цвета. Камни выстраиваются в цепочку. Игроки ходят по очереди, беря по одному камню с любого края цепочки. Игра заканчивается, когда камней не остается. Выигрывает игрок, получивший больше белых камней.

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

Первая строка ввода содержит последовательность символов B (чёрный камень) и W (белый камень) длиной от 1 до 1000 – начальная цепочка камней.

Вывести одно целое число – 1, если выигрывает игрок, делающий первый ход, или 2, если выигрывает второй, или 0, если получается ничья.

BWB

2

BW

1

Гирлянда считается красивой, если количество ламп для разных цветов одинаково или все лампы имеют один цвет. В старой гирлянде перегорели некоторые лампы, и теперь количество ламп разных цветов может не совпадать. Можно убрать из неё еще несколько ламп, чтобы гирлянда стала красивой.

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

Первая строка ввода содержит два целых числа – количество работающих ламп в гирлянде `N` (`1<= N <= 10^5`) и количество различных цветов `K` (`1<= K <= 10^5`). Вторая строка ввода содержит `N` целых чисел в диапазоне от 1 до `K` – цвета работающих ламп в гирлянде.

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

10 5
3 2 4 2 3 5 3 3 4 2

4

Можно выкрутить, например, 1 лампу цвета 3, 2 лампы цвета 4 и 1 лампу цвета 5. Останется по 3 лампы цвета 2 и 3.

Новая гирлянда содержала лампы пяти цветов, но все лампы цвета 1 перегорели, поэтому среди цветов работающих ламп нет 1.

Телетайп может передавать только прописные латинские буквы. При этом телетайп может переставить буквы слова в случайном порядке. Например, при передаче слова TEXT приемное устройство может получить XTTE или ETXT или XETT и т.д. К счастью, меняется только порядок, и буквы не заменяются на другие и не исчезают.

Напишите программу, которая кодирует слова длиной от 1 до 32 букв так, что их можно будет декодировать в приемном устройстве, и программу для их декодирования. Длина кодирующей последовательности не должна превышать 1000.

Первая строка ввода содержит два целых числа – количество передаваемых слов `N` (`1 <= N <= 1000`) и флаг 0 (передача) или 1 (приём). Далее следует `N` строк, содержащих последовательности из прописных латинских букв. При передаче указываются слова длиной от 1 до 32. Для проверки приёма программе даются закодированные ею же строки с переставленными буквами.

Для каждого слова из ввода вывести кодирующее его слово в случае передачи или переданное слово в случае приёма.

3 0
ABC
CAB
E

ABBCCC
AAABCC
AAAAA

3 1
ABBCCC
AAABCC
AAAAA

ABC
CAB
E

Программа запускается дважды, сначала с 0, а потом с 1, где в качестве строк используется ваш вывод, в котором переставлены буквы. После второго запуска на выходе должны быть строки из начального ввода.

Для получения приза нужно победить в следующей модификации игры в классики. Игра проходит на прямоугольном поле из `N xx M` клеток. При прыжке в клетку она меняет цвет с черного на белый и наоборот. Некоторые клетки на поле первоначально имеют черный цвет. Цель игры – пропрыгать из начальной клетки A в конечную клетку B так, чтобы после завершения прыжков все клетки стали белыми. Начальная и конечная клетки белые и не меняют цвет при прыжке в них. Любую клетку можно проходить несколько раз, включая начальную и конечную.

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

Первая строка ввода содержит два целых числа – размеры поля `N` и `M` (`2<= N, M <= 10`). Далее следует `N` строк, содержащих по `M` символов. Символ '.' означает белую клетку, символ '#' – черную, символ 'A' – начальную позицию, символ 'B' – конечную позицию. Гарантируется, что на поле будет ровно один символ A и один символ B.

Вывести в первой строке последовательность прыжков. Использовать следующие обозначения для прыжков: N – прыжок на соседнюю клетку в северном направлении (вверх), S – на юг (вниз), E – на восток (вправо), W – на запад (влево) Можно вывести любой вариант, но количество прыжков не должно превышать 2000.

2 3
..#
A#B

EENS

Гиперкуб состоит из 8 кубов, соединенных случайным образом с помощью 6 двухсторонних переходов в гранях кубов. Гарантируется, что из любого куба можно попасть в любой другой куб.

Первоначально робот, которым управляет ваша программа, находится в кубе номер 1, который отличается по цвету от остальных кубов. Можно выбрать один из 6 переходов. После перехода робот получает информацию о номере перехода, через который он оказался в новом кубе. Также робот получает информацию о том, является ли этот куб кубом номер 1.

Цель робота определить, в какие кубы ведут все переходы в каждом из 8 кубов, сделав не более 1000 перемещений из одного куба в другой.

Протокол взаимодействия

Программа должна вывести строку, содержащую число от 1 до 6 – номер перехода. В ответ программа получает число от 1 до 6 – номере перехода, через который он оказался в новом кубе.

Когда информация о всех переходах будет установлена, программа должна вывести число 0, а затем 8 строк по 6 целых чисел от 1 до 8 в каждой строке. `j`-е в строке означает номер куба, в который ведет `j`-й переход. `i`-я строка соответствует `i`-му кубу. Нумерация кубов может быть любой, кроме куба номер 1.

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

2 0
1 1
4 0

Выйдя из куба 1 через переход 1 робот попадает в куб 2 через переход 2, затем возвращается через переход 2 в куб 1 через переход 1. Затем через переход 2 робот попадает в другой куб через переход 4. Возможно это снова куб 2. Далее показан пример вывода результатов.

Рассмотрим строку 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`-й символ включительно.

ABBCCC
3
1 4
4 6
1 2

3
1
2