Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

Sinulle annetaan taulukko, jossa on $n$ kokonaislukua väliltä $1$ – $n+1$. On mahdollista, että jotkin kokonaisluvuista esiintyvät taulukossa useita kertoja. Silti on selvää, että vähintään yksi kokonaisluvuista väliltä $1$ – $n+1$ puuttuu taulukosta. Tehtäväsi on löytää mikä tahansa tällainen kokonaisluku. Normaalisti tämä olisi helppoa, mutta on olemassa ikävä ongelma: tietokoneessasi ei ole tarpeeksi muistia koko taulukon esittämiseen.

Siksi sinua pyydetäänkin laatimaan virta-algoritmi (streaming algorithm). Epämuodollisesti sanottuna taulukon alkiot annetaan sinulle yksi kerrallaan ilman mahdollisuutta hajasaantiin (random access). On kuitenkin yksi lohtu: vastaanotettuasi taulukon viimeisen alkion voit aloittaa taulukon lukemisen uudelleen alusta. Ihannetapauksessa haluaisit välttää tällaisen tilanteen ja ratkaista koko tehtävän yhdellä läpikäynnillä. Joskus (mukaan lukien juuri tässä tehtävässä) syötteen lukeminen useaan kertaan voi kuitenkin olla välttämätöntä liiallisen muistinkulutuksen välttämiseksi. Sinun on tasapainotettava molemmat vaatimukset ja samanaikaisesti oltava käyttämättä liikaa muistia sekä tekemättä liian monta läpikäyntiä taulukon yli (tehtävä on triviaali, jos saat tallentaa $n$ bittiä muistia tai käyttää $n$ läpikäyntiä).

Mukana on kuitenkin vielä yksi mutka. Teknisistä syistä sinun täytyy muodostaa aakkoston $\{0, 1, \dots, n + 1\}$ päällä toimiva deterministinen äärellinen automaatti (DFA), joka toteuttaa algoritmisi logiikan. Aakkoston merkit vastaavat tietoa, jonka saat lukiessasi virtaa: luvut väliltä $1$ – $n+1$ tarkoittavat vastaavan kokonaisluvun lukemista taulukosta, kun taas luku $0$ tarkoittaa, että olet saavuttanut taulukon lopun. Kun olet saavuttanut taulukon lopun ensimmäiset 7 kertaa, taulukko annetaan sinulle uudelleen samassa järjestyksessä kuin aiemmin, ja se päättyy aina taulukon loppua merkitsevään merkkiin $0$. Näin ollen DFA:llesi syötetään merkkijono $a_1, a_2, \dots, a_n, 0$ yhteensä 8 kertaa (tässä $a_1, a_2, \dots, a_n$ on piilotettu taulukko). Lopuksi, minä tahansa suorituksen hetkenä automaattisi voi ”ilmoittaa” tietävänsä jo jonkin oikean vastauksen tehtävään; tällöin suoritus pysäytetään. Jos DFA:si ei ole tehnyt näin siihen mennessä, kun se on lukenut koko virran (mukaan lukien lopussa olevan merkin $0$) 8 kertaa, sitä ei hyväksytä ratkaisuksi. Samoin, jos se pysähtyy, mutta antaa väärän vastauksen, sitä ei myöskään hyväksytä ratkaisuksi.

Muotoillaan tehtävä täsmällisesti. On olemassa piilotettu taulukko $a_1, a_2, \dots, a_n$, jossa on $n$ kokonaislukua väliltä $1$ – $n+1$. Esimerkissä $n = 4$, ja kaikissa muissa testeissä $n = 250$. Sinun tulee määrittää äärellinen tilakone, jossa on enintään 4000 tilaa, numeroituina $0$:sta $q - 1$:een, missä $q \le 4000$ on tilojen lukumäärä. Tilalle $i$ ($0 \le i \le q - 1$) sinun tulee määrittää $n + 2$ lukua $\delta(i, 0), \delta(i, 1), \dots, \delta(i, n + 1)$. Luku $\delta(i, j)$ kuvaa DFA:si toimintaa, kun se on tilassa $i$ ja lukee syötteestä luvun $j$. Sen on oltava kokonaisluku väliltä $-(n + 1)$ – $q - 1$ (päätepisteet mukaan lukien). Negatiiviset kokonaisluvut vastaavat sitä, että suoritus pysäytetään ja annetaan vastaus; tarkemmin sanottuna $-s$ vastaa sitä, että DFA:si väittää luvun $+s$ olevan oikea vastaus tehtävään. Ei-negatiiviset kokonaisluvut vastaavat sitä, että suoritus jatkuu ja automaatin tila vaihtuu tilasta $i$ tilaan $\delta(i, j)$. Automaatin suoritus alkaa tilasta $0$.

DFA:si katsotaan toimivan oikein taulukolla $a_1, a_2, \dots, a_n$, jos se pysähtyy antaen oikean vastauksen jossakin vaiheessa lukiessaan merkkijonoa $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$, missä taulukko toistetaan 8 kertaa. DFA:si katsotaan toimivan oikein yleisesti, jos se toimii oikein kaikilla mahdollisilla väliltä $1$ – $n+1$ olevista kokonaisluvuista koostuvilla taulukoilla $a_1, a_2, \dots, a_n$ (tämän vuoksi satunnaistettuja ratkaisuja ei suositella).

Tapauksessa $n = 4$ tarkistamme DFA:si kaikilla mahdollisilla taulukoilla. Tapauksessa $n = 250$ meillä ei ole keinoa tarkistaa sitä kaikilla taulukoilla, joten tarkistamme sen alle 5000:lla erityisesti valitulla taulukolla. Tehtävässä on kaksi testiä; molemmat testit varmistavat tehokkaasti, että ratkaisutapasi toimii oikein monilla taulukoilla samanaikaisesti.

Syöte

Yksi kokonaisluku $n$, joka on joko $4$ tai $250$.

Tuloste

Tulosta ensimmäiselle riville yksi kokonaisluku $q$ ($1 \le q \le 4000$), joka ilmaisee DFA:si tilojen lukumäärän.

Tulosta seuraavien $q$ rivin $i$:nnelle riville $n + 2$ kokonaislukua $\delta(i - 1, 0), \delta(i - 1, 1), \dots, \delta(i - 1, n + 1)$. Niiden kaikkien tulee olla väliltä $-(n + 1)$ – $q - 1$ (päätepisteet mukaan lukien) ja vastata automaatin siirtymiä. Huomaa, että kaikkien lukujen on oltava tällä välillä: vaikka jotakin tilan $i$ ja syöteluvun $j$ yhdistelmää ei voitaisi koskaan saavuttaa millään kelvollisella syötteellä, määrittämäsi arvon $\delta(i, j)$ on silti oltava välillä $[-(n + 1), q - 1]$.

Esimerkki

Syöte 1

4

Tuloste 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

Huomautus

Esimerkin vastaus on hyvin tylsä automaatti, joka käyttää neljää läpikäyntiä tarkistaakseen, sisältääkö taulukko luvut 3, 1, 5 ja 2 (tässä järjestyksessä). Kukin läpikäynti käyttää käytännössä vain kahta tilaa, jotka vastaavat sitä, onko se jo löytänyt etsimänsä luvun nykyisellä läpikäynnillä. Jos se saavuttaa taulukon lopun (merkin 0) löytämättä tarvittavaa lukua, se pysähtyy välittömästi ilmoittaen, että kyseinen luku todellakin puuttuu. Muussa tapauksessa se siirtyy seuraavaan läpikäyntiin etsimään seuraavaa lukua. Lopuksi, jos se on löytänyt kaikki neljä tarvittavaa kokonaislukua, luvun 4 täytyy puuttua. Siksi se ei tee viidettä läpikäyntiä etsiäkseen lukua 4 (vaikka se olisi voinut tehdä niin rikkomatta automaatin tilojen ja käytettyjen läpikäyntien määrää koskevia rajoituksia).

Tällä naiivilla lähestymistavalla ei tietenkään ole mitään mahdollisuutta toimia, kun $n = 250$, vaan tarvitaan jotakin paljon parempaa. Esimerkin olemassaolon pääasiallinen tarkoitus on havainnollistaa tulostemuotoa.

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.