Есеп A. Сиқырлы квест

Сiз компьютерлiк ойынды ойнап отырсыз. Сiзде әр түрлi өлшемдi $N$ сиқырлы заттар бар. Жол сөмкесiне өлшемдерiнiң қосындысы $K$-ға тең болатын заттар ғана салына алады. Әрқайсысы белгiлi күшi бар және берiлген заттардың белгiлi жиынтығын қолданатын $M$ сыналаулар бар. Сапарға шығар алдында, сiз қолдана алатын сыналаулардың күштерiнiң қосындысы барынша көп болатындай етiп сөмкенi заттармен толтыруыңыз тиiс. Енгiзу файлдың бiрiншi жолында үш бүтiн сан $N,$ $M,$ $K$ берiледi $(1 \le N,M \le 25,$ $1 \le K \le 10^9).$ Келесi жолда әрқайсысы $10^9$-дан аспайтын, $N$ бүтiн сандар — заттардың өлшемдерi берiледi. Келесi жолда әрқайсысы $10^9$-дан аспайтын, $M$ бүтiн сандар — сынаулардың күштерi берiледi. Келесi $M$ жолдарда сынаулардың сипаттамалары, әр жолға бiреуден берiледi. Әр сынаудың сипаттамасы — қажет ететiн заттардың нөмiрлерiнiң тiзiмi. Әр сынау кемiнде бiр затты кажет етедi. Бiр жолды — өзiмен бiрге алатын заттардың нөмiрлерiнiң тiзiмiн шығарыңыз. Вход

3 3 2
1 1 1
10 100 1000
1 2
1 2
3 2

Ответ

2 3

Есеп B. Ферзьдер

$N \times N$ шахмат тақтасында сандар жазылған — әр ұяшықта бiр сан. $N$ ферздердi бiр-бiрiн ұрмайтындай (егер екi ферзь бiр вертикальда, горизонтальда немесе диагональда тұрса, олар бiр-бiрiн ұрады) және олар тұрған ұяшықтардағы сандардың қосындысы ең көп болатындай етiп қойыңыз. Енгiзу файлының бiрiншi жолында бiр бүтiн сан $N$ берiледi $(1 \le N \le 15).$ Келесi $N$ жолдың әрқайсысында $N$ терiс емес, 1000-нан аспайтын бүтiн сандар — тақтаның сипаттамасы берiледi. Жолдағы сандар бос орынмен бөлiнген. Шығыс файлда әрқайсысында $N$ сандар болатындай $N$ жолдар шығарыңыз. $i$-шi жодағы $j$-шi сан 1-ге тең, егер $(i, j)$ ұяшығында ферзь тұрса, және 0-ге, егер тұрмаса. Вход

4
1 2 1 1
1 1 1 1
1 1 1 1
1 1 1 1

Ответ

0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0

Есеп C. Бiрiгу

Екi компанияларының бiрiгуi жүзеге асуда. Бiрiншiсiнде $n$ жұмысшылар бар, ал екiншiсiнде $m.$ Жаңа басшылық басқа компанияда қалатын жұмысшыларды танымайтын жұмысшыларды қалдырғысы келедi. Сiзге әр түрлi компанияларда кiм кiмдi бiлетiнi белгiлi. Жаңа басшылық қалдыра алатын жұмысшылар саны ең көп болатындай жұмысшыларды табыңыз. Енгiзу файлдың бiрiншi жолында екi бұтiн сандар $n$ және $m$ $(1 \le n,m \le 500)$ берiледi. Келесi $n$ жолдарда бiрiншi компанияның жұмысшыларының таныстарының сипаттамасы берiледi: $k_i$ — $i$-шi жұмысшыныңтаныстарының саны және одан кейiн әрқайсысы 1 ден $m$ ге дейiн болатын, екiншi компаниядағы таныстарының нөмiрлерi $k_i$ бүтiн сандар берiледi. Сол форматта келесi $m$ жолда екiншi компанияның таныстары туралы ақпарат жазылған. Бiрiншi компаниядан таныстарының нөмiрлерi 1 ден $n$ ге дейiнгi бүтiн сандар. Шығыс файлдың бiрiншi жолында үш бүтiн сандар — жаңа басшылық қалдыра алатын ең көп болатын жұмысшылар саны, $k_1$ — бiрiншi компаниядан жұмысшы және $k_2$ — екiншiден қанша. Екiншi жолда $k_1$ сандарды, бiрiншi компаниядан қалдыру керек жұмысшыларының нөмiрлерi. Үшiншi жолда $k_2$ сандарды, екiншi компаниядан қалдыру керек жұмысшыларының нөмiрлерi. Егер бiрнеше жауап болуы мүмкiн болса, кез келгенiн шығарыңыз. Вход

3 2
1 1
1 2
0
1 1
1 1

Ответ

3 2 1
1 3
2

Есеп D. Бiрегей сандар

Сiзге ұзындығы $N$-ға тең, бүтiн сандар $A$ массивi және осы массивтiң $[l, r]$ ретiнде көрсетiлетiн $M$ интервалдар берiледi. Әр интервал үшiн $A[l],$ $A[l + 1],$ $\ldots,$ $A[r]$ арасындағы әр түрлi сандардың санын табыңыз. Енгiзу файлдың бiрiншi жолында екi бүтiн сандар $N$ және $M$ берiледi $(1 \le N \le 10^5,$ $1 \le M \le 10^5).$ Келесi жолда $A$ массивi жазылған: $N$ бүтiн сандар $A[i]$ $(1 \le A[i] \le 10^9).$ Келесi $M$ жолдың әрқайсысында екi сандар $l[i]$ және $r[i]$ $(1 \le l[i] \le r[i] \le N)$ — сәйкес интервалдың ұштары берiледi. Шығыс файлда $M$ жолдар болуы тиiс. $i$-шi жолда $A$ массивiнiң енгiзу файлдың $(i+3)$-шi жолында берiлген, интервалда әр түрлi сандардың санын тауып шығарыңыз. Вход

6 6
1000 2 3 1 1000 1000
2 3
1 2
4 6
3 6
3 5
1 3

Ответ

2
2
2
3
3
3

Есеп E. Қосынды

$(f(L) + f(L + 1) + \ldots + f(R)) \pmod{P},$ тiзбегiнiң мәнiн табыңыз, бұл жерде $f(x) = (x - A)(x - B)(x - C)$. Енгiзу файлдың бiрiншi жолында алты бүтiн сандар $A,$ $B,$ $C,$ $L,$ $R,$ $P$ берледi $(0 \le A, B, C, L, R \le 10^9,$ $1 \le P \le 10^9,$ $1 \le R - L \le 10^8).$ Шығыс файлға бiр санды — есепке жауапты шығарыңыз. Вход

1 2 3 1 5 10^9

Ответ

30

Есеп F. Сайлау

Қалада $N$ қиылыстар және $M$ көшелер бар. Кез келген қиылыстан басқа қиылысқа жетуге болады және ол жол жалғыз. Қаланың әкiмi болу үшiн күрес басталды. Сайлаудың ақтық мәресiне екi кандидат шықты. Сайлау алдындағы үгiт көшелерде болады. Әр көшеде нақты бiр кандидатқа сайлау алдындағы үгiттi жүргiзетiн адамдар бар. Енгiзу файлдың бiрiншi жолында екi бүтiн сандар $N$ және $M$ берiлген $(1 \le N, M \le 10^5).$ Келесi $M$ жолдардың әрқайсысында қаланың сипаттамасы $a$ және $b$ — осы көше қосатын қиылыстар $(1 \le a, b \le N).$ Келесi жолда сұраулардың саны — $K$ берiледi $(1 \le K \le 10^5).$ Келесi $K$ жолдарда сұрау лар берiлген. Сұраудың екi түрлерi бар:
$+$ $x$ $y$ — $x$-шi кандитат $y$-шi көшесiнiң дауысын өзгерттi, және ендi $y$-шi көше оған сайлау алдындығы үгiттi жүргiзедi $(1 \le x \le 2,$ $1 \le y \le M).$
$q$ $x$ $y$ $k$ — $x$ және $y$ көшелерiнiң арасында $k$-шi кандидатқа қанша көше сайлау алдындағы үгiттi жүргiзедi $(1 \le k \le 2).$ Басында барлық көшелер 1-шi кандидатқа сайлау алдындағы үгiттi жүргiзедi Әр екiншi типтi сұрауға (жоғарыда берiлген) жауап шығарыңыз. Вход

3 2
1 2
1 3
3
q 1 3 1
+ 2 1
q 1 3 1

Ответ

2
1

Есеп G. Марста

Ғарыш кеме Марстың атмосферасына кiрдi. Бiрақ осы уақытта оның жұмысында шалыс болды. Кеме планетаның бетiне қонды. dist$(x, y)$ — $(x, y)$ нүктесiнен ғарыштық кемеге дейiн қашықтықты санайтын функция ғана iстейдi. Аккумулятор жұмысына да зақым келтiрiлгендiктен, бұл функцияны ең көп дегенде 10000 рет қолдана аласыз. Ғарышкерлерге көмектесiп, ғарыш кемесiнiң орналасқан нүктесiн шығарыңыз. Оның орналасқан жерiнiң координаттары бүтiн сан екенiне және и модулi бойынша $10^9$-нен аспай- тынына кепiл берiледi. Сiздiң программаңыз келесi сұрауларды қолдана алады:
C/C++ — start(), Pascal — start — бiр рет және ең бiрiншi сұрау болуы тиiс.
C/C++ — dist$(x, y),$ Pascal — dist$(x, y)$ — $(x, y)$ нүктесiнен ғарыштық кемеге дейiн қашықтықты санайтын функция, оны 10000 дан көп қолдана алмайсыз.
C/C++ — finish$(x, y),$ Pascal — finish$(x, y)$ — бiр рет және ең соңғы сұрау болуы тиiс, $(x, y)$ — сiздiң жауабыңыз.
Егер сiздiң программаңыз С/С++-да болса, dist.h қосыңыз: #include "dist.h"
Егер сiздiң программаңыз Pascal-да болса, dist модулiн: uses dist; start, dist және finish функция-процедураларын программаңызда анықтамаңыз. Керiсiнше оның комилияциясы бiзде қате өтедi.

Есеп H. Дәлелденген жылан

$N \times M$ тақтасында $(1, 1)$ ұяшығында өз алдына қойған мақсаттарын жүзеге асырғысы және $(N, M)$ ұяшығына мүмкiндiгiнше ең дәлелдi болып барғысы келетiн, жылан тұр. Жылан астыға, оңға және солға жүре алады. Егер жылан $(i, j)$ үяшығына барса, оның көңiл күйi осы ұяшықта жазылған мәнге азаяды және барлық осы уақытқа дейiн болған азайтулар осы ұяшықтың iшектi доминентiне көбейедi, бұл тағы да оның көңiл күйiн азайтуы мүмкiн. $(i, j)$ ұяшығының iшектi доминентi орын тәртiбiн сақтап $l$-дi $d$ қосылғышқа жiктеудiң әдiстерiне тең. Бұл жердегi $l(i, j)$ сандарының ең үлкенi, ал $d$ ең кiшiсi. Жыланның ең дәлелдi болып баруы үшiн ол көңiл күйiн ең аз мәнге азайтатын жолды таңдауы тиiс. Сiзге жыланның бастапқы көңiл күйi берiлген. Оның $(N, M)$ ұяшығында болатын ең үлкен болуы мүмкiн көңiл күйiнiң мөлшерiн табыңыз. Енгiзу файлдың бiрiншi жолында екi бүтiн сандар $N$ және $M$ берiледi $(1 \le N,M \le 200).$ Келесi $N$ жолдың әрқайсысында $M$ оң, әрқайсысы $10^{18}$ аспайтын сандар берiлген. Соңғы жолда $S$ — бастапқы көңiл күйi берiледi $(1 \le S \le 10^{1000}).$ Бiр санды — есептiң жауабын шығарыңыз.Жауап терiс сан болуы мүмкiн. Вход

2 3
100 1 10000 
10000 1 1 
100

Ответ

95