Есеп A. Керемет сыйлық

Жақында Темірланның туған күні болды. Ең қызық сыйлықты оның досы Айсұлтан жасады. Айсұлтан Темірланның керемет сандарды ұнататынын біледі. Айсұлтанның ойынша, белгілі бір сан кез келген басқа бір бүтін санның квадратына тең болса, ол сан керемет сан деп есептелінеді. Мысалы, $0$, $9$, $121$ — керемет сандар, ал $50$, $3$, $12$ — керемет сандар емес. Айсұлтанда қазір $n$ бүтін саннан тұратын массив бар — $a_1, a_2, a_3, ..., a_n$. Сыйлық жасау үшін, осы тізбектен Айсұлтан екі сан $a_j$ и $a_i$ ($j < i$) алып, олардың көбейтіндісінің керемет сан бола алуын тексереді. Егер де, көбейтінді сан $a_j * a_i$ керемет болса, онда Айсұлтан көбейтіндіні Темірланға сыйлай алады деген сөз. Айсұлтан сыйлықты неше түрлі жолмен жасай алатынын анықтаңыз. Басқаша айтқанда, тізбектен $(a_j, a_i)$ жұптарының арасында $j < i$ болатын және $a_j * a_i$ көбейтіндісі керемет сан болатын жұптардың санын табыңыз. Бірінші жолда тек $n$ берілген — тізбектің ұзындығы $(1 \le n \le 10^3)$. Екінші жолда бос орын арқылы жазылған $n$ бүтін саннан тұратын тізбек $a_1, a_2, a_3, ..., a_n$ берілген — Айсұлтанның тізбегі $(-1000 \le a_i \le 1000)$. Тек бір сан, яғни, Айсұлтанның неше жолмен сыйлық жасай алатынын шығаруыңыз керек. Вход

4
1 0 1 1

Ответ

6

Вход

2
-8 -2

Ответ

1

Вход

3
1 16 4

Ответ

3

Вход

1
0

Ответ

0

Бұл есеп 3 бөлімнен тұрады:

1. $0 \le a_i \le 1$ барлық $1 \le i \le n$ үшін.
2. $n = 2$, $-1000 \le a_i \le 1000$.
3. Есептің берілгеніндегі шарттар.

Бірінші мысалда 6 жұптың барлығының көбейтіндісі 0 немесе 1 санының квадраты болып табылады. Екінші мысалда тек бір жұптың көбейтіндісі ережеге сәйкес — бүтін санның квадраты болатын 16 саны. Үшінші мысалда (1, 16), (1, 4), (16, 4) жұптарының барлығының көбейтіндісі бүтін санның квадраты болып табылады. Төртінші мысалда сыйлық құрай алатын бір де бір жұп жоқ.

Есеп B. Бөлінеді ме

ОМА санның 8-ге бөлінгіштігінің өз қасиетін ойлап табуды ұйғарды. Егер берілген санның цифрларының орындарын ауыстрығанда, бастаушы нөлдерсіз және 8-ге бөлінетін сандар тізбегі табылатын болса, ОМА бұл санды 8-ге бөлінеді деп атайды. Бірінші жолда бүтін $n$ саны берілген $(1 \leq n \leq 10^3) $ - санның ұзындығы. $\\$ Екінші жолда цифрлардан тұратын $s$ жолы берілген - тексеру қажет сан. Егер берілген сан 8-ге бөлінетін болса YES, бөлінбесе NO жазуларын шығарыңыз. Вход

2
23

Ответ

YES

Вход

3
101

Ответ

NO

Сандар тізбегі дегеніміз, берілген жолдағы цифлардың орындарын ауыстыру жолымен алынған тізбек. Мысалы 123 жолынан, цифрларды орын ауыстыру арқылы 321, 312, 213, 231, 132 деген сандар тізбегін алуға болады. Бірінші мысалда 23 санынан 8-ге бөлінетін 32 санын алуға болады жауап YES. Екінші мысалда 101 санынан 8-ге бөлінетін сан алуға болмайды, жауап NO.$\\$ $\\$ Subtask 1: $(n \leq 100)$ $\\$ Subtask 2: $(n \leq 1000)$

Есеп C. Квадраттардың қосындысы

Ұзындығы $n$ болатын екі массив берілген. Берілген массивке байланысты, сізге $q$ рет сұрақ қойылады. Сұрақтардың бәрінің үлгісі бірдей, тек сандары өзгереді. Әр сұрақта сізге белгілі бір аралықты анықтайтын $l$ және $r$ берілген. Берілген аралыққа кіретін бүкіл $a[i]$ мен $b[i]$-лардың айырмаларының квадраттарының қосындысын шығаруыңыз керек. $a[i]$ мына аралықта болуы керек: $a_l, a_{l+1}, \ldots, a_r$ $b[i]$ мына аралықта болуы керек: $b_l, b_{l+1}, \ldots, b_r$ Бірінші қатарда сізге екі сан берілген: $n, q, (1 \leq n, q \leq 100000)$\newline Екінші және үшінші қатарда, сәйкесінше, $a$ және $b$ массиві берілген.\newline $(-100000 \leq a[i], b[i] \leq 100000)$, $i$ = 1, 2, ... , $n$\newline Келесі $q$ қатарда $l$, $r$ беріледі: $(1 \leq l \leq r \leq n)$ Система оценки:\newline Тесттердің $40$ пайызында $(1 \leq n, q \leq 100)$\newline Тесттердің $60$ пайызында $(1 \leq n, q \leq 100000)$ Әр сұраққа жауап шығарыңыз. Вход

3 1
1 0 5
1 2 3
2 3

Ответ

8

Есеп D. Теңестіру

Жарасханда $N$ саннан тұратын $a$ массивы бар. Жарасхан берілген массивтың әр санына тек бір операция қолдана алады. Операциялардың 3 түрі бар:

1. Санға бірді қосу.
2. Саннан бірді азайту.
3. Санға нөлді қосу.

Массивтың әр санына берілген үш операцияның тек біреуін ғана қолдана отырып, массивтегі ұқсас элементтердің санын барынша арттыру керек. Бірінші жолда бүтін сан $N$ берілген. Келесі жолда массивтың элементтері берілген $ a_{i} $. Жауап ретінде бір сан шығарыңыз — берілген операцияларды орындағаннан кейінгі массивте кездесетін ұқсас элементердің саны. Бағалау 4 бөлімнен тұрады:

1. $1 \le N \le 2$. $10$ ұпай.
2. $1 \le N \le 10^2$ және $1 \le a_{i} \le 10$. $20$ ұпай.
3. $1 \le N \le 10^5$ және $1 \le a_{i} \le 2$. $20$ ұпай.
4. $1 \le N \le 10^5$ және $1 \le a_{i} \le 10^5$. $50$ ұпай.

Вход

7
3 1 4 1 5 9 2

Ответ

4

Вход

10
1 2 3 4 5 6 7 8 9 10

Ответ

3

Бірінші мысалда массивты былай өзгертуге болады: 2,2,3,2,6,9,2.

Есеп E. 80236 Математик екеніңді дәлелде

ACM ICPC 2018-2019, NEERC - Northern Eurasia Finals-та сәтсіз өнер көрсеткеннен кейін Сақтаушылар335 командасы математикалық сауатылығын көтеруді ұйғарды, себебі сандар теориясы бойынша қарапайым есепті жарыс барысында шығара алмады. Бүгінгі күні команда мүшелерінің бірі үшбұрыштың ауданы бүтін болып табылады ма деген есепті ойлап тапты. Сіздің тапсырмаңыз осы балаларға көмектесу болып табылады. Бірінші жолда үш бүтін сан жазылған $a$, $b$ және $c$ ($ 1 \le a, b, c \le 5000 $) - үшбұрыш жақтарының ұзындығы. Есептің жауабы болатын жалғыз санды шығарыңыз — үшбұрыштың ауданың, егер ол бүтін болса. Басқа жағдайларда -1 шығарыңыз. Вход

3 4 5

Ответ

6

Вход

5 8 5

Ответ

12

Вход

3 3 3

Ответ

-1

Есеп F. Уақыт форматтары

Сізге екі уақыт моменті берілген. Екеуі де бір күннің уақыттары, екеуі екі түрлі және екеуі де бір сағаттан жазылып алынған. Қолданылған сағат қандай форматта жұмыс жасауы мүмкін екенін табыңыз. Егер "12 сағаттық формат" болса, онда уақыттарда сағаттың жазылуы үшін 1 мен 12 арасындағы сандар қолданылады. "24 сағаттық формат" үшін 0 мен 23 арасындағы сандар қолданылады. Тапсырманы толық түсіну үшін мысалдарға назар аударыңыз. Бірінші және екінші қатарда екі уақыт моменті берілген. Егер де, уақыт тек бір форматта болуы мүмкін болса "12-hour clock" немесе "24-hour clock" деп шығарыңыз. Нақты қай форматта екені белгісіз болса "both" деп шығарыңыз. Тырнақшасыз шығарыңыз. Вход

11:00
23:50

Ответ

24-hour clock

Вход

09:20
03:30

Ответ

12-hour clock

Вход

06:00
12:00

Ответ

both

Вход

00:00
01:00

Ответ

24-hour clock

Есеп G. Депозит

Ақымақтар банкінде Жарасханның депозиті бар. Депозиттің ақша соммасы теріс болыу мүмкін. Банк Жарасханның депозитін белгілі пайызбен толтырады. Және де, Жарасхан ақша керек болған кезде, депозиттің бөлігін өзіне ала алады. Сол бөлік пайыз арқылы белгіленеді. Жарасханда барлық пайыз арқылы берілген операциялар тарихы бар. Алғашында Жарасханның депозитінде соммасы $s$ болатын ақша саны бар. Жарасхан ақшасын өзіне алған кезде - пайыз теріс сан, банк толтырғанда - оң санға сейкес келеді. Жарасханның мазалап жүрген бір сұрағы - қай күні депозиттегі сомма ең көп, және қай күні депозиттегі сомма ең аз болғаны. Дәл қазір Жарасхан жұмыспен босамағандықтан, сол сұрақтың жауабын табуды сізге бұйырды. Кіріс файлының ең бірінші жолында, екі бүтін сан берілген $n$ $(1 \le n \le 25)$ - тарихтағы күндер саны, $s$ $(-100 \le s \le 100)$ - Жарасханның депозитіндегі бастапқы сомма. Екінші жолда $n$ $a_i$ сандары берілген $(-2 \le a_i \le 2)$ - $i$-күн пайызының коэффиценті. Екі бүтін сан - Жарасханның депозитіндегі ең көп және ең аз сомма болған күндердің нөмірлерін шығарыңыз. Жауапқа келетін бірнеше күн болса, сондай күндердің ішіндегі бірінші күннің нөмірін шығарыңыз. Есеп 4 бөлімнен тұрады:

1. $n = 1$. $13$ ұпайға есептеледі.
2. $0 \le a_i \le 2$. $5$ ұпайға есептеледі.
3. $1 \le n \le 15$. $40$ ұпайға есептеледі.
4. Берілген шектеулер. $42$ ұпайға есептеледі.

Вход

3 100
0.1 -0.4 2

Ответ

2 3

Вход

3 100
0.5 1 2

Ответ

0 3

Вход

2 100
1 -0.5

Ответ

0 1

Бірінші мысалда, әр күннен кейін шығатын соммалар: $110, 66, 132$. Осы тізбекке қарап, екінші күні ең аз, және үшінші күні ең үлкен сомма бар екенін анықтай аламыз. Екінші мысалда, сомма тек қана өскендіктен, ең басындағы сомма - ең аз болып саналады.

Есеп H. Өспелі бөліктер

Сізде ұзындығы $n$ $a$ массивы бар. Берілген массивке байланысты сізге $q$ рет сұрақ қойылады. Сұрақтардың бәрінің үлгісі бірдей, тек сандары өзгереді. Әр сұрақта сізге белгілі бір аралықты анықтайтын $l$ және $r$ берілген. Осы аралықты ($a_l, a_{l+1}, \ldots, a_r$) $k$ бөлікке бөліңіз. Бірақ, әр бөлігін жеке алып қараған кезде тек өспелі массив шығу керек. $k$-ның мәнін барынша кішірейтіңіз. Бірінші жолда екі сан берілген $n, q$ - массивтін ұзындығы және сұраулар саны. Екінші жолда $n$ сан берілген - а массиві. Әр келесі $q$ жолда екі сан берілген, $l$ және $r$. Әр сұрақта берілген аралықты ережеге сәйкес $k$ рет бөліңіз және $k$-ның мәнін шығарыңыз. Вход

4 3
3 1 4 2
1 4
1 3
4 4

Ответ

3
2
1

Егер барлық $l \leq i \leq r - 1$ үшін $a_i < a_{i+1}$ болса, $a_l, a_{l+1}, \ldots, a_r$ массив бөлігі өспелі деп аталады. Бірінші мысалдағы сұрауларға жауаптар: $ \\ $ [3, 1, 4, 2] - [3], [1, 4], [2] $ \\ $ [3, 1, 4] - [3], [1, 4] $ \\ $ [4] - [4] $ \\ $ $1 \leq n, q \leq 1000$ - 40 ұпай. $ \\ $ $1 \leq n, q \leq 10^5$ - 60 ұпай. $ \\ $