Du får gitt en tabell med $n$ heltall fra $1$ til $n+1$. Det er mulig at noen av heltallene forekommer flere ganger i tabellen. Likevel er det klart at minst ett av heltallene fra $1$ til $n+1$ mangler i tabellen. Din oppgave er å finne et hvilket som helst slikt heltall. Vanligvis ville dette vært enkelt, men det er et uheldig problem: det er ikke nok minne på datamaskinen din til å representere hele tabellen.
Derfor blir du bedt om å lage en strømmealgoritme (streaming algorithm) i stedet. Uformelt sett blir elementene i tabellen gitt til deg ett etter ett uten noen mulighet for direkte tilgang (random access). Det finnes imidlertid én trøst: etter å ha mottatt det siste elementet i tabellen, kan du starte lesingen på nytt fra begynnelsen. Ideelt sett vil du unngå en slik situasjon og løse hele problemet i én gjennomgang. Men noen ganger (inkludert i nettopp dette problemet) kan flere gjennomganger av inndataene være nødvendige for å unngå å bruke for mye minne. Du må balansere begge hensynene og samtidig verken bruke for mye minne eller gjøre for mange gjennomganger av tabellen (problemet er trivielt hvis du får lov til å lagre $n$ biter med minne eller bruke $n$ gjennomganger).
Det er likevel én hake til. Av tekniske grunner må du produsere en deterministisk endelig automat (DFA) over alfabetet $\{0, 1, \dots, n + 1\}$ som implementerer logikken i algoritmen din. Tegnene i alfabetet tilsvarer informasjonen du mottar når du leser strømmen: tallene fra $1$ til $n+1$ representerer lesing av det tilsvarende heltallet fra tabellen, mens tallet $0$ representerer det faktum at du har nådd slutten av tabellen. Etter de første 7 gangene du har nådd slutten av tabellen, vil tabellen bli gitt til deg igjen i samme rekkefølge som før, alltid avsluttet med et $0$-tegn som representerer slutten av tabellen. Dermed vil din DFA bli matet med strengen $a_1, a_2, \dots, a_n, 0$ totalt 8 ganger (her er $a_1, a_2, \dots, a_n$ den skjulte tabellen). Til slutt kan automaten din når som helst under kjøringen «si» at den allerede vet et riktig svar på problemet; i så fall stanses kjøringen. Hvis din DFA ikke har gjort dette innen den har lest hele strømmen (inkludert $0$-tegnet på slutten) 8 ganger, blir den ikke godkjent som en løsning. På samme måte, hvis den stanser, men med feil svar, blir den heller ikke godkjent som en løsning.
La oss formulere problemet formelt. Det finnes en skjult tabell $a_1, a_2, \dots, a_n$ med $n$ heltall fra $1$ til $n+1$. I eksempelet er $n = 4$, og i alle andre tester er $n = 250$. Du må spesifisere en endelig tilstandsmaskin med høyst 4000 tilstander, nummerert fra $0$ til $q - 1$, der $q \le 4000$ er antall tilstander. For tilstanden $i$ ($0 \le i \le q - 1$) må du oppgi $n + 2$ tall $\delta(i, 0), \delta(i, 1), \dots, \delta(i, n + 1)$. Tallet $\delta(i, j)$ representerer oppførselen til din DFA når den er i tilstanden $i$ og leser tallet $j$ fra inndata. Det må være et heltall fra $-(n + 1)$ til og med $q - 1$. Negative heltall tilsvarer at kjøringen stanses og et svar gis; nærmere bestemt tilsvarer $-s$ at din DFA hevder at $+s$ er et riktig svar på problemet. Ikke-negative heltall tilsvarer at kjøringen fortsetter og at automatens tilstand endres fra $i$ til $\delta(i, j)$. Kjøringen av automaten starter i tilstanden $0$.
Din DFA regnes for å fungere korrekt på tabellen $a_1, a_2, \dots, a_n$ hvis den stanser med et riktig svar på et eller annet tidspunkt under lesingen av strengen $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$, der tabellen gjentas 8 ganger. Din DFA regnes for å fungere korrekt generelt hvis den fungerer korrekt på alle mulige tabeller $a_1, a_2, \dots, a_n$ av heltall fra $1$ til $n+1$ (derfor frarådes probabilistiske løsninger).
For $n = 4$ vil vi sjekke din DFA på alle mulige tabeller. For $n = 250$ har vi ikke mulighet til å sjekke den på alle tabeller, så vi vil sjekke den på færre enn 5000 spesielt utvalgte tabeller. Det er to tester i problemet; begge testene sjekker effektivt at tilnærmingen din fungerer korrekt på mange tabeller samtidig.
Inndata
Ett heltall $n$, som enten er lik $4$ eller $250$.
Utdata
På den første linjen skal du skrive ut et enkelt heltall $q$ ($1 \le q \le 4000$) som angir antall tilstander i din DFA.
På den $i$-te av de følgende $q$ linjene skal du skrive ut $n + 2$ heltall $\delta(i - 1, 0), \delta(i - 1, 1), \dots, \delta(i - 1, n + 1)$. De må alle være fra $-(n + 1)$ til og med $q - 1$ og tilsvare overgangene i automaten. Merk at alle tallene må ligge i dette intervallet: selv om en kombinasjon av tilstanden $i$ og inndatatallet $j$ aldri kan nås på noen gyldige inndata, må verdien av $\delta(i, j)$ som du oppgir likevel ligge i intervallet $[-(n + 1), q - 1]$.
Eksempel
Inndata 1
4
Utdata 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
Merk
Svaret for eksempelet er en svært kjedelig automat som bruker fire gjennomganger for å sjekke om tabellen inneholder tallene 3, 1, 5 og 2 (i den rekkefølgen). Hver av gjennomgangene bruker i praksis bare to tilstander som tilsvarer hvorvidt den allerede har funnet tallet den leter etter i den gjeldende gjennomgangen. Hvis den når slutten av tabellen (tegnet 0) uten å finne det nødvendige tallet, stanser den umiddelbart og sier at det nødvendige tallet faktisk mangler. Ellers går den videre til neste gjennomgang for å lete etter det neste tallet. Til slutt, hvis den har funnet alle de fire nødvendige heltallene, må tallet 4 mangle. Derfor gjør den ikke en femte gjennomgang for å lete etter tallet 4 (men den kunne ha gjort det uten å bryte begrensningene på antall tilstander i automaten og antall brukte gjennomganger).
Selvfølgelig har denne naive tilnærmingen ingen sjanse til å fungere for $n = 250$, og noe mye bedre er nødvendig. Hovedgrunnen til at eksempelet finnes, er å illustrere utdataformatet.