Universal Cup Judging System

Universal Cup

시간 제한: 2.0 s 메모리 제한: 1024 MB 총점: 100 해킹 가능 ✓
통계

Þér er gefið fylki með $n$ heiltölum frá $1$ til $n+1$. Mögulegt er að sumar heiltölurnar komi fyrirнта oftar en einu sinni í fylkinu. Engu að síður er ljóst að að minnsta kosti eina af heiltölunum frá $1$ til $n+1$ vantar í fylkið. Verkefni þitt er að finna einhverja slíka heiltölu. Venjulega væri það auðvelt, en það er óheppilegt vandamál: það er ekki nægt minni í tölvunni þinni til að geyma allt fylkið.

Þess vegna er(t) þú beðin(n) um að búa til streymisreiknirit (streaming algorithm) í staðinn. Óformlega sagt eru stök fylkisins gefin þér eitt af öðru án nokkurrar leiðar til að nálgast þau með handahófsaðgangi (random access). Það er þó ein huggun: eftir að hafa fengið síðasta stakið í fylkinu geturðu byrjað að lesa það aftur frá byrjun. Helst myndirðu vilja forðast slíkar aðstæður og leysa allt verkefnið í einni yfirferð. Stundum (þar á meðal í þessu tiltekna verkefni) geta þó margar yfirferðir yfir inntakið verið nauðsynlegar til að forðast að nota of mikið minni. Þú þarft að vega og meta bæði atriðin og nota hvorki of mikið minni né fara of margar yfirferðir yfir fylkið á sama tíma (verkefnið er léttvægt ef þér er leyft að geyma $n$ bita af minni eða nota $n$ yfirferðir).

Það er þó enn einn hængur á. Af tæknilegum ástæðum þarftu að búa tilulega ákvarðaða endanlega stöðuvél (DFA) yfir stafrófið $\{0, 1, \dots, n + 1\}$ sem útfærir rökfræði reikniritsins þíns. Stafir stafrófsins samsvara upplýsingunum sem þú færð þegar þú lest streymið: tölur frá $1$ til $n+1$ tákna lestur á samsvarandi heiltölu úr fylkinu, en talan $0$ táknar þá staðreynd að þú hefur náð enda fylkisins. Eftir fyrstu 7 skiptin sem þú nærð enda fylkisins verður fylkið gefið þér aftur í sömu röð og áður, og endar það alltaf á stafnum $0$ sem táknar enda fylkisins. Þannig mun DFA-vélin þín fá strenginn $a_1, a_2, \dots, a_n, 0$ alls 8 sinnum (hér er $a_1, a_2, \dots, a_n$ falda fylkið). Að lokum getur stöðuvélin þín á hvaða augnabliki keyrslunnar sem er „sagt“ að hún viti nú þegar eitthvert rétt svar við verkefninu; í því tilviki er keyrslunni hætt. Ef DFA-vélin þín hefur ekki gert það þegar hún hefur lesið allt streymið (þar á meðal stafinn $0$ í lokin) 8 sinnum, er hún ekki samþykkt sem lausn. Sömuleiðis, ef hún stöðvast en gefur rangt svar, er hún heldur ekki samþykkt sem lausn.

Setjum verkefnið fram formlega. Til er falið fylki $a_1, a_2, \dots, a_n$ með $n$ heiltölum frá $1$ til $n+1$. Í dæminu er $n = 4$, en í öllum öðrum prófunum er $n = 250$. Þú þarft að tilgreina endanlega stöðuvél með að hámarki 4000 stöður, númeraðar frá $0$ til $q - 1$, þar sem $q \le 4000$ er fjöldi staða. Fyrir stöðuna $i$ ($0 \le i \le q - 1$) þarftu að tilgreina $n + 2$ tölur $\delta(i, 0), \delta(i, 1), \dots, \delta(i, n + 1)$. Talan $\delta(i, j)$ táknar hegðun DFA-vélarinnar þegar hún er í stöðu $i$ og lest töluna $j$ úr inntakinu. Hún verður að vera heiltala frá $-(n + 1)$ til $q - 1$ að báðum mörkum meðtöldum. Neikvæðar heiltölur samsvara því að keyrslunni sé hætt og svar gefið; nánar tiltekið samsvarar $-s$ því að DFA-vélin þín haldi því fram að $+s$ sé rétt svar við verkefninu. Óneikvæðar heiltölur samsvara því að keyrslan haldi áfram og staða vélarinnar breytist úr $i$ í $\delta(i, j)$. Keyrsla stöðuvélarinnar hefst í stöðu $0$.

DFA-vélin þín telst virka rétt á fylkinu $a_1, a_2, \dots, a_n$ ef hún stöðvast með rétt svar á einhverjum tímapunkti við lestur strengsins $a_1, a_2, \dots, a_n, 0, a_1, a_2, \dots, a_n, 0, \dots, a_1, a_2, \dots, a_n, 0$, þar sem fylkið er endurtekið 8 sinnum. DFA-vélin þín telst virka rétt almennt ef hún virkar rétt á öllum mögulegum fylkjum $a_1, a_2, \dots, a_n$ af heiltölum frá $1$ til $n+1$ (þess vegna er ráðlagt gegn líkindalausnum).

Fyrir $n = 4$ munum við prófa DFA-vélina þína á öllum mögulegum fylkjum. Fyrir $n = 250$ höfum við ekki tök á að prófa hana á öllum fylkjum, svo við munum prófa hana á færri en 5000 sérvöldum fylkjum. Það eru tvö prófunartilvik í verkefninu; bæði prófunartilvikin sannreyna í raun að aðferðin þín virki rétt á mörgum fylkjum samtímis.

Inntak

Ein heiltala $n$, sem er annaðhvort jöfn $4$ eða $250$.

Úttak

Á fyrstu línunni skaltu prenta eina heiltölu $q$ ($1 \le q \le 4000$) sem táknar fjölda staða í DFA-vélinni þinni.

Á $i$-tu línunni af næstu $q$ línum skaltu prenta $n + 2$ heiltölur $\delta(i - 1, 0), \delta(i - 1, 1), \dots, \delta(i - 1, n + 1)$. Þær eiga allar að vera á bilinu $-(n + 1)$ til $q - 1$ að báðum mörkum meðtöldum og samsvara færslum stöðuvélarinnar. Athugaðu að allar tölurnar verða að vera á þessu bili: jafnvel þótt einhver samsetning af stöðu $i$ og inntakstölu $j$ geti aldrei náðst á neinu gildu inntaki, verður gildið á $\delta(i, j)$ sem þú tilgreinir samt að vera á bilinu $[-(n + 1), q - 1]$.

Dæmi

Inntak 1

4

Úttak 1

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

Athugasemd

Svarið við dæminu er mjög leiðinleg stöðuvél sem notar fjórar yfirferðir til að athuga hvort fylkið innihaldi tölurnar 3, 1, 5 og 2 (í þeirri röð). Hver yfirferð notar í raun aðeins tvær stöður sem samsvara því hvort hún hafi þegar fundið töluna sem hún leitar að í núverandi yfirferð. Ef hún nær enda fylkisins (stafnum 0) án þess að finna nauðsynlegu töluna stöðvast hún samstundis og segir að umrædda tölu vanti sannarlega. Annars heldur hún áfram í næstu yfirferð til að leita að næstu tölu. Að lokum, ef hún hefur fundið allar fjórar nauðsynlegu heiltölurnar, þá hlýtur töluna 4 að vanta. Þess vegna fer hún ekki fimmtu yfirferðina til að leita að tölunni 4 (en hún hefði getað gert það án þess að brjóta gegn takmörkunum á fjölda staða í stöðuvélinni og fjölda notaðra yfirferða).

Auðvitað á þessi einfeldningslega nálgun enga möguleika á að virka fyrir $n = 250$, og eitthvað mun betra þarf til. Aðalástæðan fyrir tilvist dæmisins er að sýna úttakssniðið.

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1213EditorialOpen题解jianglyView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.