Universal Cup Judging System

Universal Cup

実行時間制限: 2.0 s メモリ制限: 1024 MB 満点: 100 ハック可能 ✓
統計

Сізге $1$-ден $n+1$-ге дейінгі $n$ бүтін саннан тұратын массив берілген. Массивте кейбір бүтін сандар бірнеше рет кездесуі мүмкін. Соған қарамастан, $1$-ден $n+1$-ге дейінгі бүтін сандардың кем дегенде біреуі массивте жоқ екені анық. Сіздің міндетіңіз — осындай кез келген бүтін санды табу. Әдетте бұл оңай болар еді, бірақ бір қолайсыз мәселе бар: компьютеріңізде бүкіл массивті сақтауға жады жеткіліксіз.

Сондықтан сізден оның орнына ағындық алгоритм (streaming algorithm) құрастыру сұралады. Бейресми түрде айтқанда, массив элементтері сізге бір-бірлеп беріледі және оларға еркін қол жеткізу (random access) мүмкіндігі жоқ. Дегенмен, бір жұбаныш бар: массивтің соңғы элементін алғаннан кейін, оны басынан бастап қайта оқуды бастай аласыз. Ең дұрысы, мұндай жағдайды болдырмай, бүкіл есепті бір өтуде (one pass) шешкіңіз келер еді. Алайда кейде (осы есептің өзін қоса алғанда) тым көп жады жұмсамау үшін кіріс деректерді бірнеше рет оқып шығу қажет болуы мүмкін. Сіз екі талапты да теңестіріп, бір мезгілде тым көп жады қолданбауыңыз және массивті тым көп рет қайталап оқымауыңыз керек (егер сізге $n$ бит жады сақтауға немесе $n$ рет өтуге рұқсат етілсе, есеп тривиальды болады).

Дегенмен, тағы бір кілтипан бар. Техникалық себептерге байланысты сізге алгоритміңіздің логикасын жүзеге асыратын $\{0, 1, \dots, n + 1\}$ әліпбиі үстіндегі детерминирленген ақырлы автоматты (ДКА) құру қажет. Әліпби таңбалары ағынды оқу кезінде алатын ақпаратқа сәйкес келеді: $1$-ден $n+1$-ге дейінгі сандар массивтен сәйкес бүтін санды оқуды білдіреді, ал $0$ саны массивтің соңына жеткеніңізді білдіреді. Массивтің соңына алғашқы 7 рет жеткеннен кейін, массив сізге бұрынғыдай ретпен қайтадан беріледі және әрқашан массивтің соңын білдіретін $0$ таңбасымен аяқталады. Осылайша, сіздің ДКА-ңызға $a_1, a_2, \dots, a_n, 0$ жолы барлығы 8 рет беріледі (мұндағы $a_1, a_2, \dots, a_n$ — жасырын массив). Соңында, орындалудың кез келген сәтінде автоматыңыз есептің қандай да бір дұрыс жауабын білетінін «айта» алады; бұл жағдайда орындалу тоқтатылады. Егер сіздің ДКА-ңыз бүкіл ағынды (соңындағы $0$ таңбасын қоса алғанда) 8 рет оқып біткенге дейін олай етпесе, ол шешім ретінде қабылданбайды. Дәл сол сияқты, егер ол тоқтап, бірақ қате жауап берсе, ол да шешім ретінде қабылданбайды.

Есепті формалды түрде баяндайық. $1$-ден $n+1$-ге дейінгі $n$ бүтін саннан тұратын жасырын $a_1, a_2, \dots, a_n$ массиві бар. Мысалда $n = 4$, ал барлық басқа тестілерде $n = 250$. Сізге $0$-ден $q - 1$-ге дейін нөмірленген ең көбі 4000 күйі бар ақырлы күйлер машинасын көрсету керек, мұндағы $q \le 4000$ — күйлер саны. $i$ күйі үшін ($0 \le i \le q - 1$) сізге $n + 2$ санды $\delta(i, 0), \delta(i, 1), \dots, \delta(i, n + 1)$ көрсету қажет. $\delta(i, j)$ саны ДКА $i$ күйінде тұрып, кірістен $j$ санын оқыған кездегі оның әрекетін білдіреді. Ол $-(n + 1)$-ден $q - 1$-ге дейінгі (шеткі мәндерді қоса алғанда) бүтін сан болуы тиіс. Теріс бүтін сандар орындалудың тоқтатылып, жауап берілуіне сәйкес келеді; атап айтқанда, $-s$ мәні сіздің ДКА-ңыздың $+s$ санын есептің дұрыс жауабы деп мәлімдеуіне сәйкес келеді. Теріс емес бүтін сандар орындалудың жалғасуына және автомат күйінің $i$-ден $\delta(i, j)$-ге ауысуына сәйкес келеді. Автоматтың орындалуы $0$ күйінен басталады.

Егер сіздің ДКА-ңыз массив 8 рет қайталанатын $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$ жолын оқудың белгілі бір сәтінде дұрыс жауаппен тоқтаса, ол $a_1, a_2, \dots, a_n$ массивінде дұрыс жұмыс істейді деп есептеледі. Егер сіздің ДКА-ңыз $1$-ден $n+1$-ге дейінгі бүтін сандардан тұратын барлық мүмкін $a_1, a_2, \dots, a_n$ массивтерінде дұрыс жұмыс істесе, ол жалпы жағдайда дұрыс жұмыс істейді деп есептеледі (сондықтан ықтималдық шешімдер ұсынылмайды).

$n = 4$ болғанда, біз сіздің ДКА-ңызды барлық мүмкін массивтерде тексереміз. $n = 250$ болғанда, оны барлық массивтерде тексеруге мүмкіндігіміз жоқ, сондықтан біз оны арнайы таңдалған 5000-нан аз массивте тексереміз. Есепте екі тест бар; екі тест те сіздің тәсіліңіздің бір мезгілде көптеген массивтерде дұрыс жұмыс істейтінін тиімді түрде тексереді.

Кіріс деректер

$4$-ке немесе $250$-ге тең бір бүтін сан $n$.

Шығыс деректер

Бірінші жолда ДКА-дағы күйлер санын білдіретін бір бүтін сан $q$ ($1 \le q \le 4000$) шығарыңыз.

Келесі $q$ жолдың $i$-ші жолында $n + 2$ бүтін санды $\delta(i - 1, 0), \delta(i - 1, 1), \dots, \delta(i - 1, n + 1)$ шығарыңыз. Олардың барлығы $-(n + 1)$-ден $q - 1$-ге дейінгі (шеткі мәндерді қоса алғанда) аралықта болуы және автоматтың өтулеріне сәйкес келуі керек. Барлық сандар осы ауқымда болуы керек екеніне назар аударыңыз: тіпті егер $i$ күйі мен кіріс саны $j$-дің қандай да бір комбинациясына ешбір жарамды кірісте қол жеткізу мүмкін болмаса да, сіз көрсеткен $\delta(i, j)$ мәні бәрібір $[-(n + 1), q - 1]$ ауқымында болуы тиіс.

Мысал

Кіріс деректер 1

4

Шығыс деректер 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

Ескертпе

Мысалдағы жауап — массивте 3, 1, 5 және 2 сандарының (осы ретпен) бар-жоғын тексеру үшін төрт өтуді пайдаланатын өте қарапайым автомат. Әрбір өту іс жүзінде ағымдағы өтуде іздеп жатқан санды тапқан-таппағанына сәйкес келетін екі күйді ғана пайдаланады. Егер ол қажетті санды таппай массивтің соңына (0 таңбасына) жетсе, қажетті санның шынымен жоқ екенін айтып, бірден тоқтайды. Әйтпесе, ол келесі санды іздеу үшін келесі өтуге көшеді. Соңында, егер ол барлық төрт қажетті бүтін санды тапса, онда 4 саны жоқ болуы керек. Сондықтан ол 4 санын іздеу үшін бесінші өтуді жасамайды (бірақ автомат күйлерінің саны мен пайдаланылған өтулер санына қойылған шектеулерді бұзбай-ақ жасай алар еді).

Әрине, бұл қарапайым тәсілдің $n = 250$ үшін жұмыс істеу мүмкіндігі мүлдем жоқ және одан әлдеқайда жақсырақ нәрсе қажет. Мысалдың негізгі мақсаты — шығыс деректер пішімін көрсету.

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.