Universal Cup Judging System

Universal Cup

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

Вам дано масив із $n$ цілих чисел від $1$ до $n+1$. Можливо, що деякі з чисел зустрічаються в масиві кілька разів. Проте очевидно, що принаймні одне з цілих чисел від $1$ до $n+1$ у масиві відсутнє. Ваше завдання — знайти будь-яке таке число. Зазвичай це було б легко, але є одна прикра проблема: на вашому комп'ютері недостатньо пам'яті, щоб зберегти весь масив.

Тому вам пропонується натомість розробити потоковий алгоритм. Неформально кажучи, елементи масиву подаються вам по одному без можливості довільного доступу до них. Однак є одна втіха: після отримання останнього елемента масиву ви можете почати читання масиву спочатку. В ідеалі хотілося б уникнути такої ситуації й розв'язати всю задачу за один прохід. Проте іноді (включно з цією задачею), щоб уникнути використання надто великого обсягу пам'яті, може знадобитися кілька проходів по вхідних даних. Вам потрібно збалансувати обидві вимоги й одночасно використовувати не надто багато пам'яті та робити не надто багато проходів по масиву (задача тривіальна, якщо вам дозволено зберігати $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 разів, він не зараховується як розв'язок. Аналогічно, якщо він зупиниться, але видасть неправильну відповідь, він також не зараховується як розв'язок.

Сформулюємо задачу формально. Є прихований масив $a_1, a_2, \dots, a_n$ із $n$ цілих чисел від $1$ до $n+1$. У прикладі $n = 4$, у всіх інших тестах $n = 250$. Вам необхідно задати скінченний автомат, що має не більше 4000 станів, пронумерованих від $0$ до $q - 1$, де $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$.

Вважається, що ваш ДСА працює коректно на масиві $a_1, a_2, \dots, a_n$, якщо він зупиняється з правильною відповіддю в деякий момент читання рядка $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$, де масив повторено 8 разів. Вважається, що ваш ДСА працює коректно загалом, якщо він працює коректно на всіх можливих масивах $a_1, a_2, \dots, a_n$ із цілих чисел від $1$ до $n+1$ (тому ймовірнісні розв'язки не рекомендуються).

При $n = 4$ ми перевіримо ваш ДСА на всіх можливих масивах. При $n = 250$ ми не маємо можливості перевірити його на всіх масивах, тому ми перевіримо його менш ніж на 5000 спеціально вибраних масивах. У задачі два тести; обидва тести фактично перевіряють, що ваш підхід працює коректно на багатьох масивах одночасно.

Вхідні дані

Одне ціле число $n$, яке дорівнює або $4$, або $250$.

Вихідні дані

У першому рядку виведіть одне ціле число $q$ ($1 \le q \le 4000$), що позначає кількість станів у вашому ДСА.

В $i$-му з наступних $q$ рядків виведіть $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.