Задача 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. Қосынды-бөлінді кесінділер

Сізге мөлшері $n$ болатын бүтін оң сандардан тұратын $a$ және $b$ массивтері беріледі. Массивтердің екеуі де $1$-ден бастап нөмірленеді. Сізге $1 <= l <= r <= n$ болатын және $a_l + \ldots + a_r$ қалдықсыз $b_l + \ldots + b_r$ санына бөлінетін $(l, 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$ қосындысына бөлінеді.