Universal Cup Judging System

Universal Cup

时间限制: 2.0 s 内存限制: 1024 MB 总分: 100 可 Hack ✓
统计

Вам дан массив из $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.