Universal Cup Judging System

Universal Cup

Süre Sınırı: 2.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

Du får en array med $n$ heltal från $1$ till $n+1$. Det är möjligt att några av heltalen förekommer flera gånger i arrayen. Det står ändå klart att minst ett av heltalen från $1$ till $n+1$ saknas i arrayen. Din uppgift är att hitta ett godtyckligt sådant heltal. Normalt skulle detta vara enkelt, men det finns ett tråkigt problem: det finns inte tillräckligt med minne i din dator för att representera hela arrayen.

Därför ombeds du att i stället konstruera en strömmande algoritm (streaming algorithm). Informellt sett ges elementen i arrayen till dig ett efter ett utan någon möjlighet till direktåtkomst (random access). Det finns dock en tröst: efter att ha tagit emot det sista elementet i arrayen kan du börja om och läsa den från början igen. Idealt skulle du vilja undvika en sådan situation och lösa hela problemet i ett enda pass. Men ibland (inklusive i just detta problem) kan flera pass över indata vara nödvändiga för att undvika att använda för mycket minne. Du måste balansera båda dessa krav och samtidigt varken använda för mycket minne eller göra för många pass över arrayen (problemet är trivialt om du tillåts lagra $n$ bitar minne eller använda $n$ pass).

Det finns dock ytterligare en hake. Av tekniska skäl måste du producera en deterministisk finit automat (DFA) över alfabetet $\{0, 1, \dots, n + 1\}$ som implementerar logiken i din algoritm. Tecknen i alfabetet motsvarar den information du får när du läser strömmen: talen från $1$ till $n+1$ representerar att motsvarande heltal läses från arrayen, medan talet $0$ representerar att du har nått slutet av arrayen. Efter de första 7 gångerna du har nått slutet av arrayen kommer arrayen att ges till dig igen i samma ordning som tidigare, alltid avslutad med ett $0$-tecken som representerar slutet av arrayen. Därmed kommer din DFA att matas med strängen $a_1, a_2, \dots, a_n, 0$ totalt 8 gånger (här är $a_1, a_2, \dots, a_n$ den dolda arrayen). Slutligen kan din automat när som helst under körningen ”säga” att den redan vet ett korrekt svar på problemet; i så fall avbryts körningen. Om din DFA inte har gjort detta när den har läst hela strömmen (inklusive $0$-tecknet på slutet) 8 gånger, godkänns den inte som en lösning. Likaså godkänns den inte heller om den stannar men ger ett felaktigt svar.

Låt oss formulera problemet formellt. Det finns en dold array $a_1, a_2, \dots, a_n$ med $n$ heltal från $1$ till $n+1$. I exemplet är $n = 4$, och i alla andra tester är $n = 250$. Du måste specificera en finit tillståndsmaskin med högst 4000 tillstånd, numrerade från $0$ till $q - 1$, där $q \le 4000$ är antalet tillstånd. För tillståndet $i$ ($0 \le i \le q - 1$) måste du ange $n + 2$ tal $\delta(i, 0), \delta(i, 1), \dots, \delta(i, n + 1)$. Talet $\delta(i, j)$ representerar beteendet hos din DFA när den befinner sig i tillståndet $i$ och läser talet $j$ från indata. Det måste vara ett heltal från $-(n + 1)$ till och med $q - 1$. Negativa heltal motsvarar att körningen avbryts och ett svar ges; specifikt motsvarar $-s$ att din DFA hävdar att $+s$ är ett korrekt svar på problemet. Icke-negativa heltal motsvarar att körningen fortsätter och att automatens tillstånd ändras från $i$ till $\delta(i, j)$. Körningen av automaten startar i tillståndet $0$.

Din DFA anses fungera korrekt på arrayen $a_1, a_2, \dots, a_n$ om den stannar med ett korrekt svar vid någon tidpunkt under läsningen av strängen $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$, där arrayen upprepas 8 gånger. Din DFA anses fungera korrekt i allmänhet om den fungerar korrekt på alla möjliga arrayer $a_1, a_2, \dots, a_n$ av heltal från $1$ till $n+1$ (därför avråds från probabilistiska lösningar).

För $n = 4$ kommer vi att kontrollera din DFA på alla möjliga arrayer. För $n = 250$ har vi ingen möjlighet att kontrollera den på alla arrayer, så vi kommer att kontrollera den på färre än 5000 särskilt utvalda arrayer. Det finns två tester i problemet; båda testerna kontrollerar effektivt att din metod fungerar korrekt på många arrayer samtidigt.

Indata

Ett heltal $n$, som antingen är lika med $4$ eller $250$.

Utdata

På den första raden ska du skriva ut ett enda heltal $q$ ($1 \le q \le 4000$) som anger antalet tillstånd i din DFA.

På den $i$-te av de följande $q$ raderna ska du skriva ut $n + 2$ heltal $\delta(i - 1, 0), \delta(i - 1, 1), \dots, \delta(i - 1, n + 1)$. De ska alla ligga mellan $-(n + 1)$ och $q - 1$ (inklusive gränserna) och motsvara övergångarna i automaten. Observera att alla tal måste ligga i detta intervall: även om någon kombination av tillståndet $i$ och indatatalet $j$ aldrig kan nås för någon giltig indata, måste värdet på $\delta(i, j)$ som du anger ändå ligga i intervallet $[-(n + 1), q - 1]$.

Exempel

Indata 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

Anmärkning

Svaret i exemplet är en mycket tråkig automat som använder fyra pass för att kontrollera om arrayen innehåller talen 3, 1, 5 och 2 (i den ordningen). Vart och ett av passen använder i praktiken bara två tillstånd som motsvarar huruvida den redan har hittat talet den letar efter under det aktuella passet. Om den når slutet av arrayen (tecknet 0) utan att hitta det nödvändiga talet stannar den omedelbart och meddelar att talet i fråga verkligen saknas. Annars går den vidare till nästa pass för att leta efter nästa tal. Slutligen, om den har hittat alla fyra nödvändiga heltal, måste talet 4 saknas. Därför gör den inget femte pass för att leta efter talet 4 (men den hade kunnat göra det utan att bryta mot begränsningarna för antalet tillstånd och antalet använda pass).

Naturligtvis har denna naiva metod ingen chans att fungera för $n = 250$, och något mycket bättre krävs. Huvudsyftet med exemplet är att illustrera utdataformatet.

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.