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

В одной маленькой стране есть всего три города и три платных двухсторонних дорог. Первая дорога проходит между городами $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$.

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

Вам даны два целых числа $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$).

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

Маленький Дамир еще не научился делать переносы при сложении чисел. Но он отлично справляется со сложением чисел, где не нужно делать перенос. Например, Дамир не сможет посчитать $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$.

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

Вам даны два массива положительных целых чисел $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$.