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.