Вам дан массив из $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$, и требуется нечто гораздо лучшее. Основная цель примера — проиллюстрировать формат выходных данных.