Есеп A. Кезек

Бекжан қызықты кезек туралы естіді. Бұл кезекте ықылассыз кассир жұмыс істейді. Бұл кассир онымен ұрсысқанда ғана-ақ клиентке қызмет етеді екен. Кейде кезектегі адамдар маңызды кездесуге кешіккендерін түсініп, кезекке қарамай кассирге өтіп, онымен ұрсысады. Ұрсысқаннан кейін кассир сол клиентке қызмет етіп, оны жібереді. Мысалы, кезексіз өткен адамның аты Ануар болсын. Онда Ануардың алдында кезекте турған әр адам Ануарға өзінің наразылығын белгілі саны бар сөзбен білдіреді. Сөздер саны әр адам үшін белгіленген. Бекжан әр кезексіз өткен адам өзі туралы қанша наразылық сөзін еститінін білгісі келді. Енгізілген мәліметтердің бірінші жолында $N$ бүтін саны — кезектегі әрекеттердің саны берілген ($2 \leq N \leq 5 \cdot 10^5$). Әр әрекеттің сипаттамасы $type$ бүтін санынан басталады ($1 \leq type \leq 2$). Егер $type = 1$ болса, одан кейін $w$ бүтін саны беріледі ($1 \leq w \leq 10^9$). Бұл сұраныс түрі кезекке жаңа адам келгенін білдіреді. Жаңадан келген адамның нөмірі оның алдында нөмір ретінде пайдаланылмаған ең кіші бүтін оң сан болады және ол наразылығын көрсеткендегі сөздер саны $w$ болып саналады. Егер $type = 2$ болса одан кейін $x$ саны беріледі. Бұл сұраныс түрі кезекте тұрған нөмірі $x$ адам кезексіз өткенін білдіреді. Сұраныс кезінде бұл адам кезекте бар екендігіне кепілдік беріледі. Кезектен тым болмаса бір адамның шығатына кепілдік беріледі. Кезексіз өткен әр адам қанша наразылық сөз санын еститінін шығарыңыз.

1. $N \le 20$, $w \le 1000$. Топ бөлігінің бағасы: $10$ ұпай.
2. $N \le 10000$. Топ бөлігінің бағасы: $40$ ұпай.
3. $N \le 500000$. Топ бөлігінің бағасы: $50$ ұпай.

Вход

2
1 1
2 1

Ответ

0

Вход

8
1 8
1 1
1 9
2 2
1 2
1 4
2 5
1 3

Ответ

8
19

Бірінші мысалда кезекке бір адам келіп, кассирмен ұрcысып, ешкімнен наразылық сөзін естіген жоқ. Екінші мысалда кезекке басында $8$, $1$ және $9$ наразылық сөздерін айтатын адамдар келеді. Олардың нөмір сандары тиісінше $1$, $2$ және $3$ болады. Одан кейін нөмірі $2$-ші адам кезексіз өтіп, нөмірі $1$-ші адамның наразылық сөздерін естиді ($8$ сөз). Бұл адамнан кейін кезекке наразылық сөз саны $2$ және $4$ адамдар келіп, $4$-ші және $5$-ші нөмірлерді тиісінше алады. Олардан кейін нөмірі $5$-ші адам кезексіз өтіп, нөмірлері $1$-ші, $3$-ші және $4$-ші адамдардан наразылық сөз естиді ($19$ сөз). Ең аяғында кезекке нөмірі $6$-шы және сөз саны $3$ адам қосылады.

(Алмалар)
Тима жәңе оның $N - 1$ достары алма жинады. Оларды $1$—ден $N$—ге дейінгі сандармен нөмірлейміз. Тиманың нөмері $1$. Тима өзіндегі алмалар саны қалғандарынан көп екенің байқап, оларға өз алмасымен бөлісетін болды. Ол кімде қанша алма бар, оған соншама алма берді. Мысалы, біреуде $X$ алма болса, Тима оған $X$ алма берді. Одан кейін нөмірі $2$—ші адам кімде қанша алма бар, соған сонша алма берді. Осылай $N$-ші адамға дейін жасады. Соныңда барлығында бірдей алма саны болды. Тима бастапқысында кімде қанша алма болғаның білгісі келеді. Ол басында өзінде $A_1$ алма болғанын біледі. Бірінші жолда бір бүтін сан берілген $T(1\le T \le 1000)$ — тесттер саны. Келесі $T$ жолда екі бүтін саннан жазылған $N$ ($1 \le N \le 50$),$1\le A_1\le 10^{16}$. $T$ — жол шығарыңыз, егер мұндай жағдай мүмкін емес болса $-1$ шығарыңыз. Олай болмаса $N$ бүтін $A_1,A_2, .., A_N$ сандарың шығарыңыз. Егер есептің бірнеше жауабы болса, кез келгенін шығарыңыз. Есеп төрт бөлімнен тұрады:

1. $1 \le T \le 50, N = 2, 1 \le A_1 \le 10^6$. Бұл бөлім $10$ ұпайға бағаланады.
2. $1 \le T \le 50, N = 3, 1 \le A_1 \le 10^9 $. Бұл бөлім $15$ ұпайға бағаланады..
3. $T = 1, 1 \le N \le 50, 1 \le A_1 \le 10^5$. Бұл бөлім $30$ ұпайға бағаланады.
4. $1 \le T \le 1000, 1 \le N \le 50, 1 \le A_1 \le 10^{16}$. Бұл бөлім $45$ ұпайға бағаланады.

Вход

2
3 13
2 10

Ответ

13 7 4 
10 6 

Бірінші тест: Басында 13, 7, 4. 1-шіден кейін : 2, 14, 8. 2-шіден кейін : 4, 4, 16. 3-шіден кейін: 8,8,8.

(Саперлер)
Екі сапер миналы алаңдағы миналарды тауып, оларды қауіпсіздендіру керек. Алаң өлшемдері $n \times m$ ($n$ жол және $m$ баған) кесте түрінде берілген және осы кестенің әрбір шаршысында көбінде 1 мина бола алады. Кестенің жолдары жоғарыдан төмен $1$-ден $n$-ге дейін және бағандары солдан оңға қарай $1$-ден $m$-ге дейін нөмірленген. Саперлер жұмысты мүмкіндігінше әділ жолмен бөлгісі келеді. Жұмыс әділ болу үшін алаң екі саперге бірдей бөліктерге (қандай да бір бұрғанда беттесу керек) бөліну керек және әділдік екі бөліктегі миналардың сандарындағы айырмашылығымен өлшенеді. Алаңды тек қана шаршылардың қабырғаларымен ғана бөлуге болады және де бөліктер өзара байланысты болу керек, яғни бір бөліктің әрбір шаршысынан кез келген басқа шаршысына қабырғасы бойынша көршілес шаршылар арқылы жету мүмкін болу керек. Сіздің тапсырмаңыз алаңды екі саперге мүмкіндігінше әділ жолмен бөліп беретін программа жазу. $m$ санының жұп екендігіне кепілдік берілген. Бірінші жолда екі бүтін $n$($1\le n \le 1000$) және $m(1 \le m \le 1000)$ сандары жазылған. Келесі $n$ жолдың әрқайсысы $m$ символдан тұрады, бұл символдар алаңды сипаттайды. Егер символ «.» болса, бұл шаршыда мина жоқ және егер символ «*» болса, бұл шаршыда мина бар дегенді білдіреді. Жауап ретінде «1» және «2» символдарынан тұратын әрқайсысы $m$ символдан құралған $n$ жол шығару керек. «1» символы осы шаршы бірінші сапердікі және «2» символы осы шаршы екінші сапердікі екенін білдіреді. Бұл есепте 100 тест. Әр өткен тест үшін қатысушы $1$ ұпай алады. Вход

5 8
**.....*
...*.*..
*..*....
*....*..
.......*

Ответ

11111111
22222211
22112211
22111111
22222222

(Әдемі тізбек)
Тізбекше деп басқа тізбектен кейбір элементтерін өшіріп және басқа элементтердің орнын ауыстырмай алуға болатын тізбекті атаймыз. Сізге көлемі $n$: $a_1, a_2, \ldots, a_n$ және көлемі $m$: $b_1, b_2, \ldots, b_m$ болатын екі тізбек берілген. $k$ бүтін саннан тұратын $c_1, c_2, \ldots, c_k$ тізбегін әдемі деп атаймыз егерде төмендегі шарттар орындалса: \begin{itemize}

k тақ сан.

Барлық $1 < 2 * j < k$ үшін $c_{2*j-1} < c_{2 * j}$ және $c_{2*j+1} < c_{2 * j}$.

$c_1, c_2, \ldots, c_k$ тізбегі $a_1, a_2, \ldots, a_n$ тізбегінің тізбекшесі.

$c_1, c_2, \ldots, c_k$ тізбегі $b_1, b_2, \ldots, b_m$ тізбегінің тізбекшесі.

\end{itemize} Ең үлкен әдемі тізбектің көлемін және ең үлкен әдемі әр түрлі тізбектің санын $10^9 + 9$ санына бөлгендегі қалдығын табу керек. Бірінші жолда бір бүтін сан берілген $n$ ($1 \le n \le 10^4$)~— $a$ тізбегінің көлемі. Екінші жолда $n$ бүтін сан жазылған $a_i$ ($1 \le a_i \le 20000$)~— $a$ тізбегі. Үшінші жолда бір бүтін сан берілген $m$ ($1 \le m \le 10^4$)~— $b$ тізбегінің көлемі. Төртінші жолда $m$ бүтін сан жазылған $b_i$ ($1 \le b_i \le 20000$)~— $b$ тізбегі. Екі тізбектегі сандар бір бос орын арқылы берілген. Екі бүтін сан шығарыңыз - берілген есептің жауабын. Егер шешімі жоқ болса екі нөл шыгарыңыз. Есеп төрт бөлімнен тұрады:

1. $1 \leq n \leq 20$, $1 \le m \le 10$. Бұл бөлім $9$ ұпайға бағаланады.
2. $1 \leq n \leq 1000$, $1 \le m \le 20$. Бұл бөлім $9$ ұпайға бағаланады.
3. $1 \leq n \leq 500$, $1 \le m \le 500$. Бұл бөлім $28$ ұпайға бағаланады.
4. $1 \leq n \leq 10^4$, $1 \le m \le 10^4$. Бұл бөлім $54$ ұпайға бағаланады.

s Вход

1
1
1
2

Ответ

0 0

Вход

7
1 5 3 4 2 5 2
5
1 3 5 4 2

Ответ

3 6

Вход

4
1 1 3 2
4
1 3 2 2

Ответ

3 1

(Аударулар)
Үстелдің үстінде $K$ қағаз жатыр. Сізге $N$ саны берілген. Әр қағазда 1 ден $N$-ге дейінгі әр сан бір реттен жазылған. Бірақ сандардың кейбірі қағаздың көрінетін бетінде ал қалғаны артқы бетінде жазылған. Сіздің тапсырмаңыз - осы қағаздардың кейбірін аудару, сол аударулардан кейін қағаздың көрінетін жақтарындағы әр түрлі сандардың санын көп қылу. Бірінші қатарда $N$ және $K$ сандары берілген($N \times K\le 10^6$, $ N \ge 1 $ және $K \ge 1$). Келесі $K$ қатарда қағаздардың сипаттамалары берілген. $i+1$-ші қатарда $i$-ші кағаздың көрінетін бетіндегі сандар саны $m$($0 \le m \le N$) жазылған. Одан кейін $m$ сан $i$-ші қағаздың көрінетін бетіндегі сандар, әр сан $1$-ден $N$-ге дейін. $K$ символдан туратын қатар шығарыңыз. $i(1 \le i \le K)$ символ 1-ге тең егерде аудару керек болса, олай болмаса 0. Егер бірнеше жауап болса кез келгенін шығарыңыз. Есеп бес бөлімнен тұрады:

1. $1 \leq N \leq 10$, $1 \le K \le 10$. Бұл бөлім $11$ ұпайға бағаланады.
2. $1 \leq N \le K$. Бұл бөлім $8$ ұпайға бағаланады.
3. $1 \leq N \leq 100$. Бұл бөлім $15$ ұпайға бағаланады.
4. $1 \leq N \times K \leq 5 \cdot 10^4$. Бұл бөлім $30$ ұпайға бағаланады.
5. $1 \leq N \times K \leq 10^6 $. Бұл бөлім $36$ ұпайға бағаланады.

s Вход

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

Ответ

1111

Вход

6 2
3 1 3 4
3 1 2 4

Ответ

01

(Бұл данаққа берген соңғы есебім:))
Бастапқысында жалғыз нөмері 1 төбесінен тұратын екілік данақ берілген. Сізге келесі түрдегі $M$ тапсырысты орындау керек:

• $Grow$ $V$, $V$ төбесінің бұтағындағы барлық $leaf$ деген листтарына нөмері $2 \cdot leaf$ және $2 \cdot leaf+1$ болатын төбелерді қосу.
• $Sum$ $V,$ $V$ төбесінің бұтағындағы барлық төбелердің нөмерлерінің қосындысының $10^9+7$ бөлгендегі қалдығын табу керек.

Сіз бұл есепті шығара аласыз ба? Бірінші жолда жалғыз бүтін сан берілген $M$ $(1 \leq M \leq 2 \cdot 10^5)$ — тапсырыстардың саны. Келесі $M$ жолда тапсырыстардың сипаттамасы берілген. Әрбір тапсырыс бір жолмен сипатталады $Op$ $V$, мұндағы $Op$ — тапсырыстың түрі ($Grow$ немесе $Sum$), ал $V$ — төбенің нөмері. Барлық $Sum$ деген тапсырыстың түрі үшін керек қосындыны шығарыңыз. Берілген ретімен шығарыңыз. Есеп 7 бөлімнен тұрады:

1. $1 \leq M \leq 20$. Бұл бөлім $15$ ұпайға бағаланады.
2. $1 \leq M \leq 2 \cdot 10^5$, $V = 1$ во всех запросах $Grow$ $V$. Бұл бөлім $10$ ұпайға бағаланады.
3. $1 \leq M \leq 2 \cdot 10^5$, $V = 1$ во всех запросах $Sum$ $V$. Бұл бөлім $10$ ұпайға бағаланады.
4. $1 \leq M \leq 10^3$. Бұл бөлім $15$ ұпайға бағаланады.
5. $1 \leq M \leq 2 \cdot 10^5$, барлық $Sum$ тапсырыстары $Grow$ тапсырыстарынан кейін орындала. Бұл бөлім $15$ ұпайға бағаланады.
6. $1 \leq M \leq 2 \cdot 10^5$, $1 \le V \le 10^6$. Бұл бөлім $15$ ұпайға бағаланады.
7. $1 \leq M \leq 2 \cdot 10^5$, $1 \le V \le 10^9$. Бұл бөлім $20$ ұпайға бағаланады.

\Example Вход

5
Grow 1
Grow 1
Grow 2
Sum 1
Sum 4

Ответ

66
21

(Құпиялы алгоритмдер)
Timart елінде $N$ қала және $M$ екіжақты жол бар. Қалалар $1$-ден $N$-ге дейінгі сандармен белгіленген. Осы жолдар арқылы әр қаладан кез келген қалаға баруға болады. Андрей құпиялы алгоритмдер жазылған бүктеме қағаздарды Timart елінің қалаларында жасырып қойды. $i$-ші қалада $A_i$ бүктеме қағаз жасырылған. Рамазан осы бүктеме қағаздарды ұрлап кеткісі келеді. Рамазан өзі тұрған қаладағы барлық бүктеме қағаздарды ұрлап кете алады. Ол кез келген қаладан бастап ұрлай алады. Рамазан Андрейге ұсталып қалмас үшін, бір жолмен қатарынан екі рет жүрмейді. Әр қаладағы бүктеме қағаздарды бір рет ғана ұрлап кетуге болады, бірақ бір қалаға бірнеше рет баруға болады. Рамазан ең көп дегенде неше бүктеме қағаз ұрлай алады? Бірінші жолда екі бүтін сан берілген $N$, $M$ ($1 \le N \le 5 \cdot 10^5$, $0 \le M \le 5 \cdot 10^5$). Екінші жолда $N$ бүтін сан жазылған $A_1, A_2, \ldots, A_N$, мұндағы $A_i$ ~— $i$-ші қаладағы бүктеме қағаздардың саны. Келесі $M$ жолда $2$ бүтін саннан жазылған $u_i$, $v_i$ ($1 \le u_i, v_i \le N, u_i \neq v_i$)~— $u_i$ және $v_i$ қалаларын қосатын жол бар. Екі әр түрлі қаланы байланыстыратын ең көп дегенде бір ғана жол болуы мүмкін. Осы жолдар арқылы әр қаладан кез келген қалаға жетуге болады. Бір бүтін сан шығарыңыз - берілген есептің жауабын. Есеп бес бөлімнен тұрады:

1. $1 \le N \le 100$,$M = \frac{N \cdot (N - 1)}{2}$, $1 \le A_i \le 300$, барлық $1 \le i \le N$ үшін. Бұл бөлім $7$ ұпайға бағаланады.
2. $1 \le N \le 12$, $0 \le M \le 66$, $1 \le A_i \le 300$, барлық $1 \le i \le N$ үшін. Бұл бөлім $12$ ұпайға бағаланады.
3. $1 \le N \le 10^5$, $M = N - 1$, $1 \le A_i \le 10^9$, барлық $1 \le i \le N$ үшін. Бұл бөлім $12$ ұпайға бағаланады.
4. $3 \le N \le 10^5$, $M = N$, $1 \le A_i \le 10^9$, барлық $1 \le i \le N$ үшін. Бұл бөлім $25$ ұпайға бағаланады.
5. $1 \le N \le 5 \cdot 10^5$, $0 \le M \le 5 \cdot 10^5$, $1 \le A_i \le 10^9$, барлық $1 \le i \le N$ үшін. Бұл бөлім $44$ ұпайға бағаланады.

\Example Вход

8 8
1 2 3 4 5 6 7 8
1 2
2 3
2 4
2 5
5 6
6 7
7 8
8 5

Ответ

35

(Тима және дәрежелер қосындысы)
Тимада $N$ бүтін саны және $N$ саннан тұратын $A$ массивы бар. Тағыда ода $M$ және $K$ бүтін сандары бар. Барлық $1$—ден $N$-$M$+$1$—ге дейінгі $i$ бүтін саны үшін Тима мынадай өрнектің $1^K \cdot A_{i} + 2^K \cdot A_{i + 1} + \cdots + M^K \cdot A_{i + M - 1}$ мәнің санағысы келеді. Оған осы есепті шығаруға көмектесіңіз. Бірінші жолда үш бүтін сан берілген $N$($1 \le N \le 10^5$),$M$($1 \le M \le N$) және $K$($0 \le K \le 20$). Екінші жолда $N$ бүтін сан берілген $A_1,A_2, \cdots, A_N$ ($1 \le A_i \le 10^9$). $N$-$M$+$1$ жол шығарыңыз, $i$-ші жолда $1^K \cdot A_{i} + 2^K \cdot A_{i + 1} + \cdots + M^K \cdot A_{i + M - 1}$ өрнегінің мәнің $10^9 + 7$ бөлгендегі қалдығын шығарыңыз. Есеп бес бөлімнен тұрады:

1. $1 \le N \le 100, 0 \le K \le 3,1 \le A_i \le 10$. Бөлім $7$ ұпайға бағаланады.
2. $1 \le N \le 10^4, 0 \le K \le 20,1 \le A_i \le 10^9$. Бөлім $12$ ұпайға бағаланады..
3. $1 \le N \le 10^5, 0 \le K \le 1,1 \le A_i \le 10^9$. Бөлім $13$ ұпайға бағаланады.
4. $1 \le N \le 10^5, K = 2,1 \le A_i \le 10^9$. Бөлім $20$ ұпайға бағаланады.
5. $1 \le N \le 10^5, 0 \le K \le 20,1 \le A_i \le 10^9$. Бөлім $48$ ұпайға бағаланады.

Вход

5 3 2
1 2 3 4 5

Ответ

36
50
64

Вход

3 2 0
7 3 2

Ответ

10
5

Бірінші мысалға түсіндірме: $i = 1$ болғанда, $1^K \cdot A_1 + 2^K \cdot A_2 + 3^K \cdot A_3$ = $1^2 \cdot 1 + 2^2 \cdot 2 + 3^2 \cdot 3 = 1 + 8 + 27 = 36$. $i = 2$ болғанда, $1^K \cdot A_2 + 2^K \cdot A_3 + 3^K \cdot A_4$ = $1^2 \cdot 2 + 2^2 \cdot 3 + 3^2 \cdot 4 = 50$. $i = 3$ болғанда, $1^K \cdot A_3 + 2^K \cdot A_4 + 3^K \cdot A_5$ = $1^2 \cdot 3 + 2^2 \cdot 4 + 3^2 \cdot 5 = 64$.