Universal Cup Judging System

Universal Cup

Límite de tiempo: 2.0 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓
Estadísticas

$1$부터 $n+1$까지의 정수 $n$개로 이루어진 배열이 주어집니다. 배열에 일부 정수가 여러 번 나타날 수도 있습니다. 그럼에도 불구하고, $1$부터 $n+1$까지의 정수 중 적어도 하나는 배열에 빠져 있다는 것이 분명합니다. 여러분의 과제는 그러한 정수를 아무것이나 하나 찾는 것입니다. 보통이라면 쉬운 일이겠지만, 안타까운 문제가 하나 있습니다. 컴퓨터에 배열 전체를 표현할 만큼 충분한 메모리가 없다는 것입니다.

따라서 여러분은 대신 스트리밍 알고리즘을 만들어야 합니다. 비공식적으로 말하면, 배열의 원소들이 하나씩 차례대로 주어지며 임의로 접근(random access)할 방법이 없습니다. 하지만 한 가지 위안이 되는 점은, 배열의 마지막 원소를 받은 후 처음부터 다시 읽기를 시작할 수 있다는 것입니다. 이상적으로는 이러한 상황을 피하고 한 번의 패스(pass)로 문제 전체를 해결하고 싶을 것입니다. 그러나 때로는 (바로 이 문제를 포함하여) 메모리를 너무 많이 사용하는 것을 피하기 위해 입력을 여러 번 훑는 패스가 필요할 수 있습니다. 여러분은 두 가지 문제를 모두 조율하여 메모리를 너무 많이 사용하지 않으면서 동시에 배열을 너무 여러 번 훑지 않아야 합니다 ($n$비트의 메모리를 저장하거나 $n$번의 패스를 사용하는 것이 허용된다면 문제는 자명해집니다).

하지만 여전히 한 가지 함정이 더 있습니다. 기술적인 이유로, 여러분은 알고리즘의 논리를 구현하는 알파벳 $\{0, 1, \dots, n + 1\}$ 상의 결정론적 유한 오토마타(DFA)를 만들어야 합니다. 알파벳의 각 문자는 스트림을 읽을 때 받는 정보에 대응합니다. $1$부터 $n+1$까지의 수는 배열에서 해당하는 정수를 읽는 것을 나타내며, 수 $0$은 배열의 끝에 도달했다는 사실을 나타냅니다. 처음 7번 배열의 끝에 도달한 후에는 배열이 이전과 동일한 순서로 다시 주어지며, 항상 배열의 끝을 나타내는 $0$ 문자로 끝납니다. 따라서 여러분의 DFA에는 문자열 $a_1, a_2, \dots, a_n, 0$이 총 8번 입력됩니다 (여기서 $a_1, a_2, \dots, a_n$은 숨겨진 배열입니다). 마지막으로, 실행 중 어느 순간에나 오토마타는 문제의 올바른 답을 이미 알고 있다고 "선언"할 수 있으며, 그 경우 실행이 중지됩니다. 전체 스트림(끝에 있는 $0$ 문자 포함)을 8번 읽을 때까지 DFA가 그렇게 하지 않으면 올바른 해답으로 인정되지 않습니다. 마찬가지로 실행이 중지되었더라도 틀린 답을 내놓으면 해답으로 인정되지 않습니다.

문제를 공식적으로 설명하겠습니다. $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)$는 DFA가 상태 $i$에 있을 때 입력에서 수 $j$를 읽었을 때의 동작을 나타냅니다. 이 값은 $-(n + 1)$ 이상 $q - 1$ 이하의 정수여야 합니다. 음의 정수는 실행이 중지되고 답이 주어지는 상황에 대응합니다. 구체적으로, $-s$는 여러분의 DFA가 $+s$가 문제의 올바른 답이라고 주장하는 것에 대응합니다. 음이 아닌 정수는 실행이 계속되고 오토마타의 상태가 $i$에서 $\delta(i, j)$로 변경되는 것에 대응합니다. 오토마타의 실행은 상태 $0$에서 시작합니다.

문자열 $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번 반복됨)을 읽는 도중 어느 시점에 올바른 답을 내고 정지한다면, 여러분의 DFA는 배열 $a_1, a_2, \dots, a_n$에 대해 올바르게 작동하는 것으로 간주됩니다. $1$부터 $n+1$까지의 정수로 이루어진 가능한 모든 배열 $a_1, a_2, \dots, a_n$에 대해 올바르게 작동한다면, 여러분의 DFA는 일반적으로 올바르게 작동하는 것으로 간주됩니다 (따라서 확률적 풀이는 권장되지 않습니다).

$n = 4$인 경우 가능한 모든 배열에 대해 DFA를 검사합니다. $n = 250$인 경우 모든 배열에 대해 검사할 방법이 없으므로, 특별히 선택된 5000개 미만의 배열에 대해 검사합니다. 이 문제에는 두 개의 테스트가 있으며, 두 테스트 모두 여러분의 접근 방식이 동시에 많은 배열에서 올바르게 작동하는지를 효과적으로 확인합니다.

입력

정수 $n$이 하나 주어지며, 그 값은 $4$ 또는 $250$입니다.

출력

첫 번째 줄에 DFA의 상태 개수를 나타내는 단일 정수 $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.