Задачи командных соревнований PRIME TIME 2021
1. Игра в простые числа
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
В известной игре в слова нужно составлять слова из букв заданного слова. При этом количество букв в составленном слове
не должно превышать количества этих букв в слове-основе. Победителем считается тот, кто составит наибольшее количество слов.
Напишите программу для игры в числа, которая составляет простые числа из цифр заданного числа.
Первая строка ввода содержит одно число `N` (`1 <= N < 10^7`).
Вывести количество различных простых чисел, которые можно составить из цифр числа `N`.
```sample Пример ввода 1
121
```
```sample Пример вывода 1
3
```
Простыми числами, которые можно составить из цифр числа 121, являются 11, 2 и 211.
```sample Пример ввода 2
46
```
```sample Пример вывода 2
0
```
2. No Thanks!
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
No Thanks! is a card game for three to five players designed by Thorsten Gimmler and originally called Geschenkt!
There are playing cards numbered 3 to 35 in the game, and nine cards are chosen at random and removed from the deck, which is then shuffled.
Each player starts with 11 chips.
The first player flips over the top card and either takes it (earning that player points according to the value) or passes on
the card by paying a chip (placing it on the card) and saying, "No thanks!"
Play then proceeds in a clockwise circle until someone finally takes the card along with all of its accumulated chips,
if any. That same player then flips over the next card, also deciding on whether to take the card or pass it, and so the
game continues until all cards have been taken.
At the end of the game, players accrue points from cards according to their value, but cards in a row only count as
a single card with the lowest value (e.g., a run with cards numbered 30, 29, 28, 27 is worth 27 points). Chips are worth *one
negative point* each. The player(s) with the lowest number of points win(s) the game.
Your job is to compute the score for a single player’s pile of cards.
The first line contains two integers, `n` (`1 <= n <= 10^5`), representing the number of cards collected, and `m` (`0 <= m <= 10^5`),
representing the number of player's chips.
The second line contains `n` integers representing the numbers on the collected cards.
All card values are in the range `1...10^5` inclusive, and no card value is repeated.
Output a single line containing the score for the given set of cards.
```sample Sample Input 1
5 0
1 3 7 5 4
```
```sample Sample Output 1
11
```
```sample Sample Input 2
6 10
2 8 1 3 4 5
```
```sample Sample Output 2
-1
```
3. HTML From Shortcuts
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
One kind of software that is becoming very popular is software for blog writting.
A typical blog
writting software will parse text into Hypertext Markup Language (HTML) that is suitable to display
content in widely used web browsers.
While you can write HTML, most content authors do not
have expertise using it, or do not feel comfortable writing using HTML tags. To make their lives
easier, you decided to offer a software with a simpler syntax, authors can write their content and
use “shortcuts” to achieve some markup textual effects when displaying it. To start, you decided to
implement “shortcuts” for two of the most used text decorations in a blog: bold text, and italic.
To write bold text, the author can write the asterisk ('\*') shortcut, for example, if the author
types: "\*This is bold\*", the software will render the HTML code "<b>This is bold</b>".
For italic, the author can write the underscore ('\_') shortcut, for example, if the author types:
"_This is italic_", the software will render the HTML code "<i>This is italic</i>".
To make the authors job easier, nesting of shortcuts is not allowed, this is no text enclosed in a
shortcut will have another shortcut.
Your job is to write the code that will take a document written with shortcuts and translate it
into proper HTML.
The first line contains a text written in shortcut. The shortcut text is a string
with at most 100 characters, containing only characters that are the letters from the english alphabet:
'a' to 'z' and 'A' to ’Z’, the underscore '\_', the asterisk '\*', the space character, and the punctuation
symbols: ',', ';', '.', '!', '?', '-', '(', and ')'.
It is guaranteed that if there will be an even number of
underscores and asterisks.
Print a single line containing the HTML code for the shortcut text given in the input.
```sample Sample Input 1
_This is italic_*This is bold*
```
```sample Sample Output 1
<i>This is italic</i><b>This is bold</b>
```
```sample Sample Input 2
*(Is,;*this.)*a!*_question?_*-*__
```
```sample Sample Output 2
<b>(Is,;</b>this.)<b>a!</b><i>question?</i><b>-</b><i></i>
```
4. Минимальные поднаборы
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Строка “aabbabb” состоит из букв 'a' и 'b'. "Поднабором" будем называть
непрерывную подпоследовательность символов заданной строки,
которая содержит все символы исходной строки хотя бы в одном экземпляре.
Минимальным поднабором
будем назвать поднабор, у которого нельзя убрать букву в начале или в конце последовательности, так как
не все буквы будут присутствовать в последовательности.
Например, поднабором является подстрока "aabb", а минимальным поднабором является подстрока "ab".
Эта подстрока присутствует в исходной строке дважды. Есть два различных минимальных поднабора
в строке “aabbabb”: "ab" и "ba".
Напишите программу, которая определяет количество различных минимальных поднаборов для заданной строки.
Первая строка ввода содержит строку длиной от 1 до 100000 символов, состоящую из латинских букв и цифр
(a–z, A–Z, 0–9). Строчные и прописные буквы считаются различными.
Вывести одно целое число -- количество различных минимальных поднаборов.
```sample Пример ввода 1
aabbabb
```
```sample Пример вывода 1
2
```
```sample Пример ввода 2
abAB347aB3ba7
```
```sample Пример вывода 2
3
```
5. Очистка памяти
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
В новом процессоре PDP-1 (Prime Data Processor) есть специальная операция `dec(i,j,k)`,
которая уменьшает все ячейки памяти с `i`-й по `j`-ю включительно на целое положительное число `k`.
Разработчики процессора не сделали операцию для очистки (обнуления) памяти. Необходимо, используя только указанную
операцию, очистить `n` ячеек памяти, имеющих заданные начальные значения.
Напишите программу, которая определит наименьшее количество операций для обнуления памяти.
Первая строка ввода содержит одно целое число `n` (`1 <= n <= 10^5`) -- количество обнуляемых ячеек.
Вторая строка ввода содержит `n` целых чисел `a_i` (`0 <= a_i <= 10^9`, `0 <= i < n`) -- начальные значения
ячеек памяти.
Вывести одно целое число -- минимальное количество операций для обнуления памяти.
```sample Пример ввода 1
3
1 1 1
```
```sample Пример вывода 1
1
```
```sample Пример ввода 2
5
2 5 5 5 2
```
```sample Пример вывода 2
2
```
Для обнуления нужно выполнить 2 операции:\
dec(0,4,2)\
dec(1,3,3)
```sample Пример ввода 2
7
3 2 3 2 7 2 0
```
```sample Пример вывода 2
4
```
Для обнуления нужно выполнить 4 операции:\
dec(0,5,2)\
dec(0,0,1)\
dec(2,2,1)\
dec(4,4,5)
6. Ленивый турист
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Задача о "ленивом туристе" формулируется следующим образом. Имеется рюкзак, который может вместить предметы общим весом не более `C`,
и `N` предметов, `i`-й предмет имеет вес `w_i`.
Нужно выбрать предметы так, чтобы их суммарный вес минимальным, но при этом ни один из оставшихся предметов
нельзя добавить в рюкзак. Например, если есть три предмета с весами 4, 3 и 5, а вместимость рюкзака равна 7,
то ленивый турист может положить в рюкзак предмет с весом 5, тогда в рюкзак нельзя будет положить ни предмет с весом 3, ни предмет с весом 4.
Первая строка ввода содержит два целых числа -- количество предметов `N` (`1 <= N <= 1000`) и вместимость рюкзака `C` (`1 <= C <= 10^5`).
Вторая строка содержит `N` целых чисел -- веса предметов `w_i` (`1 <= w_i <= C`).
В первой строке вывести количество выбранных предметов `K` (`1 <= K <= N`). Во второй строке вывести `K` чисел -- веса выбранных предметов через пробел.
Веса предметов можно вывести в любом порядке, если существует несколько вариантов, минимизирующих суммарный вес, то можно вывести любой из них.
```sample Пример ввода
3 7
4 3 5
```
```sample Пример вывода
1
5
```
7. Чат
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Команда разработчиков общается в чате, посылая друг другу сообщения.
Всем участникам команды нужно читать эти сообщения, но так как в чат они заходят только
при отправке нового сообщения, то могут быть сообщения, которые кто-то из участников ещё не прочитал.
При входе каждый участник сначала читает все сообщения, появившиеся в чате, затем отправляет
новое сообщение. Естественно, при отправке он читает своё сообщение.
Будем считать, что чтение и написание сообщений происходит
мгновенно, и в этот момент времени в чате находится только один участник.
Напишите программу, которая считает суммарное количество непрочитанных сообщений для всех участников команды
после отправки очередного сообщения в чат.
Первая строка ввода содержит два целых числа -- количество участников чата `n` (`1 <= n <= 10^9`) и
количество отправленных сообщений `m` (`1 <= m <= 10^4`).
Далее следует `m` строк, каждая строка содержит одно целое число -- номер участника от 1 до `n`,
отправившего очередное сообщение.
Вывести `m` строк, в каждой строке вывести суммарное количество непрочитанных сообщений после отправки i-го сообщения.
```sample Пример ввода 1
2 4
1
2
1
2
```
```sample Пример вывода 1
1
1
1
1
```
```sample Пример ввода 2
3 9
1
2
3
2
1
3
3
2
1
```
```sample Пример вывода 2
2
3
3
4
3
3
5
4
3
```
8. Треугольник Штерна
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Треугольник Штерна строится следующим образом.
`n`-я строка содержит `2^n-1` элементов
Обозначим значение `k`-го элемента в `n`-й строке как `S(n, k)`.
Будем считать, что `S(n, k) = 0` если `k = 0` или `k = 2^n`.
Тогда\
`S(1, 1) = 1`\
`S(n+1, 2*k) = S(n, k)` для `n >= 1`\
`S(n+1, 2*k+1) = S(n, k) + S(n, k+1)`.
Первые 6 строк треугольника Штерна выглядят так:
```text
1
1 1 1
1 1 2 1 2 1 1
1 1 2 1 3 2 3 1 3 2 3 1 2 1 1
1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 4 3 5 2 5 3 4 1 3 2 3 1 2 1 1
1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7 2 7 5 8 3 7 4 5 1 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 4 3 5 2 5 3 4 1 3 2 3 1 2 1 1
```
При достаточно большом `n` `S(n+1,k)=S(n,k)`.
Рассмотрим предельную последовательность `B(k)=lim_{n->oo} S(n,k)`.
Можно доказать, что для любого рационального положительного числа `p/q`, где `gcd(p,q)=1`,
существует ровно одно `k`, такое что `p/q={B(k)}/{B(k+1)}`. Например, `3/5={B(10)}/{B(11)}`.
Напишите программу, которая находит заданное рациональное число в последовательности `B(k)`.
Первая строка ввода содержит два взаимно простых целых числа `p` и `q` (`1 <= p, q <= 200000`).
Вывести одно целое число -- номер элемента `k` по модулю `1 000 000 007`.
```sample Пример ввода 1
3 5
```
```sample Пример вывода 1
10
```
```sample Пример ввода 2
123 67
```
```sample Пример вывода 2
131197
```
9. Пропущенный номер
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Вы участвуете в беспроигрышной лотерее, каждому участнику лотереи был присвоен номер от 1 до `N`
(`2 <= N <= 99`).
Вы пришли уже после завершения розыгрыша, и на доске в беспорядке записаны номера
участников, уже получивших приз.
Приз ещё можно получить, если вы покажете свою карточку
с номером или хотя бы вспомните номер.
К сожалению, вы потеряли карточку. Но, очевидно, что у вас был номер, отсутствующий на доске.
Напишите программу, которая поможет определить пропущенный номер по записям на доске.
Первая строка ввода содержит последовательность цифр -- номера участников в порядке розыгрыша призов. Гарантируется, что пропущен ровно один номер из диапазона от 1 до `N`.
Вывести пропущенный номер в этой последовательности.
Если существует несколько вариантов, вывести все варианты в порядке возрастания номеров.
```sample Пример ввода 1
52314
```
```sample Пример вывода 1
6
```
```sample Пример ввода 2
3456789101113141516171819201212
```
```sample Пример вывода 2
12
21
```
10. Метапрограммирование
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Перед вами устройство с экраном и площадкой 3x6, на которой расположены 5 клавиш и изображение человечка.
Верхняя и нижняя строки площадки пустые, все клавиши и изображение находятся во второй строке площадки.
Сначала при нажатии на клавиши вверх (U), вниз (D), вправо (R) и влево (L) ничего не происходит,
но после нажатия на клавишу включения (+), на экране появляется изображение такого же устройства.
Далее устройство не реагирует на повторное нажатие клавиши включения,
но нажатие на клавиши направления приводят человечка в движение. Команды,
которые могут вывести человечка за пределы площадки, игнорируются.
При перемещении человечка на клавишу включения на экране нарисованного устройства
появляется изображения очередного устройства, движения человечка на котором подчиняются
командам первого нарисованного устройства, которым
можно управлять с помощью клавиш начального устройства. Человечек может находиться на
клавишах сколь угодно долго, к движению человечка на следующем устройстве
приводит только перемещение человечка на клавишу с другой клавиши или с пустой клетки площадки.
Напишите программу, которая укажет порядок нажатия клавиш для включения `K`-го устройства.
Начальное устройство имеет номер 0.
Первая строка ввода содержит одно целое число - номер включаемого устройства `K` (`1 <= K <= 9`). Далее следует строка, содержащая
перестановку символов U, D, R, L, + и * (этот символ указывает начальную позицию человечка при включении).
Вывести строку, содержащую последовательность нажатий клавиш на начальном устройстве.
Последовательность должна содержать только символы +, U, D, R, L.
Последовательность может быть произвольной и не обязательно минимальной.
```sample Пример ввода
2
+UDLR*
```
```sample Пример вывода
+LLLLLURRRDDUUDDUUD
```
11. Соседние клетки
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
После случайной генерации поля для игры необходимо определить его характеристики:
количество связей между клетками по стороне и количество связей между клетками по вершинам.
Напишите программу для выполнения этой задачи.
Первая строка ввода содержит два целых числа -- количество строк `R` (`1 <= R <= 1000`) и
и количество столбцов `C` (`1 <= C <= 1000`). Следующие `R` строк содержат `C` целых чисел
0 или 1 -- сгенерированное поле (1 означает обычную клетку, 0 -- препятствие).
Вывести два целых числа - количество связей между обычными клетками по стороне и количество связей между обычными клетками по вершинам.
```sample Пример ввода
5 5
1 0 0 1 0
0 1 1 0 1
0 1 0 1 1
1 0 1 1 1
0 1 1 1 1
```
```sample Пример вывода
14 17
```
Начало
Соревнования
Простые числа, разложение на множители