Сіз Just Ordinary Inventions компаниясын білесіз бе? Бұл компанияның қызметі — «кәдімгі қарапайым өнертабыстар» жасау.

JOI-кун Just Ordinary Inventions компаниясы әзірлеген ең жаңа ойынды ойнап отыр.

Бұл ойын бірнеше бөлмеден және бірнеше жолдан тұратын зынданды зерттеуді қамтиды. Жол зындандағы екі түрлі бөлмені байланыстырады және онымен екі бағытта да жүруге болады. Кез келген екі түрлі бөлменің арасында оларды байланыстыратын ең көп дегенде бір ғана жол бар, және екі шеті де бір бөлмеге тірелетін жолдар жоқ. Сонымен қатар, зындандағы кез келген екі бөлмеге бір-бірінен бірнеше жолды пайдалану арқылы жетуге болатыны белгілі. Әрбір бөлме басқаларына өте ұқсас, ал шығатын жолдарының саны бірдей бөлмелерді тек сыртқы түріне қарап бір-бірінен ажырату мүмкін емес.

Бұл ойында зерттеуге көмектесу үшін әр бөлме белгімен және тұғырмен жабдықталған. Бөлмеден шығатын жолдарды белгіге сүйене отырып 1-ші, 2-ші, ... жол деп санауға болады. Ойын барысында зынданның құрылымы өзгермейді. Сондықтан, егер сіз бір бөлмеден бірдей нөмірлі жолды пайдаланып шықсаңыз, әрқашан бір бөлмеге келесіз. Тұғыр ойыншы түсін өзгерте алатын бір асыл таспен безендірілген. Асыл тастың түсі 1-түс, 2-түс, ..., $X$-түс мәндерінің бірі болады, ал ойынның басында әр бөлмедегі асыл тастың түсі — 1-түс. Ойыншы оны өзгертпейінше, асыл тастың түсі өзгермейді.

JOI-кун егер осы зынданның құрылымы, яғни бөлмелердің жолдармен қалай байланысқаны белгілі болса, бұл ойынды оңай өтуге болатынын түсінді. Алайда, JOI-кун қанша тырысса да, зынданның құрылымын анықтай алмады. Сондықтан сіз JOI-кунның орнына зынданның құрылымын анықтайтын бағдарлама жазуды ұйғардыңыз.

Тапсырма

Зынданды зерттеп, оның құрылымын анықтайтын бағдарлама құрыңыз. Алайда, JOI-кун зынданның құрылымы толықтай ашылып қалғанын қаламағандықтан, бағдарлама зынданның құрылымын тікелей қайтармай, оның орнына 1-ден $R$-ге дейінгі әрбір $i$ бүтін саны үшін «ең аз дегенде дәл $i$ жолды пайдаланып жетуге болатын қанша бөлмелер жұбы бар» екенін (бөлмелердің реті ауысқан жұптар бір жұп деп есептеледі) жауап ретінде беруі тиіс.

Зынданды зерттеу үшін сізге келесі әрекеттерді орындайтын кітапхана беріледі:

• Ағымдағы бөлмеден қанша жол шығатынын білу.
• Ағымдағы бөлмедегі тұғырда орналасқан асыл тастың түсін білу.
• Ағымдағы бөлмедегі тұғырда орналасқан асыл тастың түсін көрсетілген түске өзгерту (ағымдағы түспен бірдей түсті де көрсетуге болады). Одан кейін бөлмеден шығатын бір жолды таңдап, сол жол арқылы басқа бөлмеге өту.
• Соңғы пайдаланылған жол ағымдағы бөлмеден шығатын жолдардың ішінде нешінші жол болғанын білу.

Іске асыру мәліметтері

Сіз JOI-кунның жауап беру әдісін іске асыратын бір бағдарлама жазуыңыз керек. Бағдарламада dungeon2.h файлы қосылуы тиіс.

Бағдарлама келесі процедураны іске асыруы тиіс:

• void Inspect(int R)
  • Бұл процедура басында дәл бір рет шақырылады.
  • $R$ аргументі 1-ден $R$-ге дейінгі әрбір $i$ бүтін саны үшін «ең аз дегенде дәл $i$ жолды пайдаланып жетуге болатын қанша бөлмелер жұбы бар» екенін жауап ретінде беруіңіз керек екенін білдіреді.

Сондай-ақ, сұрақтарға жауап беру үшін келесі процедураны шақыруыңыз керек:

• void Answer(int D, int A)
  • $D$ және $A$ аргументтері осы шақыруда сіздің «ең аз дегенде дәл $D$ жолды пайдаланып жетуге болатын $A$ бөлмелер жұбы бар» деп жауап беріп жатқаныңызды білдіреді.

Алайда, Answer процедурасын шақыру келесі шарттарды қанағаттандыруы тиіс:

• $D$ саны 1 мен $R$ аралығындағы бүтін сан болуы тиіс. Егер бұл шарт орындалмаса, ол Қате [1] деп бағаланады.
• Бірдей $D$ аргументімен Answer процедурасын бір реттен артық шақыруға болмайды. Егер бұл шарт орындалмаса, ол Қате [2] деп бағаланады.
• Answer процедурасы дәл $R$ рет шақырылуы тиіс. Егер бұл шарт орындалмаса, ол Қате [3] деп бағаланады.
• $A$ саны ең аз дегенде дәл $D$ жолды пайдаланып жетуге болатын бөлмелер жұптарының санына тең болуы тиіс. Егер бұл шарт орындалмаса, ол Қате [4] деп бағаланады.

Егер Answer шақыруы қате деп бағаланса, бағдарламаның одан кейінгі бөлігі орындалмауы мүмкін.

Сонымен қатар, бағдарламаңызда келесі процедураларды шақыра аласыз:

• void Move(int I, int C)
  • $I$ аргументі — ойыншының жүру үшін таңдаған жолының нөмірі. Осы шақырудан кейін бірден ойыншы ағымдағы бөлмеден шығатын $I$-ші жолды пайдаланып басқа бөлмеге өтеді.
  • $C$ аргументі басқа бөлмеге өтпес бұрын ағымдағы бөлмедегі тұғырда орналасқан асыл тастың түсі $C$-түске өзгертілетінін білдіреді.

Алайда, Move процедурасын шақыру келесі шарттарды қанағаттандыруы тиіс:

• $I$ аргументі 1 мен $K$ аралығындағы бүтін сан болуы тиіс, мұндағы $K$ — ойыншы дәл қазір орналасқан бөлмеден шығатын жолдардың саны. Егер бұл шарт орындалмаса, ол Қате [5] деп бағаланады.
• $C$ аргументі 1 мен $X$ аралығындағы бүтін сан болуы тиіс, мұндағы $X$ — асыл тас түстерінің түрлерінің саны. $X$ мәні әрбір ішкі тапсырма үшін белгіленген. Егер бұл шарт орындалмаса, ол Қате [6] деп бағаланады.

• Move процедурасы 1,500,000 реттен артық шақырылмауы тиіс. Егер ол одан көп шақырылса, Қате [7] деп бағаланады.

• int NumberOfRoads()

  • Бұл функция ойыншы дәл қазір орналасқан бөлмеден шығатын жолдардың санын қайтарады.

• int LastRoad()

  • Бұл функция соңғы пайдаланылған жол ағымдағы бөлмеден шығатын жолдардың ішінде нешінші жол болғанын қайтарады. Алайда, егер бұл функция Move бір рет те шақырылмай тұрып шақырылса, ол -1 мәнін қайтарады.

• int Color()

  • Бұл функция ойыншы дәл қазір орналасқан бөлмедегі тұғырда тұрған асыл тастың түсін қайтарады.

Inspect процедурасы шақырылып болғаннан кейін жауап тексеріледі.

Ішкі қажеттіліктер үшін басқа процедураларды іске асыруға немесе жаһандық айнымалыларды жариялауға еріктісіз. Дегенмен, сіздің жіберген кодыңыз стандартты енгізу/шығарумен немесе кез келген басқа файлдармен ешқандай түрде әрекеттеспеуі тиіс.

Компиляция және іске қосу

Жарыс сайтынан жүктеп алуға болатын мұрағатта үлгі тексеруші (sample grader) берілген. Бұл мұрағатта сіз жіберуге тиіс файлдың үлгісі де бар.

Үлгі тексеруші бір ғана grader.c немесе grader.cpp файлынан тұрады. Бағдарламаңызды тексеру үшін келесі командаларды орындаңыз:

• C тілі үшін: gcc -std=c11 -O2 -o grader grader.c dungeon2.c -lm
• C++ тілі үшін: g++ -std=c++11 -O2 -o grader grader.cpp dungeon2.cpp

Егер компиляция сәтті өтсе, grader деп аталатын орындалатын файл жасалады.

Бағалау үшін қолданылатын нақты тексеруші үлгі тексерушіден өзгеше екенін ескеріңіз. Үлгі тексеруші стандартты енгізуден деректерді оқып, нәтижелерді стандартты шығаруға жазатын бір процесс ретінде жұмыс істейді.

Үлгі тексерушінің кіріс деректері

Үлгі тексеруші стандартты енгізуден келесі деректерді оқиды:

• 1-ші жолда бос орын арқылы бөлінген $N, X, R$ бүтін сандары берілген. Бұл зынданда $N$ бөлме (1-бөлме, 2-бөлме, ..., $N$-бөлме) бар екенін, асыл тас түстерінің $X$ түрі бар екенін және бағдарлама $R$ мәнді жауап ретінде беруі тиіс екенін білдіреді.
• Келесі $2N$ жолда, $(2i - 1)$-ші жолда ($1 \le i \le N$) $i$-ші бөлмеден $D_i$ жол шығатынын білдіретін бір бүтін сан $D_i$ берілген. $2i$-ші жолда ($1 \le i \le N$) бос орындар арқылы бөлінген $D_i$ бүтін сан $T_{i1}, T_{i2}, \dots, T_{iD_i}$ берілген. Бұл $i$-ші бөлмеден шығатын $j$-ші жолмен ($1 \le j \le D_i$) жүргенде $T_{ij}$-ші бөлмеге баратынын білдіреді.
• Келесі $R$ жолда, $j$-ші жолда ($1 \le j \le R$) бір бүтін сан $A_j$ берілген. Бұл ең аз дегенде дәл $j$ жолды пайдаланып жетуге болатын $A_j$ бөлмелер жұбы бар екенін білдіреді. Яғни, әрбір $j$ ($1 \le j \le R$) үшін, егер Answer процедурасы $D$ аргументі $j$ және $A$ аргументі $A_j$ болып шақырылса, үлгі тексеруші оны дұрыс деп бағалайды, әйтпесе қате деп бағалайды.

Үлгі тексеруші ойыншының бастапқы орнын 1-бөлме етіп сіздің процедураңызды шақырады.

Үлгі тексерушінің шығыс деректері

Бағдарламаның орындалуы қалыпты аяқталған кезде, үлгі тексеруші стандартты шығаруға бір жолда келесі ақпаратты шығарады (тырнақшалар іс жүзінде шығарылмайды):

• Егер дұрыс болса, Move функциясын шақырулар саны Accepted : #move = 8 түрінде шығарылады.
• Егер қате болса, қатенің түрі Wrong Answer [1] сияқты шығарылады.

Шектеулер

Барлық кіріс деректер келесі шарттарды қанағаттандырады. $N, D_i, T_{ij}$ мәндерінің мағынасын «Үлгі тексерушінің кіріс деректері» бөлімінен қараңыз.

• $2 \le N \le 200$
• $3 \le X \le 100$
• $1 \le R \le 200$
• $1 \le D_i \le N - 1$ ($1 \le i \le N$)
• $1 \le T_{ij} \le N$ және $T_{ij} \neq i$ ($1 \le i \le N, 1 \le j \le D_i$)
• $T_{i1}, T_{i2}, \dots, T_{iD_i}$ ($1 \le i \le N$) сандары өзара әртүрлі.
• Әрбір $i, j$ ($1 \le i \le N, 1 \le j \le D_i$) үшін $T_{T_{ij}k} = i$ болатындай $k$ ($1 \le k \le D_{T_{ij}}$) табылады.
• Кез келген екі бөлмеге бір-бірінен бірнеше жолды пайдалану арқылы жетуге болады.

Ішкі тапсырмалар

Төменде кіріс деректердегі зындандағы бөлмелер санын $N$ деп, ал жолдар санын $M$ деп белгілейік.

1-ішкі тапсырма [17 ұпай]

Келесі шарттар орындалады:

• $N \le 50$
• $M \le 100$
• $X = 100$

2-ішкі тапсырма [27 ұпай]

Келесі шарттар орындалады:

• $N \le 50$
• $M \le 100$
• $X = 3$

3-ішкі тапсырма [56 ұпай]

• $X = 3$ шарты орындалады.

Бұл ішкі тапсырмада ұпай келесідей анықталады:

• $L$ — осы ішкі тапсырмадағы барлық тест жағдайлары бойынша келесі шаманың ең үлкен мәні болсын:
  • $\frac{C}{M}$, мұндағы $C$ — Move функциясын шақырулар саны.
• Бұл жағдайда осы ішкі тапсырманың ұпайы:
  • Егер $L \le 14$ болса, 56 ұпай.
  • Егер $14 < L \le 32$ болса, $\lfloor 70 - L \rfloor$ ұпай.
  • Егер $32 < L \le 64$ болса, $\lfloor 54 - \frac{L}{2} \rfloor$ ұпай.
  • Егер $64 < L$ болса, 0 ұпай.

Мұндағы $\lfloor x \rfloor$ жазбасы $x$-тен аспайтын ең үлкен бүтін санды білдіреді.

Мысалдар

Кіріс 1

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

Шығыс 1

Inspect(3)
NumberOfRoads() -> 1
LastRoad() -> -1
Move(1,2)
Color() -> 1
LastRoad() -> 1
NumberOfRoads() -> 3
Move(1,3)
Color() -> 2
Answer(1,4)
Answer(2,2)
Answer(3,0)

Ескертпе

Бұл мысалдағы функция шақырулары міндетті түрде мағыналы шақырулар болып табылмайды.