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$ までの整数のうち少なくとも1つは配列に含まれていないことが明らかです。あなたの仕事は、そのような整数をどれか1つ見つけることです。通常であればこれは簡単ですが、残念な問題があります。コンピュータのメモリが足りず、配列全体を表現できないのです。

そのため、代わりにストリーミングアルゴリズムを作成することが求められます。非公式に言えば、配列の要素は1つずつ順番に与えられ、ランダムアクセスする方法はありません。ただし、1つだけ救いがあります。配列の最後の要素を受け取った後、最初から読み直すことができるのです。理想的にはそのような状況を避け、1回のパス(走査)で問題全体を解きたいところです。しかし、場合によっては(まさにこの問題を含め)、メモリの使いすぎを避けるために入力を複数回走査する必要があります。両方の懸念のバランスを取り、メモリを使いすぎず、かつ配列の走査回数も増やしすぎないようにする必要があります($n$ ビットのメモリを保存したり $n$ 回のパスを使ったりすることが許されれば、問題は自明になります)。

しかし、もう1つ条件があります。技術的な理由により、あなたのアルゴリズムのロジックを実装する、アルファベット $\{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個未満の配列に対して検証します。この問題には2つのテストがあり、どちらのテストもあなたのアプローチが多くの配列に対して同時に正しく動作することを実質的に検査します。

入力

1つの整数 $n$ が与えられます。その値は $4$ または $250$ のいずれかです。

出力

1行目には、あなたの 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

注記

入出力例の解答は、4回のパスを使って配列に数 3, 1, 5, 2 が(この順序で)含まれているかどうかを調べる非常に退屈なオートマトンです。各パスは実質的に、現在のパスで探している数をすでに見つけたかどうかに対応する2つの状態しか使用しません。必要な数を見つけられないまま配列の末尾(文字 0)に到達した場合、必要な数が確かに欠けていると宣言して直ちに停止します。そうでない場合、次のパスを使って次の数を探します。最後に、4つの必要な整数をすべて見つけた場合、数 4 が欠けているはずです。したがって、数 4 を探すための5回目のパスは行いません(ただし、オートマトンの状態数と使用パス数の制限に違反することなく5回目のパスを行うことも可能ではあります)。

もちろん、このような単純なアプローチが $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.