Олимпиада 1С 2025, предметный тур
Statement is not available in English language
A. Комбинации
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть $$$A$$$ единиц и $$$B$$$ троек. Определите, сколько различных целых положительных чисел можно представить в виде суммы чисел из этого набора.

Входные данные

В первой строке содержится одно число $$$A$$$ ($$$0 \le A \le 10^5$$$) — количество единиц в наборе.

Во второй строке содержится одно число $$$B$$$ ($$$0 \le B \le 10^5$$$) — количество троек в наборе.

Выходные данные

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

Система оценки

В данной задаче $$$20$$$ тестов, помимо тестов из условия, каждый из них оценивается в $$$5$$$ баллов. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.

Решения, корректно работающие при $$$A, B \le 100$$$, наберут не менее $$$50$$$ баллов.

Примеры
Входные данные
3
5
Выходные данные
18
Входные данные
1
3
Выходные данные
7
Входные данные
0
10
Выходные данные
10
Входные данные
2
5
Выходные данные
17
Примечание

В первом примере в виде суммы от $$$0$$$ до $$$3$$$ единиц и от $$$0$$$ до $$$5$$$ троек можно представить любое число от $$$1$$$ до $$$18$$$.

Во втором примере можно получить такие числа: $$$1, 3, 4, 6, 7, 9, 10$$$.

В третьем примере можно получить числа $$$3, 6, \ldots, 30$$$.

В четвёртом примере можно получить все числа от $$$1$$$ до $$$17$$$.

Statement is not available in English language
B. Диплом
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В финальном этапе олимпиады участвовало $$$n$$$ школьников. Первый участник набрал $$$a_1$$$ баллов, второй набрал $$$a_2$$$ баллов, и так далее. Участники не упорядочены по баллам. Оказалось, что никакие два участника не набрали одинаковое количество баллов.

Дипломами будут награждены $$$\frac{n}{2}$$$ участника, которые набрали больше всего баллов. Гарантируется, что $$$n$$$ было чётным, поэтому количество дипломов всегда будет целым. Определите, получит ли первый участник (набравший $$$a_1$$$ баллов) диплом.

Входные данные

В первой строке находится одно число $$$n$$$ ($$$2 \le n \le 100$$$, $$$n$$$ — чётное) — количество участников олимпиады.

В $$$i$$$-й из следующих $$$n$$$ строк содержится по одному числу $$$a_i$$$ ($$$0 \le a_i \le 500$$$) — количество баллов, которое набрал очередной участник. Гарантируется, что все участники набрали разное число баллов.

Выходные данные

В ответ выведите «YES» (без кавычек), если первый участник получит диплом, и «NO», если не получит.

Система оценки

В данной задаче $$$20$$$ тестов, помимо тестов из условия, каждый из них оценивается в $$$5$$$ баллов. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.

Решения, корректно работающие при $$$n = 2$$$, наберут не менее $$$20$$$ баллов.

Примеры
Входные данные
4
400
300
200
500
Выходные данные
YES
Входные данные
2
1
2
Выходные данные
NO
Входные данные
6
100
50
10
25
5
0
Выходные данные
YES
Примечание

В первом примере первый участник набрал $$$400$$$ баллов. Если расположить баллы участников по убыванию, то мы получим такой порядок: $$$500, 400, 300, 200$$$. Так как было $$$4$$$ участника, то дипломы получат двое лучших, среди которых есть $$$a_1$$$.

Во втором примере диплом получит только второй участник.

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

Statement is not available in English language
C. Собери все монеты!
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы играете в мобильную игру, где вам нужно собирать монетки. Уровень выглядит как клетчатое поле из $$$n$$$ строк и $$$3$$$ столбцов. Пронумеруем строки сверху вниз, а столбцы — слева направо. Обозначим как $$$(i, j)$$$ клетку, находящуюся на пересечении $$$i$$$-й строки и $$$j$$$-го столбца. Каждая клетка поля либо пуста, либо содержит монетку. Гарантируется, что в каждой строке находится не более $$$2$$$ монеток. Также гарантируется, что в первой строке монеток нет.

Вы играете за двух персонажей — Алису и Боба. Изначально Алиса находится на клетке $$$(1, 1)$$$, а Боб — на клетке $$$(1, 3)$$$. Каждую секунду оба персонажа делают ход. Пусть до начала хода персонаж находился в клетке $$$(i, j)$$$. Тогда за ход он может перейти в:

  • клетку $$$(i + 1, j)$$$ — перейти на одну клетку вниз;
  • клетку $$$(i + 1, j - 1)$$$, если $$$j \gt 1$$$ — перейти по диагонали вниз и влево;
  • клетку $$$(i + 1, j + 1)$$$, если $$$j \lt 3$$$ — перейти по диагонали вниз и вправо;

Также после хода персонажи не должны оказаться в одной клетке. Игра заканчивается, когда они оказываются в $$$n$$$-й строке, то есть всего они сделают $$$n - 1$$$ ход.

Ваша задача — составить план перемещений для Алисы и Боба, в результате которого они соберут все монетки и никогда не окажутся в одной клетке. Можно показать, что при заданных ограничениях это всегда возможно.

Входные данные

В первой строке содержится одно число $$$n$$$ ($$$1 \le n \le 1000$$$) — количество строк игрового поля.

На $$$i$$$-й из следующих $$$n$$$ строк находится по $$$3$$$ символа — описание $$$i$$$-й строки поля: «C» означает клетку с монеткой, а «.» — пустую клетку. Гарантируется, что в первой строке монеток нет. Также гарантируется, что в каждой строке находится не более $$$2$$$ монеток.

Выходные данные

Выведите план перемещений Алисы и Боба — $$$n - 1$$$ строку по $$$2$$$ символа. Первый символ в строке означает ход Алисы, а второй — ход Боба. «D» означает переход вниз, «L» означает переход по диагонали вниз и влево, а «R» — переход по диагонали вниз и вправо.

Система оценки

В данной задаче $$$20$$$ тестов, помимо тестов из условия, каждый из них оценивается в $$$5$$$ баллов. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.

Решения, корректно работающие, когда в одном ряду не может быть монетки в $$$1$$$ и $$$2$$$ столбце, наберут не менее $$$30$$$ баллов.

Решения, корректно работающие, когда в каждом ряду (кроме первого) находится ровно две монетки, наберут не менее $$$30$$$ баллов.

Примеры
Входные данные
5
...
CC.
..C
C..
.CC
Выходные данные
DL
DR
DD
RD
Входные данные
4
...
.CC
CC.
.CC
Выходные данные
RD
LL
RR
Входные данные
3
...
...
.C.
Выходные данные
RD
DD
Примечание

В первом примере персонажи перемещаются по таким траекториям:

Statement is not available in English language
D. Контрольная сумма
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Один банк выпускает кредитные карты, у которых номера состоят из $$$n$$$ цифр. При этом номер состоит из $$$2$$$ частей: первые $$$n - 2$$$ цифры — любые, а последние две являются контрольной суммой, которая вычисляется так:

  • Изначально контрольная сумма $$$S$$$ равна $$$0$$$;
  • Для вычисления суммы нужно пройти по первым $$$n - 2$$$ цифрам номера карты слева направо;
  • Если текущая позиция — нечётная (в нумерации с $$$1$$$), то прибавить текущую цифру к $$$S$$$;
  • Если же позиция чётная, то прибавить к $$$S$$$ удвоенную текущую цифру;
  • Тогда последние $$$2$$$ цифры номера карты определяются как две последние цифры числа $$$S$$$ (если $$$S$$$ — однозначное, то добавляется ведущий ноль).
  • Для примера вычисления контрольной суммы обратитесь к примечанию.

Назовём строку из $$$n$$$ цифр корректным номером карты, если последние $$$2$$$ цифры совпадают с контрольной суммой, вычисленной по первым $$$n - 2$$$ цифрам в соответствии с алгоритмом.

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

Входные данные

В первой строке содержится одно число $$$n$$$ ($$$3 \le n \le 10^5$$$) — длина номера карты.

Во второй строке содержится строка из $$$n$$$ цифр — номер, записанный на бумажке. Обратите внимание, что номер карты стоит рассматривать именно как строку, так как она может содержать ведущие нули и быть очень большим числом.

Выходные данные

Если существует корректный номер кредитной карты, который отличается от записанного не более чем в $$$1$$$ символе, в первой строке выведите «YES» (без кавычек). Во второй строке выведите подходящий корректный номер карты.

Если же искомого номера карты не существует, выведите в первой строке «NO» (без кавычек).

Система оценки

В данной задаче $$$20$$$ тестов, помимо тестов из условия, каждый из них оценивается в $$$5$$$ баллов. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.

Решения, корректно работающие при $$$n \le 5$$$, наберут не менее $$$20$$$ баллов.

Решения, корректно работающие при $$$n \le 100$$$, наберут не менее $$$60$$$ баллов.

Примеры
Входные данные
5
26919
Выходные данные
YES
24919
Входные данные
5
21448
Выходные данные
YES
21408
Входные данные
4
9999
Выходные данные
NO
Примечание

В первом примере изначально строка не является корректным номером кредитной карты: контрольная сумма равна $$$2 + 6 \cdot 2 + 9 = 23$$$, а последние два символа строки — 19. Но после изменения второго символа она становится корректной: $$$2 + 4 \cdot 2 + 9 = 19$$$. Существует ещё один корректный ответ: 26519.

Во втором примере контрольная сумма вычисляется так: $$$2 + 1 \cdot 2 + 4 = 8$$$. Значит, можно изменить четвёртый символ, и строка 21408 будет корректным номером кредитной карты.

Для третьего примера не существует корректного номера кредитной карты, который отличается от записанной строки не более чем в одном символе.

Statement is not available in English language
E. Оптимальная анаграмма
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана строка $$$s$$$. Пусть $$$t$$$ — анаграмма$$$^{\text{∗}}$$$ строки $$$s$$$.

Определим стоимость $$$t$$$ как количество строчных латинских букв $$$a, b, \ldots, z$$$, таких, что эта буква встречается в строке $$$s$$$ (тогда она встречается и в $$$t$$$), и индекс её самого левого вхождения этой буквы в строку $$$t$$$ меньше индекса самого левого вхождения в строку $$$s$$$. Для примера расчёта стоимости анаграммы обратитесь к примечанию.

Ваша задача — по заданной строке $$$s$$$ и числу $$$k$$$ найти лексикографически минимальную$$$^{\text{†}}$$$ анаграмму со стоимостью не более $$$k$$$.

$$$^{\text{∗}}$$$Строка $$$t$$$ является анаграммой строки $$$s$$$, если $$$t$$$ можно получить из $$$s$$$ перестановкой символов. Иными словами, каждая буква входит в строку $$$s$$$ и строку $$$t$$$ одинаковое число раз.

$$$^{\text{†}}$$$Строка $$$a$$$ лексикографически меньше строки $$$b$$$ ($$$a$$$ идёт раньше $$$b$$$ в алфавитном порядке), если и только если выполняется одно из двух условий:

  • $$$b$$$ начинается со строки $$$a$$$, но $$$a \ne b$$$; или
  • в первой позиции, где $$$a$$$ и $$$b$$$ различны, в строке $$$a$$$ находится буква, которая встречается в алфавите раньше, чем соответствующая буква в $$$b$$$.
Входные данные

В первой строке содержится одно число $$$n$$$ ($$$1 \le n \le 10^5$$$) — длина строки $$$s$$$.

Во второй строке содержится строка $$$s$$$ длины $$$n$$$, состоящая из строчных латинских букв.

В третьей строке содержится одно число $$$k$$$ ($$$0 \le k \le 26$$$) — ограничение на стоимость анаграммы.

Выходные данные

Выведите одну строку — лексикографически минимальную анаграмму строки $$$s$$$ со стоимостью не более $$$k$$$.

Система оценки

В данной задаче $$$20$$$ тестов, помимо тестов из условия, каждый из них оценивается в $$$5$$$ баллов. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.

Решения, корректно работающие, когда строка $$$s$$$ состоит только из символов a и b, наберут не менее $$$30$$$ баллов.

Решения, корректно работающие при $$$n \le 8$$$, наберут не менее $$$30$$$ баллов.

Решения, корректно работающие при $$$n \le 1000$$$, наберут не менее $$$50$$$ баллов.

Решения, корректно работающие при $$$k=0$$$, наберут не менее $$$30$$$ баллов.

Примеры
Входные данные
6
banana
1
Выходные данные
aaabnn
Входные данные
6
banana
0
Выходные данные
baaann
Входные данные
8
bbaabbaa
0
Выходные данные
bbaaaabb
Примечание

В первом примере s="banana", а t="aaabnn". Строка $$$t$$$ является анаграммой $$$s$$$, так как её можно получить перестановкой символов. Стоимость $$$t$$$ определяется так:

  • Буква a первый раз встречается в $$$s$$$ на позиции $$$2$$$ (в $$$1$$$-нумерации), а в $$$t$$$ на позиции $$$1$$$, поэтому она увеличивает стоимость на $$$1$$$.
  • Буква b в строке $$$s$$$ находится на позиции $$$1$$$, а в $$$t$$$ — на позиции $$$4$$$. Значит, она встречается в $$$s$$$ не позже, чем в $$$t$$$, поэтому она не увеличивает стоимость.
  • Буква n в строке $$$s$$$ находится на позиции $$$3$$$, а в $$$t$$$ — на позиции $$$5$$$. Значит, она встречается в $$$s$$$ не позже, чем в $$$t$$$, поэтому она не увеличивает стоимость.
  • Остальные буквы не встречаются в строках.

Итого, стоимость такой анаграммы равна $$$1$$$.

Во втором и третьем примере анаграммы имеют стоимость $$$0$$$.