Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

俾你一個由 $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.