Информатика пәнi бойынша Республикалық олимпиада 2018-iң 3-шi кезеңi, 10-11 сынып, *1 КҮНI*
Қазақстан, Желтоқсан, 6, 2018

Problem A. Уақыт форматтары
Input file:
Output file:
Time limit:
Memory limit:

standard input
standard output
1 second
256 megabytes

Сiзге екi уақыт моментi берiлген. Екеуi де бiр күннiң уақыттары, екеуi екi түрлi және екеуi де бiр
сағаттан жазылып алынған. Қолданылған сағат қандай форматта жұмыс жасауы мүмкiн екенiн
табыңыз.
Егер "12 сағаттық формат"болса, онда уақыттарда сағаттың жазылуы үшiн 1 мен 12 арасындағы
сандар қолданылады. "24 сағаттық формат"үшiн 0 мен 23 арасындағы сандар қолданылады.
Тапсырманы толық түсiну үшiн мысалдарға назар аударыңыз.

Input
Бiрiншi және екiншi қатарда екi уақыт моментi берiлген.

Output
Егер де, уақыт тек бiр форматта болуы мүмкiн болса "12-hour clock"немесе "24-hour clock"деп шығарыңыз. Нақты қай форматта екенi белгiсiз болса "both"деп шығарыңыз. Тырнақшасыз шығарыңыз.

Examples
standard input
11:00
23:50

standard output
24-hour clock

09:20
03:30

12-hour clock

06:00
12:00

both

00:00
01:00

24-hour clock

Page 1 of 3

Информатика пәнi бойынша Республикалық олимпиада 2018-iң 3-шi кезеңi, 10-11 сынып, *1 КҮНI*
Қазақстан, Желтоқсан, 6, 2018

Problem B. Теңестiру
Input file:
Output file:
Time limit:
Memory limit:

standard input
standard output
1 second
256 megabytes

Жарасханда N саннан тұратын a массивы бар. Жарасхан берiлген массивтың әр санына тек бiр
операция қолдана алады. Операциялардың 3 түрi бар:
1. Санға бiрдi қосу.
2. Саннан бiрдi азайту.
3. Санға нөлдi қосу.
Массивтың әр санына берiлген үш операцияның тек бiреуiн ғана қолдана отырып, массивтегi ұқсас
элементтердiң санын барынша арттыру керек.

Input
Бiрiншi жолда бүтiн сан N берiлген. Келесi жолда массивтың элементтерi берiлген ai .

Output
Жауап ретiнде бiр сан шығарыңыз — берiлген операцияларды орындағаннан кейiнгi массивте кездесетiн ұқсас элементердiң саны.

Scoring
Бағалау 4 бөлiмнен тұрады:
1. 1 ≤ N ≤ 2. 10 ұпай.
2. 1 ≤ N ≤ 102 және 1 ≤ ai ≤ 10. 20 ұпай.
3. 1 ≤ N ≤ 105 және 1 ≤ ai ≤ 2. 20 ұпай.
4. 1 ≤ N ≤ 105 және 1 ≤ ai ≤ 105 . 50 ұпай.

Examples
standard input
7
3 1 4 1 5 9 2
10
1 2 3 4 5 6 7 8 9 10

standard output
4
3

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

Page 2 of 3

Информатика пәнi бойынша Республикалық олимпиада 2018-iң 3-шi кезеңi, 10-11 сынып, *1 КҮНI*
Қазақстан, Желтоқсан, 6, 2018

Problem C. Өспелi бөлiктер
Input file:
Output file:
Time limit:
Memory limit:

standard input
standard output
1 second
256 megabytes

Сiзде ұзындығы n a массивы бар. Берiлген массивке байланысты сiзге q рет сұрақ қойылады.
Сұрақтардың бәрiнiң үлгiсi бiрдей, тек сандары өзгередi. Әр сұрақта сiзге белгiлi бiр аралықты
анықтайтын l және r берiлген. Осы аралықты (al , al+1 , . . . , ar ) k бөлiкке бөлiңiз. Бiрақ, әр бөлiгiн
жеке алып қараған кезде тек өспелi массив шығу керек. k-ның мәнiн барынша кiшiрейтiңiз.

Input
Бiрiншi жолда екi сан берiлген n, q - массивтiн ұзындығы және сұраулар саны. Екiншi жолда n сан
берiлген - а массивi. Әр келесi q жолда екi сан берiлген, l және r.

Output
Әр сұрақта берiлген аралықты ережеге сәйкес k рет бөлiңiз және k-ның мәнiн шығарыңыз.

Example
standard input
4
3
1
1
4

3
1 4 2
4
3
4

standard output
3
2
1

Note
Егер барлық l ≤ i ≤ r − 1 үшiн ai < ai+1 болса, al , al+1 , . . . , ar массив бөлiгi өспелi деп аталады.
Бiрiншi мысалдағы сұрауларға жауаптар:
[3, 1, 4, 2] - [3], [1, 4], [2]
[3, 1, 4] - [3], [1, 4]
[4] - [4]
1 ≤ n, q ≤ 1000 - 40 ұпай.
1 ≤ n, q ≤ 105 - 60 ұпай.

Page 3 of 3

Информатика пәнi бойынша Республикалық олимпиада 2018-iң 3-шi кезеңi, 8-9 сынып, *1 КҮНI*
Қазақстан, Желтоқсан, 6, 2018

Problem A. 80236. Математик екенiңдi дәлелде!
Input file:
Output file:
Time limit:
Memory limit:

standard input
standard output
1 second
256 megabytes

ACM ICPC 2018-2019, NEERC - Northern Eurasia Finals-та сәтсiз өнер көрсеткеннен кейiн Сақтаушылар335 командасы математикалық сауатылығын көтерудi ұйғарды, себебi сандар теориясы бойынша қарапайым есептi жарыс барысында шығара алмады. Бүгiнгi күнi команда мүшелерiнiң бiрi
үшбұрыштың ауданы бүтiн болып табылады ма деген есептi ойлап тапты. Сiздiң тапсырмаңыз осы
балаларға көмектесу болып табылады.

Input
Бiрiншi жолда үш бүтiн сан жазылған a, b және c (1 ≤ a, b, c ≤ 5000) - үшбұрыш жақтарының
ұзындығы.

Output
Есептiң жауабы болатын жалғыз санды шығарыңыз — үшбұрыштың ауданың, егер ол бүтiн болса.
Басқа жағдайларда -1 шығарыңыз.

Examples
standard input

standard output

3 4 5

6

5 8 5

12

3 3 3

-1

Page 1 of 3

Информатика пәнi бойынша Республикалық олимпиада 2018-iң 3-шi кезеңi, 8-9 сынып, *1 КҮНI*
Қазақстан, Желтоқсан, 6, 2018

Problem B. Уақыт форматтары
Input file:
Output file:
Time limit:
Memory limit:

standard input
standard output
1 second
256 megabytes

Сiзге екi уақыт моментi берiлген. Екеуi де бiр күннiң уақыттары, екеуi екi түрлi және екеуi де бiр
сағаттан жазылып алынған. Қолданылған сағат қандай форматта жұмыс жасауы мүмкiн екенiн
табыңыз.
Егер "12 сағаттық формат"болса, онда уақыттарда сағаттың жазылуы үшiн 1 мен 12 арасындағы
сандар қолданылады. "24 сағаттық формат"үшiн 0 мен 23 арасындағы сандар қолданылады.
Тапсырманы толық түсiну үшiн мысалдарға назар аударыңыз.

Input
Бiрiншi және екiншi қатарда екi уақыт моментi берiлген.

Output
Егер де, уақыт тек бiр форматта болуы мүмкiн болса "12-hour clock"немесе "24-hour clock"деп шығарыңыз. Нақты қай форматта екенi белгiсiз болса "both"деп шығарыңыз. Тырнақшасыз шығарыңыз.

Examples
standard input
11:00
23:50

standard output
24-hour clock

09:20
03:30

12-hour clock

06:00
12:00

both

00:00
01:00

24-hour clock

Page 2 of 3

Информатика пәнi бойынша Республикалық олимпиада 2018-iң 3-шi кезеңi, 8-9 сынып, *1 КҮНI*
Қазақстан, Желтоқсан, 6, 2018

Problem C. Теңестiру
Input file:
Output file:
Time limit:
Memory limit:

standard input
standard output
1 second
256 megabytes

Жарасханда N саннан тұратын a массивы бар. Жарасхан берiлген массивтың әр санына тек бiр
операция қолдана алады. Операциялардың 3 түрi бар:
1. Санға бiрдi қосу.
2. Саннан бiрдi азайту.
3. Санға нөлдi қосу.
Массивтың әр санына берiлген үш операцияның тек бiреуiн ғана қолдана отырып, массивтегi ұқсас
элементтердiң санын барынша арттыру керек.

Input
Бiрiншi жолда бүтiн сан N берiлген. Келесi жолда массивтың элементтерi берiлген ai .

Output
Жауап ретiнде бiр сан шығарыңыз — берiлген операцияларды орындағаннан кейiнгi массивте кездесетiн ұқсас элементердiң саны.

Scoring
Бағалау 4 бөлiмнен тұрады:
1. 1 ≤ N ≤ 2. 10 ұпай.
2. 1 ≤ N ≤ 102 және 1 ≤ ai ≤ 10. 20 ұпай.
3. 1 ≤ N ≤ 105 және 1 ≤ ai ≤ 2. 20 ұпай.
4. 1 ≤ N ≤ 105 және 1 ≤ ai ≤ 105 . 50 ұпай.

Examples
standard input
7
3 1 4 1 5 9 2
10
1 2 3 4 5 6 7 8 9 10

standard output
4
3

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

Page 3 of 3

Информатика пәнi бойынша Республикалық олимпиада 2018-iң 2-шi кезеңi, 10-11 сынып, *2 КҮНI*
Қазақстан, Желтоқсан, 7, 2018

Problem A. Бөлiнедi ме?
Input file:
Output file:
Time limit:
Memory limit:

standard input
standard output
1 second
256 megabytes

ОМА санның 8-ге бөлiнгiштiгiнiң өз қасиетiн ойлап табуды ұйғарды. Егер берiлген санның цифрларының орындарын ауыстрығанда, бастаушы нөлдерсiз және 8-ге бөлiнетiн сандар тiзбегi табылатын
болса, ОМА бұл санды 8-ге бөлiнедi деп атайды.

Input
Бiрiншi жолда бүтiн n саны берiлген (1 ≤ n ≤ 103 ) - санның ұзындығы.
Екiншi жолда цифрлардан тұратын s жолы берiлген - тексеру қажет сан.

Output
Егер берiлген сан 8-ге бөлiнетiн болса YES, бөлiнбесе NO жазуларын шығарыңыз.

Examples
standard input

standard output

2
23

YES

3
101

NO

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

Page 1 of 3

Информатика пәнi бойынша Республикалық олимпиада 2018-iң 2-шi кезеңi, 10-11 сынып, *2 КҮНI*
Қазақстан, Желтоқсан, 7, 2018

Problem B. Депозит
Input file:
Output file:
Time limit:
Memory limit:

standard input
standard output
1 second
256 megabytes

Ақымақтар банкiнде Жарасханның депозитi бар. Депозиттiң ақша соммасы терiс болыу мүмкiн.
Банк Жарасханның депозитiн белгiлi пайызбен толтырады. Және де, Жарасхан ақша керек болған
кезде, депозиттiң бөлiгiн өзiне ала алады. Сол бөлiк пайыз арқылы белгiленедi.
Жарасханда барлық пайыз арқылы берiлген операциялар тарихы бар. Алғашында Жарасханның
депозитiнде соммасы s болатын ақша саны бар. Жарасхан ақшасын өзiне алған кезде - пайыз терiс
сан, банк толтырғанда - оң санға сейкес келедi.
Жарасханның мазалап жүрген бiр сұрағы - қай күнi депозиттегi сомма ең көп, және қай күнi депозиттегi сомма ең аз болғаны.
Дәл қазiр Жарасхан жұмыспен босамағандықтан, сол сұрақтың жауабын табуды сiзге бұйырды.

Input
Кiрiс файлының ең бiрiншi жолында, екi бүтiн сан берiлген n (1 ≤ n ≤ 25) - тарихтағы күндер
саны, s (−100 ≤ s ≤ 100) - Жарасханның депозитiндегi бастапқы сомма. Екiншi жолда n ai сандары
берiлген (−2 ≤ ai ≤ 2) - i-күн пайызының коэффицентi.

Output
Екi бүтiн сан - Жарасханның депозитiндегi ең көп және ең аз сомма болған күндердiң нөмiрлерiн
шығарыңыз. Жауапқа келетiн бiрнеше күн болса, сондай күндердiң iшiндегi бiрiншi күннiң нөмiрiн
шығарыңыз.

Scoring
Есеп 4 бөлiмнен тұрады:
1. n = 1. 13 ұпайға есептеледi.
2. 0 ≤ ai ≤ 2. 5 ұпайға есептеледi.
3. 1 ≤ n ≤ 15. 40 ұпайға есептеледi.
4. Берiлген шектеулер. 42 ұпайға есептеледi.

Examples
standard input

standard output

3 100
0.1 -0.4 2

2 3

3 100
0.5 1 2

0 3

2 100
1 -0.5

0 1

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

Информатика пәнi бойынша Республикалық олимпиада 2018-iң 2-шi кезеңi, 10-11 сынып, *2 КҮНI*
Қазақстан, Желтоқсан, 7, 2018

Problem C. Квадраттардың қосындысы
Input file:
Output file:
Time limit:
Memory limit:

standard input
standard output
1 second
256 megabytes

Ұзындығы n болатын екi массив берiлген. Берiлген массивке байланысты, сiзге q рет сұрақ қойылады. Сұрақтардың бәрiнiң үлгiсi бiрдей, тек сандары өзгередi. Әр сұрақта сiзге белгiлi бiр аралықты
анықтайтын l және r берiлген. Берiлген аралыққа кiретiн бүкiл a[i] мен b[i]-лардың айырмаларының
квадраттарының қосындысын шығаруыңыз керек.
a[i] мына аралықта болуы керек: al , al+1 , . . . , ar
b[i] мына аралықта болуы керек: bl , bl+1 , . . . , br

Input
Бiрiншi қатарда сiзге екi сан берiлген: n, q, (1 ≤ n, q ≤ 100000)
Екiншi және үшiншi қатарда, сәйкесiнше, a және b массивi берiлген.
(−100000 ≤ a[i], b[i] ≤ 100000), i = 1, 2, ... , n
Келесi q қатарда l, r берiледi: (1 ≤ l ≤ r ≤ n) Система оценки:
Тесттердiң 40 пайызында (1 ≤ n, q ≤ 100)
Тесттердiң 60 пайызында (1 ≤ n, q ≤ 100000)

Output
Әр сұраққа жауап шығарыңыз.

Example
standard input
3
1
1
2

1
0 5
2 3
3

standard output
8

Page 3 of 3

Информатика пәнi бойынша Республикалық олимпиада 2018-iң 2-шi кезеңi, 8-9 сынып, *2 КҮНI*
Қазақстан, Желтоқсан, 7, 2018

Problem A. Керемет сыйлық
Input file:
Output file:
Time limit:
Memory limit:

standard input
standard output
1 second
256 megabytes

Жақында Темiрланның туған күнi болды. Ең қызық сыйлықты оның досы Айсұлтан жасады. Айсұлтан Темiрланның керемет сандарды ұнататынын бiледi. Айсұлтанның ойынша, белгiлi бiр сан кез
келген басқа бiр бүтiн санның квадратына тең болса, ол сан керемет сан деп есептелiнедi. Мысалы,
0, 9, 121 — керемет сандар, ал 50, 3, 12 — керемет сандар емес.
Айсұлтанда қазiр n бүтiн саннан тұратын массив бар — a1 , a2 , a3 , ..., an . Сыйлық жасау үшiн, осы
тiзбектен Айсұлтан екi сан aj и ai (j < i) алып, олардың көбейтiндiсiнiң керемет сан бола алуын
тексередi. Егер де, көбейтiндi сан aj ∗ ai керемет болса, онда Айсұлтан көбейтiндiнi Темiрланға
сыйлай алады деген сөз.
Айсұлтан сыйлықты неше түрлi жолмен жасай алатынын анықтаңыз. Басқаша айтқанда, тiзбектен (aj , ai ) жұптарының арасында j < i болатын және aj ∗ ai көбейтiндiсi керемет сан болатын
жұптардың санын табыңыз.

Input
Бiрiншi жолда тек n берiлген — тiзбектiң ұзындығы (1 ≤ n ≤ 103 ).
Екiншi жолда бос орын арқылы жазылған n бүтiн саннан тұратын тiзбек a1 , a2 , a3 , ..., an берiлген —
Айсұлтанның тiзбегi (−1000 ≤ ai ≤ 1000).

Output
Тек бiр сан, яғни, Айсұлтанның неше жолмен сыйлық жасай алатынын шығаруыңыз керек.

Examples
standard input

standard output

4
1 0 1 1

6

2
-8 -2

1

3
1 16 4

3

1
0

0

Note
Бұл есеп 3 бөлiмнен тұрады:
1. 0 ≤ ai ≤ 1 барлық 1 ≤ i ≤ n үшiн.
2. n = 2, −1000 ≤ ai ≤ 1000.
3. Есептiң берiлгенiндегi шарттар.
Бiрiншi мысалда 6 жұптың барлығының көбейтiндiсi 0 немесе 1 санының квадраты болып табылады.
Екiншi мысалда тек бiр жұптың көбейтiндiсi ережеге сәйкес — бүтiн санның квадраты болатын 16
саны.
Page 1 of 4

Информатика пәнi бойынша Республикалық олимпиада 2018-iң 2-шi кезеңi, 8-9 сынып, *2 КҮНI*
Қазақстан, Желтоқсан, 7, 2018
Үшiншi мысалда (1, 16), (1, 4), (16, 4) жұптарының барлығының көбейтiндiсi бүтiн санның квадраты
болып табылады.
Төртiншi мысалда сыйлық құрай алатын бiр де бiр жұп жоқ.

Page 2 of 4

Информатика пәнi бойынша Республикалық олимпиада 2018-iң 2-шi кезеңi, 8-9 сынып, *2 КҮНI*
Қазақстан, Желтоқсан, 7, 2018

Problem B. Бөлiнедi ме?
Input file:
Output file:
Time limit:
Memory limit:

standard input
standard output
1 second
256 megabytes

ОМА санның 8-ге бөлiнгiштiгiнiң өз қасиетiн ойлап табуды ұйғарды. Егер берiлген санның цифрларының орындарын ауыстрығанда, бастаушы нөлдерсiз және 8-ге бөлiнетiн сандар тiзбегi табылатын
болса, ОМА бұл санды 8-ге бөлiнедi деп атайды.

Input
Бiрiншi жолда бүтiн n саны берiлген (1 ≤ n ≤ 103 ) - санның ұзындығы.
Екiншi жолда цифрлардан тұратын s жолы берiлген - тексеру қажет сан.

Output
Егер берiлген сан 8-ге бөлiнетiн болса YES, бөлiнбесе NO жазуларын шығарыңыз.

Examples
standard input

standard output

2
23

YES

3
101

NO

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

Page 3 of 4

Информатика пәнi бойынша Республикалық олимпиада 2018-iң 2-шi кезеңi, 8-9 сынып, *2 КҮНI*
Қазақстан, Желтоқсан, 7, 2018

Problem C. Депозит
Input file:
Output file:
Time limit:
Memory limit:

standard input
standard output
1 second
256 megabytes

Ақымақтар банкiнде Жарасханның депозитi бар. Депозиттiң ақша соммасы терiс болыу мүмкiн.
Банк Жарасханның депозитiн белгiлi пайызбен толтырады. Және де, Жарасхан ақша керек болған
кезде, депозиттiң бөлiгiн өзiне ала алады. Сол бөлiк пайыз арқылы белгiленедi.
Жарасханда барлық пайыз арқылы берiлген операциялар тарихы бар. Алғашында Жарасханның
депозитiнде соммасы s болатын ақша саны бар. Жарасхан ақшасын өзiне алған кезде - пайыз терiс
сан, банк толтырғанда - оң санға сейкес келедi.
Жарасханның мазалап жүрген бiр сұрағы - қай күнi депозиттегi сомма ең көп, және қай күнi депозиттегi сомма ең аз болғаны.
Дәл қазiр Жарасхан жұмыспен босамағандықтан, сол сұрақтың жауабын табуды сiзге бұйырды.

Input
Кiрiс файлының ең бiрiншi жолында, екi бүтiн сан берiлген n (1 ≤ n ≤ 25) - тарихтағы күндер
саны, s (−100 ≤ s ≤ 100) - Жарасханның депозитiндегi бастапқы сомма. Екiншi жолда n ai сандары
берiлген (−2 ≤ ai ≤ 2) - i-күн пайызының коэффицентi.

Output
Екi бүтiн сан - Жарасханның депозитiндегi ең көп және ең аз сомма болған күндердiң нөмiрлерiн
шығарыңыз. Жауапқа келетiн бiрнеше күн болса, сондай күндердiң iшiндегi бiрiншi күннiң нөмiрiн
шығарыңыз.

Scoring
Есеп 4 бөлiмнен тұрады:
1. n = 1. 13 ұпайға есептеледi.
2. 0 ≤ ai ≤ 2. 5 ұпайға есептеледi.
3. 1 ≤ n ≤ 15. 40 ұпайға есептеледi.
4. Берiлген шектеулер. 42 ұпайға есептеледi.

Examples
standard input

standard output

3 100
0.1 -0.4 2

2 3

3 100
0.5 1 2

0 3

2 100
1 -0.5

0 1

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

Информатика пәнi бойынша Республикалық олимпиаданың 3-шi кезеңi 2021-2022, 1шi тур
Қазақстан, 24 наурыз, 2022

Есеп A. Спорттық бағдарламаушылар
Енгiзу файлының аты:
Шығару файлының аты:
Уақыт шектеу:
Жадыға шектеу:

standard input
standard output
1 second
256 megabytes

Қазақстанның спорттық бағдарламаушылар ассоциациясы жүгiруден жарыс өткiздi. Жарысқа N
жүгiрушi қатысты. Басында жүгiрушiлер 1-ден N -ге дейiн бiрi артынан бiрi орналасты.
Жарыс басталғанда олар сол реттi бұзбай жүгiре бастады. Нөмiрi 1 болатын жүгiрушi бiрiншi, ал
нөмiрi N болатын жүгiрушi — соңғы. Бiрақ қандай жарыста ешкiм ешкiмдi озбайды? Бiр жүгiрушiнiң бауы шешiлiп кеткенде ғана олардың ретi өзгере алады. Жүгiрушi бауын байлап жатқанда
одан кейiн келе жатқан бiрнеше адам оны озып кетуi мүмкiн.
Мысалы, N = 5 жүгiрушi жарысқа қатысқан кезде бастапқы қатар осындай болады: 1 2 3 4 5. Бiраз
уақыттан кейiн 2-шi жүгiрушiнiң бауы шешiлiп кеттi дейiк. Ол бауын байлап жатқан уақытта оны
екi жүгiрушi озып кеттi дейiк. Онда олардың ендiгi ретi осындай болады: 1 3 4 2 5. Егер бұдан кейiн
4-шi жүгiрушiнiң бауы шешiлсе, және сол үшiн оны бiр адам озып кетсе, жаңа рет мынадай болады:
1 3 2 4 5.
Сiзге N және жүгiрушiлердiң мәреге келген ретi берiледi. Сiзге ең кем дегенде неше жүгiрушiнiң
бауы шешiлiп кеткенiн айту керек.

Енгiзу файлының форматы
Бiрiншi жолда бiр бүтiн сан N (1 ≤ N ≤ 200000) — жүгiрушiлердiң саны берiледi.
Екiншi жолда N бүтiн сан p1 , p2 , . . . , pN (1 ≤ pi ≤ N , i 6= j болса pi 6= pj ) берiледi. Мәреге бiрiншi
болып p1 келдi, екiншi болып p2 , . . . , соңғы болып pN келдi.

Шығару файлының форматы
Бiр бүтiн сан — есептiң жауабын шығарыңыз.

Бағалау жүйесi
Бөлiмдер
0
1
2
3
4

Қосымша шектеулер
Примеры
n=2
n≤8
n ≤ 2000
—

Ұпайлар
0
15
20
30
35

Қажеттi бөлiмдер
—
—
0, 1
0, 1, 2
0, 1, 2, 3

Мысалдар
standard input

standard output

6
1 2 5 4 3 6

2

3
1 2 3

0

Түсiнiктеме
Бiрiншi мысалды қарастырайық. Басында қатар: 1 2 3 4 5 6. Мүмкiн жағдайлардың бiрi:
4-шi жүгiрушiнiң бауы шешiлiп кеттi, байлап жатқанда 5 оны озып кеттi. Ендiгi рет: 1 2 3 5 4 6
болды. Одан кейiн 3-шi жүгiрушiнiң бауы шешiлiп кеттi және оны 5 пен 4 озып кеттi. Ендiгi қатар
1 2 5 4 3 6 болды.
Page 1 of 4

Информатика пәнi бойынша Республикалық олимпиаданың 3-шi кезеңi 2021-2022, 1шi тур
Қазақстан, 24 наурыз, 2022
Екiден аз адамның бауы шешiлiп кетсе, онда берiлген қатарға қол жеткiзу мүмкiн емес болатынын
көрсетуге болады.

Page 2 of 4

Информатика пәнi бойынша Республикалық олимпиаданың 3-шi кезеңi 2021-2022, 1шi тур
Қазақстан, 24 наурыз, 2022

Есеп B. Бiрегей есеп
Енгiзу файлының аты:
Шығару файлының аты:
Уақыт шектеу:
Жадыға шектеу:

standard input
standard output
1 second
512 megabytes

Аңыз адам «LeGross» Арлан өз жанкүйерлерiне келесi есептi ұсынды:
Сiзге мөлшерi n және m болатын бүтiн сандардан тұратын a және b массивтерi берiлген. b массивiнiң
барлық сандары әр түрлi.
Сiзге келесi шарттар орындалатындай a массивiн неше әдiспен m бөлiкке (l1 , r1 ), . . . , (lm , rm ) бөлуге
болатының табу керек:
• a массивының кез-келген элементi дәл бiр бөлiкте жатады.
• Кез келген 1 ≤ i ≤ m үшiн, bi саны (ali , . . . , ari ) сандарының арасында дәл бiр рет кездеседi
(бөлiктер солдан оңға қарай нөмiрленедi).
Есептiң жауабы өте үлкен болуы мүмкiн, сол үшiн оның 998244353 санына бөлгендегi қалдығын
шығару қажет.

Енгiзу файлының форматы
Бiрiншi жолда екi бүтiн сан — n және m (1 ≤ n, m ≤ 5 · 105 ) берiлген.
Екiншi жолда n бүтiн сандар a1 , a2 , . . . , an (1 ≤ ai ≤ 5 · 105 ) — a массивi берiлген.
Үшiншi жолда m бүтiн сан b1 , b2 , . . . , bm (1 ≤ bi ≤ 5 · 105 ) — b массивы берiлген.

Шығару файлының форматы
Арланның есебiнiң жауабын 998244353 санына бөлгендегi қалдығын шығарыңыз.

Бағалау жүйесi
Бөлiмдер
0
1
2
3
4

Қосымша шектеулер
Мысалдар
m = 1, n ≤ 105
n, m ≤ 300
n, m ≤ 3000
—

Ұпайлар
0
13
25
22
40

Қажеттi бөлiмдер
—
—
0
2
3

Мысалдар
standard input

standard output

4 2
1 7 7 3
7 3

1

2 1
1 1
1

0

Түсiнiктеме
Бiрiншi мысалды жалғыз әдiс бар, ол — (1, 2) және (3, 4) бөлiктерiне бөлу.
Page 3 of 4

Информатика пәнi бойынша Республикалық олимпиаданың 3-шi кезеңi 2021-2022, 1шi тур
Қазақстан, 24 наурыз, 2022

Есеп C. Cөздi табу
Енгiзу файлының аты:
Шығару файлының аты:
Уақыт шектеу:
Жадыға шектеу:

standard input
standard output
3 seconds
256 megabytes

Сiзге ұзындығы n болатын, кiшi латын әрiптерi және ‘ ?’ таңбаларынан тұратын s сөзi берiледi.
Сондай-ақ, сiзде m шарт бар. Әр шарт l1 , l2 және x үш бүтiн сандарымен сипатталады. Бұл шарт
(sl1 . . . sl1 +x−1 ) iшкi жолы (sl2 . . . sl2 +x−1 ) iшкi жолына тең болу керек екенiн бiлдiредi.
Бүкiл m шарт орындалатындай, әрбiр ‘ ?’ таңбасын кiшi латын әрiпiне ауыстыру керек. Барлық
шарттарды қанағаттандыратын сөздердiң iшiнен лексикографиялық минималды сөздi табыңыз.

Енгiзу файлының форматы
Бiрiншi жолда n(1 ≤ n ≤ 300000) бүтiн саны берiлген.
Екiншi жолда ұзындығы n болатын s сөзi берiлген.
Үшiншi жолда m(1 ≤ m ≤ 300000) бүтiн саны берiлген.
Келесi m жолда l1 , l2 және x (1 ≤ l1 , l2 ≤ n − x + 1) үш бүтiн сандары берiлген. Бұл үштiк
(sl1 . . . sl1 +x−1 ) iшкi жолы (sl2 . . . sl2 +x−1 ) iшкi жолына тең болу керек екенiн бiлдiредi.

Шығару файлының форматы
Барлық шарттарды қанағаттандыратын лексикографиялық минималды сөздi шығарыңыз. Егер
мұндай сөз болмаса, −1 шығырыңыз.

Бағалау жүйесi
Бөлiмдер
0
1
2
3
4
5

Қосымша шектеулер
Ұпайлар Қажеттi бөлiмдер
n, m ≤ 10, si = {a, b, ?}
7
—
n, m ≤ 1000, count(‘?0 ) = 0
8
—
0
n, m ≤ 300000, count(‘? ) = 0
20
1
count(‘?0 ) сөздегi
0
count(‘? ) ≤ 100
17
1, 2
n, m ≤ 1000
13
0
n, m ≤ 300000
35
0, 1, 2, 3, 4
сұрақ белгiлерiнiң санын бiлдiредi.

Мысалдар
standard input

standard output

10
a?b?b???b?
3
1 4 3
7 9 2
3 10 1

abbabbbbbb

6
a????b
5
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1

-1

Page 4 of 4