Universal Cup Judging System

Universal Cup

حد الوقت: 2.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

Dana jest tablica $n$ liczb całkowitych z przedziału od $1$ do $n+1$. Możliwe, że niektóre liczby całkowite występują w tablicy wielokrotnie. Mimo to oczywiste jest, że co najmniej jednej liczby całkowitej z przedziału od $1$ do $n+1$ brakuje w tablicy. Twoim zadaniem jest znalezienie dowolnej takiej liczby całkowitej. Zwykle byłoby to łatwe, ale pojawia się niefortunny problem: w Twoim komputerze nie ma wystarczająco dużo pamięci, aby zapisać całą tablicę.

Dlatego zamiast tego musisz stworzyć algorytm strumieniowy (streaming algorithm). Nieformalnie mówiąc, elementy tablicy są podawane pojedynczo bez możliwości swobodnego dostępu do nich. Jest jednak jedno pocieszenie: po otrzymaniu ostatniego elementu tablicy możesz rozpocząć czytanie jej od początku. Idealnie byłoby uniknąć takiej sytuacji i rozwiązać cały problem w jednym przebiegu. Czasami jednak (w tym również w tym zadaniu) wielokrotne przebiegi po wejściu mogą być konieczne, aby uniknąć zużycia zbyt dużej ilości pamięci. Musisz zrównoważyć obie te kwestie i jednocześnie nie używać zbyt dużo pamięci oraz nie wykonywać zbyt wielu przebiegów po tablicy (zadanie staje się trywialne, jeśli wolno Ci przechować $n$ bitów pamięci lub wykonać $n$ przebiegów).

Jest jednak jeszcze jeden haczyk. Z powodów technicznych musisz wygenerować deterministyczny automat skończony (DFA) nad alfabetem $\{0, 1, \dots, n + 1\}$, implementujący logikę Twojego algorytmu. Znaki alfabetu odpowiadają informacjom otrzymywanym podczas czytania strumienia: liczby od $1$ do $n+1$ oznaczają wczytanie odpowiedniej liczby całkowitej z tablicy, natomiast liczba $0$ oznacza dotarcie do końca tablicy. Po pierwszych 7 razach, gdy dotrzesz do końca tablicy, tablica zostanie podana ponownie w tej samej kolejności co wcześniej, zawsze kończąc się znakiem $0$ oznaczającym koniec tablicy. Tym samym Twój DFA otrzyma napis $a_1, a_2, \dots, a_n, 0$ łącznie 8 razy (tutaj $a_1, a_2, \dots, a_n$ to ukryta tablica). Wreszcie, w dowolnym momencie działania Twój automat może „ogłosić”, że zna już poprawną odpowiedź na zadanie; w takim przypadku wykonanie zostaje zatrzymane. Jeśli Twój DFA nie zrobi tego do momentu 8-krotnego przeczytania całego strumienia (wliczając znak $0$ na końcu), nie zostanie zaakceptowany jako rozwiązanie. Podobnie, jeśli się zatrzyma, ale poda błędną odpowiedź, również nie zostanie zaakceptowany.

Sformułujmy zadanie formalnie. Istnieje ukryta tablica $a_1, a_2, \dots, a_n$ złożona z $n$ liczb całkowitych od $1$ do $n+1$. W przykładzie $n = 4$, a we wszystkich pozostałych testach $n = 250$. Musisz określić maszynę stanów skończonych mającą co najwyżej 4000 stanów, ponumerowanych od $0$ do $q - 1$, gdzie $q \le 4000$ to liczba stanów. Dla stanu $i$ ($0 \le i \le q - 1$) musisz podać $n + 2$ liczb $\delta(i, 0), \delta(i, 1), \dots, \delta(i, n + 1)$. Liczba $\delta(i, j)$ reprezentuje zachowanie Twojego DFA, gdy znajduje się on w stanie $i$ i wczytuje z wejścia liczbę $j$. Musi ona być liczbą całkowitą z przedziału od $-(n + 1)$ do $q - 1$ włącznie. Ujemne liczby całkowite odpowiadają zatrzymaniu wykonania i udzieleniu odpowiedzi; konkretnie, $-s$ oznacza, że Twój DFA twierdzi, iż $+s$ jest poprawną odpowiedzią na zadanie. Nieujemne liczby całkowite oznaczają kontynuację wykonania oraz zmianę stanu automatu z $i$ na $\delta(i, j)$. Wykonanie automatu rozpoczyna się w stanie $0$.

Uznaje się, że Twój DFA działa poprawnie na tablicy $a_1, a_2, \dots, a_n$, jeśli zatrzyma się z poprawną odpowiedzią w pewnym momencie czytania napisu $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$, gdzie tablica jest powtórzona 8 razy. Uznaje się, że Twój DFA działa poprawnie w ogólności, jeśli działa poprawnie na wszystkich możliwych tablicach $a_1, a_2, \dots, a_n$ liczb całkowitych od $1$ do $n+1$ (dlatego rozwiązania probabilistyczne są odradzane).

Dla $n = 4$ sprawdzimy Twój DFA na wszystkich możliwych tablicach. Dla $n = 250$ nie mamy możliwości sprawdzenia go na wszystkich tablicach, więc przetestujemy go na mniej niż 5000 specjalnie wybranych tablicach. W zadaniu są dwa testy; oba testy skutecznie sprawdzają, czy Twoje podejście działa poprawnie na wielu tablicach jednocześnie.

Wejście

Jedna liczba całkowita $n$, równa $4$ lub $250$.

Wyjście

W pierwszym wierszu wypisz jedną liczbę całkowitą $q$ ($1 \le q \le 4000$) oznaczającą liczbę stanów w Twoim DFA.

W $i$-tym z kolejnych $q$ wierszy wypisz $n + 2$ liczb całkowitych $\delta(i - 1, 0), \delta(i - 1, 1), \dots, \delta(i - 1, n + 1)$. Wszystkie one powinny należeć do przedziału od $-(n + 1)$ do $q - 1$ włącznie i odpowiadać przejściom automatu. Zauważ, że wszystkie liczby muszą mieścić się w tym zakresie: nawet jeśli pewna kombinacja stanu $i$ oraz liczby wejściowej $j$ jest nieosiągalna dla żadnego poprawnego wejścia, podana przez Ciebie wartość $\delta(i, j)$ nadal musi należeć do przedziału $[-(n + 1), q - 1]$.

Przykład

Wejście 1

4

Wyjście 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

Uwaga

Odpowiedź dla przykładu to bardzo nudny automat, który wykonuje cztery przebiegi, aby sprawdzić, czy tablica zawiera liczby 3, 1, 5 oraz 2 (w tej kolejności). Każdy z przebiegów używa w praktyce tylko dwóch stanów odpowiadających temu, czy w bieżącym przebiegu znaleziono już szukaną liczbę. Jeśli automat dotrze do końca tablicy (znaku 0) bez znalezienia wymaganej liczby, natychmiast się zatrzymuje, ogłaszając, że tej liczby rzeczywiście brakuje. W przeciwnym razie przechodzi do kolejnego przebiegu w celu poszukania następnej liczby. Wreszcie, jeśli znalazł wszystkie cztery szukane liczby całkowite, to brakować musi liczby 4. Dlatego nie wykonuje piątego przebiegu w poszukiwaniu liczby 4 (choć mógłby to zrobić bez naruszania ograniczeń na liczbę stanów automatu i użytych przebiegów).

Oczywiście to naiwne podejście nie ma żadnych szans zadziałać dla $n = 250$ i potrzebne jest znacznie lepsze rozwiązanie. Głównym celem przykładu jest zilustrowanie formatu wyjścia.

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.