2-й этап Республиканской олимпиады по информатике 2022-2023


Задача A. Три города

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

В одной маленькой стране есть всего три города и три платных двухсторонних дорог. Первая дорога проходит между городами $1$ и $2$, проехать по этой дороге стоит $A$ тенге. Вторая дорога проходит между городами $2$ и $3$, проехать по этой дороге стоит $B$ тенге. Третья дорога соединяет города $1$ и $3$, проехать по этой дороге стоит $C$ тенге. Парасату нужно доехать из города $1$ в город $3$ потратив как можно меньше денег.
Формат входного файла
В единственной строке находятся три целых числа $A$, $B$, $C$($1 <= A,B,C <= 5000$).
Формат выходного файла
Выведите минимальную стоимость добраться из города $1$ в город $3$.
Система оценки
Данная задача состоит из $10$ тестов. Каждый тест оценивается в $10$ баллов.
Примеры:
Вход
10 7 15
Ответ
15
Вход
200 300 700
Ответ
500
Замечание
Во втором примере: Парасату выгодно поехать через город $2$.

комментарий/решение(6) Проверить мое решение

Задача B. Сумма, произведение и четыре числа

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

Вам даны два целых числа $s$ и $p$. Найдите количество целых положительных четверок, что их сумма не превышает $s$, а произведение не превышает $p$. Формально, в этой задаче вам нужно найти количество таких целых положительных четверок $a, b, c, d$ что выполняются два условия: 1. $a + b + c + d <= s$ 2. $a * b * c * d <= p$
Формат входного файла
В первой строке входных данных даны два целых числа $s$ и $p(1 <= s <= 500, 1 <= p <= 10^9)$.
Формат выходного файла
В единственной строке выведите ответ на задачу.
Система оценки
В этой задаче 10 тестов, каждая из них оценивается в 10 баллов:
  • Тесты 1-2: Примеры из условия.
  • Тесты 3-6: $s <= 100$.
  • Тесты 7-10: без дополнительных ограничений.
Примеры:
Вход
5 10
Ответ
5
Вход
10 15
Ответ
125
Замечание
Все подходящие четверки в первом примере: ($1,1,1,1$), ($2,1,1,1$), ($1,2,1,1$), ($1,1,2,1$), ($1,1,1,2$).

комментарий/решение(4) Проверить мое решение

Задача C. Без переноса

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

Маленький Дамир еще не научился делать переносы при сложении чисел. Но он отлично справляется со сложением чисел, где не нужно делать перенос. Например, Дамир не сможет посчитать $27+5$, но легко посчитает $31421 + 6374 + 3$. У вас есть $N$ чисел. Вам нужно среди них выбрать максимальное количество чисел, которых можно сложить без переноса.
Формат входного файла
В первой строке находится одно целое число $N(1 <= N <= 18)$. Во второй строке находятся $N$ целых числа $a_1, a_2, ..., a_N$($1 <= a_i <= 10^8$).
Формат выходного файла
Выведите ответ на задачу.
Система оценки
Данная задача состоит из $10$ тестов. Каждый тест оценивается в $10$ баллов.
  • Тест 1. Пример из условия.
  • Тесты 2-4: $n = 2$.
  • Тесты 5-7: $1 <= a_i <= 9$.
  • Тесты 8-10: без дополнительных ограничении.
Пример:
Вход
5
8 45 32 27 111
Ответ
3
Замечание
В первом примере можно выбрать три числа: $45$,$32$,$111$.

комментарий/решение(1) Проверить мое решение

Задача D. Сумма-делимые отрезки

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

Вам даны два массива положительных целых чисел $a$ и $b$ длины $n$. Нумерация обоих массивов начинается с $1$. Посчитайте количество отрезков $(l, r)$ таких, что $1 <= l <= r <= n$ и $a_l + \ldots + a_r$ нацело делится на $b_l + \ldots + b_r$. Простыми словами, сумма массива $a$ на этом отрезке должна делиться без остатка на сумму массива $b$ на том же отрезке.
Формат входного файла
В первой строке дано одно целое число $n$ — длины массивов ($1 <= n <= 10^5$). Во второй строке даны числа $a_1$, \ldots, $a_n$ ($1 <= a_i <= 10$). В третьей строке даны числа $b_1$, \ldots, $b_n$ ($1 <= b_i <= 10$).
Формат выходного файла
Выведите одно целое число — количество подходящих отрезков $(l, r)$.
Система оценки
Данная задача состоит из $10$ тестов. Каждый тест оценивается в $10$ баллов.
  • [(1-2)] Примеры из условия.
  • [(3-4)] $n = 1$.
  • [(5-6)] $n = 100$.
  • [(7-8)] $n = 2000$.
  • [(9-10)] $n = 100000$.
Примеры:
Вход
3
1 2 3
1 1 1
Ответ
4
Вход
5
2 3 1 5 4
3 2 2 1 2
Ответ
7
Замечание
В первом примере подходят $4$ отрезка $(1, 1)$, $(2, 2)$, $(3, 3)$, $(1, 3)$. Отрезок $(1, 3)$ подходит, потому что $a_1+a_2+a_3=1+2+3=6$ делится без остатка на $b_1+b_2+b_3=1+1+1=3$.

комментарий/решение(1) Проверить мое решение