Universal Cup Judging System

Universal Cup

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

Ti viene dato un array di $n$ interi compresi tra $1$ e $n+1$. È possibile che alcuni interi compaiano più volte nell'array. Tuttavia, è chiaro che almeno uno degli interi da $1$ a $n+1$ manca dall'array. Il tuo compito è trovare uno qualsiasi di questi interi mancanti. Normalmente sarebbe facile, ma c'è uno sfortunato problema: non c'è abbastanza memoria sul tuo computer per rappresentare l'intero array.

Pertanto, ti viene chiesto di produrre invece un algoritmo di streaming. Informalmente, gli elementi dell'array ti vengono forniti uno alla volta senza alcun modo di accedervi in modo casuale. Tuttavia, c'è una consolazione: dopo aver ricevuto l'ultimo elemento dell'array, puoi ricominciare a leggerlo dall'inizio. Idealmente, vorresti evitare una situazione del genere e risolvere l'intero problema in una sola passata. Tuttavia, a volte (incluso questo stesso problema) possono essere necessarie più passate sull'input per evitare di usare troppa memoria. Devi bilanciare entrambe le esigenze e contemporaneamente non usare troppa memoria e non fare troppe passate sull'array (il problema è banale se ti è consentito memorizzare $n$ bit di memoria o usare $n$ passate).

C'è però ancora un ostacolo. Per ragioni tecniche, devi produrre un automa a stati finiti deterministico (DFA) sull'alfabeto $\{0, 1, \dots, n + 1\}$ che implementi la logica del tuo algoritmo. I caratteri dell'alfabeto corrispondono alle informazioni che ricevi leggendo lo stream: i numeri da $1$ a $n+1$ rappresentano la lettura del corrispondente intero dall'array, mentre il numero $0$ rappresenta il fatto che hai raggiunto la fine dell'array. Dopo le prime 7 volte in cui hai raggiunto la fine dell'array, l'array ti verrà fornito nuovamente nello stesso ordine di prima, terminando sempre con un carattere $0$ che rappresenta la fine dell'array. Pertanto, al tuo DFA verrà fornita in input la stringa $a_1, a_2, \dots, a_n, 0$ per un totale di 8 volte (qui, $a_1, a_2, \dots, a_n$ è l'array nascosto). Infine, in qualsiasi momento dell'esecuzione, il tuo automa può "dire" che conosce già una risposta corretta al problema; in tal caso, l'esecuzione viene interrotta. Se il tuo DFA non lo ha ancora fatto nel momento in cui ha letto l'intero stream (incluso il carattere $0$ alla fine) per 8 volte, non viene accettato come soluzione. Allo stesso modo, se si ferma ma con una risposta errata, non viene accettato comunque.

Enunciamo il problema formalmente. C'è un array nascosto $a_1, a_2, \dots, a_n$ di $n$ interi da $1$ a $n+1$. Nell'esempio, $n = 4$, mentre in tutti gli altri test $n = 250$. Devi specificare una macchina a stati finiti con al massimo 4000 stati, numerati da $0$ a $q - 1$, dove $q \le 4000$ è il numero di stati. Per lo stato $i$ ($0 \le i \le q - 1$), devi specificare $n + 2$ numeri $\delta(i, 0), \delta(i, 1), \dots, \delta(i, n + 1)$. Il numero $\delta(i, j)$ rappresenta il comportamento del tuo DFA quando si trova nello stato $i$ e legge il numero $j$ dall'input. Deve essere un intero compreso tra $-(n + 1)$ e $q - 1$ inclusi. Gli interi negativi corrispondono al fatto che l'esecuzione si arresta e viene fornita una risposta; nello specifico, $-s$ corrisponde al tuo DFA che afferma che $+s$ è una risposta corretta al problema. Gli interi non negativi corrispondono al fatto che l'esecuzione continua e lo stato dell'automa passa da $i$ a $\delta(i, j)$. L'esecuzione dell'automa inizia nello stato $0$.

Si considera che il tuo DFA funzioni correttamente sull'array $a_1, a_2, \dots, a_n$ se si arresta con una risposta corretta in un qualche punto durante la lettura della stringa $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$, dove l'array è ripetuto 8 volte. Si considera che il tuo DFA funzioni correttamente in generale se funziona correttamente su tutti i possibili array $a_1, a_2, \dots, a_n$ di interi da $1$ a $n+1$ (pertanto, le soluzioni probabilistiche sono sconsigliate).

Per $n = 4$, verificheremo il tuo DFA su tutti i possibili array. Per $n = 250$, non abbiamo modo di verificarlo su tutti gli array, quindi lo verificheremo su meno di 5000 array appositamente selezionati. Ci sono due test nel problema; entrambi i test verificano efficacemente che il tuo approccio funzioni correttamente su molti array contemporaneamente.

Input

Un intero $n$, che è uguale a $4$ oppure a $250$.

Output

Sulla prima riga, stampa un singolo intero $q$ ($1 \le q \le 4000$) che indica il numero di stati nel tuo DFA.

Sulla $i$-esima delle seguenti $q$ righe, stampa $n + 2$ interi $\delta(i - 1, 0), \delta(i - 1, 1), \dots, \delta(i - 1, n + 1)$. Devono essere tutti compresi tra $-(n + 1)$ e $q - 1$ inclusi e corrispondere alle transizioni dell'automa. Nota che tutti i numeri devono trovarsi in questo intervallo: anche se una qualche combinazione dello stato $i$ e del numero in input $j$ non può mai essere raggiunta su alcun input valido, il valore di $\delta(i, j)$ che specifichi deve comunque appartenere all'intervallo $[-(n + 1), q - 1]$.

Esempio

Input 1

4

Output 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

Note

La risposta per l'esempio è un automa molto noioso che usa quattro passate per controllare se l'array include i numeri 3, 1, 5 e 2 (in quest'ordine). Ciascuna delle passate usa effettivamente solo due stati che corrispondono all'aver già trovato o meno il numero cercato nella passata corrente. Se raggiunge la fine dell'array (il carattere 0) senza trovare il numero necessario, si ferma immediatamente dicendo che il numero necessario è effettivamente mancante. Altrimenti, procede a usare la passata successiva per cercare il numero successivo. Infine, se ha trovato tutti e quattro gli interi necessari, allora il numero 4 deve per forza mancare. Pertanto, non esegue una quinta passata per cercare il numero 4 (ma avrebbe potuto farlo senza violare le restrizioni sul numero di stati dell'automa e sulle passate utilizzate).

Naturalmente, questo approccio ingenuo non ha alcuna possibilità di funzionare per $n = 250$, ed è necessario qualcosa di molto migliore. Il motivo principale dell'esistenza dell'esempio è illustrare il formato di output.

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.