(Сиқырлы матрица)
Жас сиқыршы Асхат жаңа сиқырдың жаңа түрін ойлап тапты — енді ол кез келген матрицаны оның префикс қосындысымен ауыстыра алады!
   Жаңадан меңгерген қабілетіне сенімді болу үшін, ол біраз жаттығамын деп шешті. Ол өлшемдері шексіз үлкен, барлық элементтері $1$ саны болатын матрицаны алып, сол матрицаға өте көп рет жоғарыда айтылған сиқырды қолданды.
   Бұл есепте сіз өзіңіздің бағдарламалау қабілетіңіз сиқырдан еш кем емес екенін дәлелдеу. Сізге саны өте көп сұраулар беріледі. Солардың әрқайсысына бастапқы матрицаға жоғарыда келтірілген сиқырды $k$ рет қолданғаннан кейін, матрицаның $i$-жолындағы және $j$-қатарындағы тұрған санның мәнін анықтаңыз. Ол сан өте үлкен болуы мүмкін болғандықтан 1000000007-ге бөлгендегі қалдығын шығарыңыз. Бірінші жолда жалғыз оң сан $Q \; (1 <= Q <= 10^5)$ берілген — сіздің бағдарламаңызға берілетін сұраулардың саны.
   Келесі берілген $Q$ жолдың әрқайсысы бағдарламаға келген кезекті сұрауды үш сан арқылы сипаттайды: сәйкесінше жол нөмірі $i$, қатар нөмірі $j$ және сиқырдың неше рет қолданылғанын көрсететін сан $k$ $(1 <= i, j, k <= 10^5)$. Келесі $Q$ жолдың әрқайсысында бір саннан шығарыңыз — сиқырды $k$ рет қолданғаннан кейін, матрицаның $i$-жолындағы және $j$-қатарындағы тұрған санның мәннің 1000000007-ге бөлгендегі қалдығы. 1-бөлім (10 ұпай) — $1 <= Q <= 10, 1 <= i, j, k <= 100$ 2-бөлім (10 ұпай) — $1 <= i, j, k <= 100$ \par 3-бөлім (10 ұпай) — $1 <= i, j, k <= 10^3$ \par 4-бөлім (10 ұпай) — $i = 1$ немесе $j = 1$ \par 5-бөлім (10 ұпай) — $k = 1$ \par 6-бөлім (50 ұпай) — қосымша шарттарсыз. \exmpfile{example.01}{example.01.a}% \exmpfile{example.02}{example.02.a}%
   Еске сала кетсек, матрица — бүтін сандардан тұратын екі өлшемді массив (басқаша айтқанда, кесте). Мысалы, өлшемі 3x4 болатын матрица: \begin{center} \begin{tabular}{|c|c|c|c|} \hline 1 & 2 & 3 & 4\\ \hline 4 & 7 & 0 & -2\\ \hline 5 & 9 & 2 & 6\\ \hline \end{tabular} \end{center}
   Префикс қосынды — кез келген элементі осы сәйкес келетін тормен және қарама-қарсы бұрышы $(1, 1)$ торымен шектелген тіктөртбұрышағы сандардың қосындысы болатын матрица. Басқаша айтқанда, $A$ матрицасының префикс қосындысы деп $B$ матрицасын алсақ, кез келген $i > 0, \; j > 0$ үшін келесі шарт орындалуы қажет: \[B_{i, j} = A_{i, j} + B_{i - 1, j} + B_{i, j - 1} - B_{i - 1, j - 1}\]
   $B$ матрицасының $i = 0$ және $j = 0$ болатын ұяшықтарында нөл жазылған.
   Келесі матрица үшін \begin{center} \begin{tabular}{|c|c|c|c|} \hline 1 & 2 & 0 & 1\\ \hline 4 & 1 & 5 & 9\\ \hline 3 & 2 & 6 & 1\\ \hline 0 & 7 & 2 & 4\\ \hline \end{tabular} \end{center}
   Префикс қосынды матрица төмендегідей болады: \begin{center} \begin{tabular}{|c|c|c|c|} \hline 1 & 3 & 3 & 4\\ \hline 5 & 8 & 13 & 23\\ \hline 8 & 13 & 24 & 35\\ \hline 8 & 20 & 33 & 48\\ \hline \end{tabular} \end{center}

Есеп B. Machine Vision

\includegraphics[width=0.25\textwidth,natwidth=360,natheight=300,height=100pt]{abbey_road.png} Өзінің жаңа стартапы үшін НурлашКО, суреттен мәтін шығаруды талап етті. Прототип кезеңінде болғандықтан, Muugle Cloud Vision API платформасындағы дайын шешімді қолдануды жөн көрді. Алайда, түсінікті мәтінді алумен бір мәселе туып отыр. Жіберілген суретке мәтіннің орнына бөлек сөздер мен оладрың орналасқан төртбұрышты аумақ ретінде жауап келеді. НурлашКОға сіздің көмегіңіз қажет — сөздерді кере орналастырып, мәнді мәтін алуға көмектесіңіз. Ресми түрде, сізге $N$ жақтары координаттар өстеріне қатар төртбұрыштар мен әр қайсысына сәйкес сөз берілген. $B$ төртбұрышы мен $A$ төртбұрышының проекцияларының ординаттар өсіне қараған қиылысының ауданы оң болғанда және $B$ $A$-ға ең жақын болып табылғанда тек сол және сол ғана жағдайда $B$ $A$-ға көрші болып аталады. Бір біріне көршілер арқылы жетуге болатын ең үлкен төртбұраштар жиыны жол болып табылады. Жолдың биіктілігі сол жолдағы ең биік төртбұрыштың биіктілігімен белгіленеді. Жолдарды биіктігі бойынша кему ретімен шығарыңыз. Әр жолдың ішіндегі солдан оңға қарай жатқан төртбұрыштардың сәйкес келген сөздерді шығарыңыз. Ешбір екі төртбұрыш бір-бірімен қиылыспайтынына, бірақ бір-біріне тиуі мүмкін екеніне кепілдік беріледі. Бірінші жолда бір бүтін сан $N(1 <=q N <=q 2*10^5)$ — төртбұрыштар саны жазылған. Келесі $N$ жолда әрбір төртбұрыш сипатталады. Әр төртбұрыш сипаттамасында кіші латын әріптері мен сандардан тұратын жол $s_i (1 <=q |s_i| <=q 100000)$ және төрт бүтін сан $xl_i$, $yb_i$, $xr_i$, $yt_i$ $(1 <=q xl_i, yb_i, xr_i, yt_i <=q 10^9)$ — төртбұрышқа сәйкес сөз бен сол жақ төменгі және оң жақ жоғарғы бұрыштарының координаталары жазылған. Барлық $s_i$ ұзындықтарының қосындысы $2*10^5$ аспайтынына кепілдік беріледі. Әр жолды бөлек жолда, және жол ішіндегі сөздерді бос орынмен жазыңыз. Есеп екі бөлімнен тұрады:

1. $1 <=q N <=q 2000$. $30$ ұпайға есептеледі.
2. $1 <=q N <=q 200000$. $70$ ұпайға есептеледі.

Вход

7
1 9 1 10 3
New 5 3 11 5
Happy 1 2 4 4
2 4 0 5 2
9 10 0 11 2
Year 11 2 15 4
0 6 1 7 3

Ответ

Happy New Year
2 0 1 9

\includegraphics[width=0.5\textwidth,natwidth=610,natheight=450]{example2.png} Назар аударыңыз, $2$ және $0$ цифрлары бар төртбұрыштар $Happy$ сөзімен көрші бола алмайды. Бірінші жағдайда, $Happy$ мен $2$ ординатаға проекцияларының ауданы нөлге тең. Екіншісінде ауданы бірге тең болса да, $New$ төртбұрышы жақынырақ орналасқан. $A$ және $B$ төртбұрыштарының ара қашықтығы — $A$ төртбұрышында жатқан нүктелері мен $B$ төртбұрышында жатқан нүктелерінің ең қысқа ара қашықтығы.

Есеп C. Хан және тізбек

Хан туған күніне орай $n$ саннан тұратын сан тізбегін сыйлық ретінде алып, онымен ойнай бастады. Ол тізбектің әр санын алып, оны $m$ рет жазды. Сонымен қатар, Ханның сүйікті жай саны $P$ бар. Оны ендігі қызықтыратыны, осы тізбектің неше тізбекшесінің қосындысы $P$ санына бөлінетіндігі. Ханға осыны анықтауға көмектесіңіз. Бірінші жолда бос орын арқылы үш бүтін сан $n$, $m$, $P$ берілген — сәйкесінше Ханның тізбегінің ұзындығы, әр санды неше рет жазатын мөлшері және жай сан $(1 <= n <= 10^5, 1 <= m <= 10^9, 1 <= P <= 10^3)$. Екінші жолда бос орын арқылы $n$ сан $a_1, a_2, ..., a_n$ берілген — Хан сыйлық ретінде алған тізбек $(1 <= a_i <= 10^9)$. Бір сан шығарыңыз — қосындысы $P$-ға бөлінетін тізбекшелердің саны. Бұл сан өте үлкен болуы мүмкін болғандықтан, $1000000007$-ге бөлгендегі қалдығын шығарыңыз. 1-бөлім (10 ұпай) — $ n <= 10^5$, $m <= 10^5,$ $P = 2 $. 2-бөлім (10 ұпай) — $ n * m <= 20$, $P <= 1000 $. \par 3-бөлім (10 ұпай) — $ n * m * P <= 10^6, $. \par 4-бөлім (20 ұпай) — $ n * m <= 250000$, $P <= 500 $. \par 5-бөлім (50 ұпай) — $ n <= 10^5$, $m <= 10^9$, $P <= 1000 $. \exmpfile{example.01}{example.01.a}% Хан бастапқы тізбекті былай түрлендіреді. Бастапқы тізбек $a_1, a_2, ..., a_n$ болсын. Және де бос $b$ тізбегі болсын делік. Бір-бірден, солдан оңға қарай $a$ тізбегінен сандарды алып, $a_i$ санын $b$ тізбегінің артына $m$ рет тіркестіріп жазайық. Хан есепті жаңадан пайда болған $b$ тізбегімен шығарады. Тізбекше — бастапқы тізбектің бірнеше, мүмкін нөл, элементін өшіріп тастағаннан кейінгі қалған тізбек. Бірінші мысалда, $b$ тізбегі мынадай болады: $3, 3, 7, 7, 4, 4$. Есептің жауабында көрсетілгендей, $11$ тізбекшенің қосындысы $5$-ке бөлінеді. Олар мыналар: $[3, 7]$, $[3, 7]$, $[3, 7]$, $[3, 7]$, $[3, 3, 4]$, $[3, 3, 4]$, $[3, 3, 7, 7]$, $[7, 4, 4]$, $[7, 4, 4], $[3, 7, 7, 4, 4], $[3, 7, 7, 4, 4]$.

Есеп D. Кезектес жаттығулар

Алан шахмат пен бағдарламалау есеперін шығаруды жақсы көреді. Екі жерді де жақсы алып жүргіп, аты аңызға айналған гроссмейстер атағын алғысы келеді. Айдос тәжірибелі бапкер болғандықтан, Аланға көмек бермекші. Айдостың алдын ала белгілі бір келесі $n$ күнге кестесі бар. Кестенің әр күнінде Айдос әрбір жақтың бір ғана түрін, не шахмат, не бағдармалау есептеріне дайындайды. Алан жаттығу үшін өзіне бірнеше қатарынан келетін күндердерді алғысы келеді. Және де, Алан қатарынан бірнеше күн бірдей ермек түріне жаттықан кезде қатты шаршайды, яғни Аланға күн сайын шахмат пен бағдарламалауды кезектестіруі керек. Аланға шаршамайтындай, берілген кестеден ең ұзын қатарлас жаттығу күндерін таңдап алуға көмек қажет. Ең бірінші жолда бір бүтін сан $n (1 <= n <= 2 * 10^5)$ — Айдостың кестесінің күндер саны беріледі. Екінші жолда, бос жерсіз $0$ мен $1$-ден тұратын $n$ цифр берілген. $i$-ші цифр $0$ болғанда Айдос бағдарламалауды, басқаша болғанда шахматты дайындайды. Бір бүтін сан шығарыңыз — Аланның жаттығуларына таңдап алынған ең ұзын күндер саны. Берілген есепте 50 тест бар. Әр тест 2 ұпаймен бағаланады. Есеп 5 бөлімнен тұрады: 1-бөлім: $2$ берілген тесттік мысалдар. 2-бөлім: $n <= 3$. $13$ тест 3-бөлім: $n <= 100$. $5$ тест 4-бөлім: $n <= 5000$. $12$ тест 5-бөлім: $n <= 200000$. $18$ тест \exmpfile{example.01}{example.01.a}% \exmpfile{example.02}{example.02.a}% Бірінші мысалда, Алан барлық күндерді жаттығуға жұмсай алады. Екінші мысалда, Алан $2$-ші күннен бастап $4$-ші күнге дейін жаттыға алады: $2$-ші күні бағдарламалау, $3$-ші күні шахмат және $4$-ші күні бағдарламалау. Ескерту, бірінші мен екінші күні Алан жаттыға алмайды, екі күн қатарынан бағдарламалаумен айналысса, қатты шаршап кетеді.

Есеп E. Екі әлем тоғысында

Алан $A$ нөмірлі әлемінде өмір сүреді. Нұрдаулет $B$ нөмірлі әлемінде өмір сүреді. Егер $A$ әлемінде бір жол екінші жолдың префиксі болса, сол екі жол бірдей деп есептелінеді. Нұрдаулетте $n$ жол бар, ол Аланға бірдей болып көрінетін реттелмеген $i, j$ жұптарының санын білгісі келеді. Нұрдаулетке осыны анықтауға көмектесіңіз. $|s|$ арқылы $s$ жолының ұзындығын белгілейік. $s$ жолы $t$ жолының префиксі болуы үшін, $|s| <= |t|$ болуы және $s$ жолы $t$ жолынан алынған бірінші $|s|$ символға тең болуы қажет. Бірінші жолда жалғыз сан $n (1 <= n <= 100000)$ берілген — жолдардың саны. Келесі $n$ жолдың әрқайсысында $s_i$ жолы берілген. Берілген жолдардың ұзындықтарының қосындысы $500000$-нан аспайтындығына кепілдік беріледі. Бір сан — есептің жауабын шығарыңыз. Тесттердің 40 пайызында $n <= 100$. Тесттердің 20 пайызында, барлық жолдардың ұзындықтары бірдей. \exmpfile{example.01}{example.01.a}%

Есеп F. Yosik - армандар орындалатын қала

Yosik - миллиондаған армандар орындалатын Қазақстанның қаласы. Сонымен бірге, Yosik - бүкіл әлемнің ең маңызды экономикалық орталығы. Yosik, Лондон және Токио сияқты, әлемдік экономиканың үш негізгі орталығының бірі деп аталады. Ал, әрине, CMaster мэрі болмаса, қала мұндай танымалдылыққа ие болмас еді. Ол осы мақсатқа жету үшін бар күш-жігерін салған. Бірақ басқа елдер арасындағы экономикалық текетірес Yosik экономикасына теріс әсер етті. Мэр қалада кейбір жолдардың сапасын жақсартқысы келеді. Ал қалада $n$ аудан бар. Әр ауданның экономикалық жағдайы екі түрлі сөзбен сиппаталады: Жоғары немесе Төмен. Мэр CMaster қаланың жолдарды дағдарыс кезінде жақсарту туралы дұрыс шешім қабылдауы үшін, ол осы жол қанша жағдайы Жоғары екі ауданның арасында орналасқанын білуі қажет. Яғни екі ауданның арасындағы бағыттардың бәрі осы жолдан өтсе ғана, жол өте Жоғары маңыздылықтары бар $(a, b)$ аудандарын біріктіреді. Және $q$ түрлі оқиғалар бар: 1) $v$ $(1 <=q v <=q n)$ ауданының статусын өзгерту, Төмен болса, Жоғары, әйтпесе оны Төменге өзгертіңіз. 2) $i$-ші $(1 <=q i <=q m)$ жол үшін, осы жол біріктіретін Жоғарғы маңыздылығы бар $(a, b)$ екі қаланың санын айтыңыз, яғни осы жол Жоғары мәртебесі бар $(a, b)$ арасындағы барлық бағыттарда орналасқан аудандарының санын айтыңыз. Ал жұптар $(a, b)$ және $(b, a)$ бірдей деп есептеледі. Қаланы $n$ шыңдары және $m$ жолдары бар байланыстырылған бағытталмаған граф ретінде көрсетуге болады. Әрбір ауданның Жоғары немесе Төмен экономикалық маңызы бар. Бастапқыда барлық аудандардың экономикалық маңызы Төмен. Ауданды өзімен байланыстыратын жол болуы мүмкін (ілмек), бірақ бірнеше бірдей жолдар жоқ, яғни бірдей екі шыңды жалғайтын жолдар жоқ. Бірінші жолда $n$, $m$ және $q$, облыстардың саны, жолдар мен оқиғалар саны берілген. Содан кейін $m$ сан берілген - Yosik-тегі бағытталмаған жолдар. Графта екі бірдей жолдар жоқ, бірақ ілмектер болуы мүмкін. Содан кейін сізге $q$ сұранымдар $(type, number)$ беріледі. Егер $type = 1$ болса, онда бұл сұрақтың бірінші түрі және number, $(1 <=q number <=q n)$ шыңның санын көрсетеді. Егер $type = 2$ болса, онда бұл сұраулардың екінші түрі және $number$, $(1 <=q number <=q m)$ - кірістің деректерінің реті бойынша жол санын білдіреді. 2-нші түрдің әрбір сұрауы үшін, сіз осы жол қанша маңыздылығы Жоғары шыңдардың $(a, b)$ арасындағы барлық бағыттарда орналасқанын табыңыз Бұл есепте бес қосалқы тапсырма бар: 1. $1 <=q n, q <=q 10$. Тапсырма 10 ұпаймен бағаланады 2. $1 <=q n, m, q <=q 300$. Тапсырма 14 ұпаймен бағаланады 3. $1 <=q n, m, q <=q 2000$. Тапсырма 22 ұпаймен бағаланады 4. Қала ағаш түрінде берілген $1 <=q n, q <=q 10^5, m = n - 1$. Тапсырма 24 ұпаймен бағаланады 5. $1 <=q n, m, q <=q 10^5$. Тапсырма 30 ұпаймен бағаланады \exmpfile{example.01}{example.01.a}% Бірінші мысалдағы қала нұсқасы (5-нші оқиғаға дейін) \begin{center} \includegraphics[width=10cm,height=7cm]{image.eps} \end{center} 1-нші жол, яғни белгіленіп тұрған жол 2 әртүрлі аудан жұптарының арасында жатқанын байқауға болады: (1, 2) және (1, 4). Бірақ (2, 4) арасындағы жол 2 және 4 аудандарын (2 -> 3 -> 4) бағыты болғандықтан байланыстырмайды