Aidos はパズルを考案し、Temirulan にその解決を挑みました。彼は $1$ から $n$ までの番号が付けられた、$n$ 個の相異なる非負整数からなる数列 $a = a_1, a_2, \dots, a_n$ を選びました。
Temirulan は以下の2種類の質問をすることができます。
ask— 与えられた数列の $i$ 番目の位置にある数値を明らかにします。get_pairwise_xor— 相異なる整数の数列 $i_1, i_2, \dots, i_k$ に対して、数列 $a$ のインデックス $i_1, i_2, \dots, i_k$ にある要素のペアの XOR 値の集合 $\{a_{i_x} \oplus a_{i_y} \mid 1 \leq x, y \leq k\}$ を取得します。
例えば、Aidos が数列 $[1, 5, 6, 3]$ を選んだと仮定します。このとき、質問 ask(2) に対しては数値 $5$ が返され、質問 get_pairwise_xor({3, 4}) に対しては、以下のように計算されるため、数列 $[0, 0, 5, 5]$ が返されます。
- $a_3 \oplus a_4 = 6 \oplus 3 = 5$
- $a_4 \oplus a_3 = 3 \oplus 6 = 5$
- $a_3 \oplus a_3 = 6 \oplus 6 = 0$
- $a_4 \oplus a_4 = 3 \oplus 3 = 0$
Temirulan はこのパズルを解くことができませんでした。あなたの課題は、上記の質問を使用して隠された数列を見つけ出し、彼を助けることです。
入力
提出プログラムは、標準入力から読み込んだり、標準出力へ書き出したり、他のファイルとやり取りしたりしてはいけません。
あなたの課題は、以下の関数を実装することです： int[] guess(int n)
- $n$: 隠された数列の長さ。
- この関数は、各テストケースに対してちょうど1回呼び出されます。
- この関数は、隠された数列を元の順序で返さなければなりません。
あなたの関数は、以下の関数を呼び出すことができます：
int ask(int i)- $i$: 数列のインデックス、$1 \leq i \leq n$。
- この関数は、隠された数列の $i$ 番目の数値を返します。
int[] get_pairwise_xor(int[] pos)- $pos$: 数列のインデックスの空でないリスト。
- $pos$ のすべての要素は相異なる整数でなければなりません。
- $k$ を $pos$ の要素数とすると、$1 \leq pos_i \leq n$ ($1 \leq i \leq k$) です。
- この関数は、$k^2$ 個の要素からなるソートされたリスト、すなわち XOR 値のペアの集合 $\{a_{pos_x} \oplus a_{pos_y} \mid 1 \leq x, y \leq k\}$ を返します。
各テストケースにおいて、両方の関数を合計で $200$ 回を超えて呼び出すことはできません。上記の条件のいずれかに違反した場合、プログラムは Wrong Answer と判定されます。それ以外の場合、プログラムは Accepted と判定され、スコアは ask 関数と get_pairwise_xor 関数の合計呼び出し回数に基づいて計算されます（「小課題」のセクションを参照してください）。
小課題
- $2 \leq n \leq 100$
- 各 $1 \leq i \leq n$ に対して $0 \leq a_i \leq 10^9$
この課題において、グレーダーは適応型ではありません。つまり、数列 $a$ はグレーダーの実行開始時に固定されており、あなたのプログラムからの呼び出しには依存しません。
- (6 点) $n \leq 4$
- (94 点) 追加の制約はありません。この小課題では、スコアは以下の方法で計算されます。$q$ を
ask関数とget_pairwise_xor関数の合計呼び出し回数とします。- $q \leq 15$ の場合、スコアは $94$ です。
- $15 < q \leq 40$ の場合、スコアは $84 - 2(q - 16)$ です。
- $40 < q \leq 50$ の場合、スコアは $35$ です。
- それ以外の場合、スコアは $0$ です。
各小課題のスコアは、その小課題のすべてのテストケースにおける結果のうち、最小のスコアとなります。
注記
XOR 演算はビット単位の排他的論理和です。
隠された数列 $a$ が $[1, 5, 6, 3]$ であるとします。グレーダーが関数を呼び出す際のインタラクションの例を以下に示します。
| 呼び出し | 結果 |
|---|---|
ask(2) |
$5$ |
get_pairwise_xor({1, 2, 3}) |
$\{0, 0, 0, 3, 3, 4, 4, 7, 7\}$ |
ask(3) |
$6$ |
get_pairwise_xor({4, 2}) |
$\{0, 0, 6, 6\}$ |
get_pairwise_xor({2}) |
$\{0\}$ |
サンプルグレーダーは以下の形式で入力を読み取ります： 1行目: $n$ 2行目: $a_1, a_2, \dots, a_n$
システムから xoractive.zip をダウンロードできます。これには Java、C++11、FPC、Python 2 用の例が含まれています。
関数呼び出しのすべての例は上記に記載されています。Python 2 の場合、def guess(n, interactor) 関数を実装する必要があります。ここで interactor はテスト対象のクラスのインスタンスであり、ask および get_pairwise_xor はこのクラスのメソッドです。
xoractive.zip には各言語の解答例が含まれています。
Java 言語での解答の場合、ファイル名とクラス名はそれぞれ Xoractive.java および Xoractive とする必要があります。
Pascal 言語での解答の場合、ファイル名は xoractive.pas とする必要があります。