Universal Cup Judging System

Universal Cup

時間限制: 2.0 s 記憶體限制: 1024 MB 總分: 100 可 Hack ✓
统计

給你一個由 $n$ 個介於 $1$ 到 $n+1$ 之間的整數所組成的陣列。陣列中某些整數可能會出現多次。顯然,在 $1$ 到 $n+1$ 的整數中,至少有一個整數不在陣列裡。你的任務是找出任意一個這樣的整數。通常這很簡單,但有個不幸的問題:你的電腦沒有足夠的記憶體來儲存整個陣列。

因此,題目要求你設計一個串流演算法(streaming algorithm)。非正式地說,陣列的元素會逐一提供給你,你無法隨機存取它們。不過有一點值得慶幸:在收到陣列的最後一個元素之後,你可以重新從頭開始讀取它。理想情況下,你會希望避免這種情況,並在一次掃描(one pass)內解決整個問題。然而,有時(包括本題)為了避免使用過多記憶體,對輸入進行多次掃描可能是必要的。你必須在兩者之間取得平衡,同時不使用太多記憶體,也不對陣列進行太多次掃描(如果允許你儲存 $n$ 個位元的記憶體或進行 $n$ 次掃描,這個問題就變得微不足道了)。

然而還有一個限制。出於技術原因,你需要產生一個基於字母表 $\{0, 1, \dots, n + 1\}$ 的確定性有限狀態自動機(DFA)來實作你的演算法邏輯。字母表中的字元對應於你讀取串流時收到的資訊:$1$ 到 $n+1$ 的數字代表從陣列讀取到對應的整數,而數字 $0$ 則代表你已經到達陣列的結尾。在前 7 次到達陣列結尾之後,陣列會以與先前相同的順序再次提供給你,且每次皆以代表陣列結尾的 $0$ 字元結束。因此,你的 DFA 總共會被餵入 8 次字串 $a_1, a_2, \dots, a_n, 0$(此處 $a_1, a_2, \dots, a_n$ 是隱藏的陣列)。最後,在執行的任何時刻,你的自動機都可以「宣布」它已經知道該問題的某個正確答案;在這種情況下,執行將會停止。如果你的 DFA 在完整讀取整個串流(包含結尾的 $0$ 字元)8 次後仍未宣布答案,則不會被接受為正確解答。同樣地,如果它停止了卻給出錯誤的答案,也不會被接受。

讓我們正式地定義這個問題。有一個由 $n$ 個介於 $1$ 到 $n+1$ 的整數所組成的隱藏陣列 $a_1, a_2, \dots, a_n$。在範例中 $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)$ 代表當你的 DFA 處於狀態 $i$ 且從輸入讀取到數字 $j$ 時的行為。它必須是介於 $-(n + 1)$ 到 $q - 1$ 之間(含兩端)的整數。負整數代表執行停止並給出答案;具體而言,$-s$ 代表你的 DFA 宣稱 $+s$ 是本題的一個正確答案。非負整數則代表執行繼續,且自動機的狀態從 $i$ 轉移至 $\delta(i, j)$。自動機的執行從狀態 $0$ 開始。

如果你的 DFA 在讀取字串 $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$ 上運作正確。如果你的 DFA 在所有可能由 $1$ 到 $n+1$ 的整數組成的陣列 $a_1, a_2, \dots, a_n$ 上都能正確運作,則視為它在一般情況下運作正確(因此不建議使用機率性解法)。

對於 $n = 4$,我們會在所有可能的陣列上測試你的 DFA。對於 $n = 250$,我們無法在所有陣列上測試,因此我們會在少於 5000 個特別挑選的陣列上進行測試。本題共有兩筆測試資料;兩筆測試資料都會有效地檢驗你的方法是否能同時在許多陣列上正確運作。

輸入格式

一個整數 $n$,其值為 $4$ 或 $250$。

輸出格式

第一行請輸出一個整數 $q$($1 \le q \le 4000$),代表你的 DFA 的狀態數。

在接下來的 $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.