/
実行時間制限: 2 sec / メモリ制限: 1024 MiB
Submission on AtCoder
When using C++
- Include
Anna.handBruno.h, and implement all the functions in one source file.- Do not use standard input/output or file input/output.
When using other languages
Three processes run: the grader, your program with
argv[1]set to0(Anna), and your program withargv[1]set to1(Bruno). The time and memory usage of these processes are added together.Anna
When
argv[1]is0, act as Anna. First read the integer Q from one line. Then process Q fortune tellings as follows:
- Read N from one line.
-1on one line.- Repeat the following N times: read the number A written on the drawn card, then print an integer x satisfying -1 \le x \le l, where l is the number of cards currently on the table. The meaning of x is the same as the argument of
DrawCard.- Finally, read a line containing
-1.Bruno
When
argv[1]is1, act as Bruno. First read the integer Q from one line. Then process Q fortune tellings. For each one, read:N L C[0] C[1] \cdots C[L - 1]Print the result of the fortune-telling on one line.
Notes
- Flush standard output after every output.
- If your output is invalid or a wrong-answer condition is met, the next input is
-2. Terminate your program immediately in this case.
Score: 100 points
Problem Statement
Anna and Bruno like fortune-telling and enjoy playing various styles of fortune-telling together. Today, they will play fortune-telling using cards, which is described below. They will play it for Q times.
- They prepare many cards with 0 or 1 written on each one, shuffle them, and pile them up on the deck.
-
Anna draws N (= 900) cards from the deck, one at a time. Anna and Bruno know the value of N. Every time she draws a card, she decides whether to discard the card or put the card on the table.
- If she selects to put the card on the table, she inserts the card into the sequence of cards on the table.
- More formally, when there are l cards on the table, she designates a non-negative integer x (0 \le x \le l) and puts the card immediately right to the x-th leftmost card on the table. In the case of x = 0, she puts the card on the leftmost of the sequence of cards on the table.
-
The procedure for Anna finishes when she draws and processes N cards. The result of the fortune-telling is the number of cards with 1 among the N cards.
- After Anna finishes her procedure, Bruno sees the sequence of cards on the table. Using the information, he needs to guess the result of the fortune-telling. If he guesses correctly, the fortune-telling is a success.
The fortune-telling is considered more proficient when fewer cards are on the table. Write a program to implement Anna’s and Bruno’s strategies to succeed in all Q fortune tellings. In this task, the fewer cards Anna puts on the table, the higher the score will be.
Implementation Details
You should submit two files.
The first file is Anna.cpp. This file is intended to implement Anna’s strategy and should implement the following function. The program should include Anna.h using the preprocessor directive #include.
-
void Anna(int N)This function is called Q times. The i-th call (1 \le i \le Q) of this function corresponds to Anna’s procedure in the i-th fortune-telling.
- The parameter
Nis the number of cards that Anna draws.
- The parameter
For each call of the function Anna, this function must call the following function N + 1 times.
-
int DrawCard(int x)Using this function, Anna draws the card from the deck, and selects whether to discard it or put it on the table. She obtains the number written on the j-th card via the return value of the j-th call (1 \le j \le N) of this function. She designates the operation for the (k - 1)-th card via the parameter for the k-th call (2 \le k \le N + 1) of this function.
- The return value of the j-th call (1 \le j \le N) of this function is 0 or 1, representing the number written on the j-th card.
- The return value of the (N + 1)-th call of this function is - 1, representing that Anna finished drawing cards.
- The parameter x for the 1-st call of this function must satisfy x = -1. If not, your program will be judged as Wrong Answer [1].
- The parameter x for the k-th call of this function represents the operation for the (k - 1)-th card. If x = - 1, the (k - 1)-th card will be discarded. If 0 \le x, the (k - 1)-th card will be put immediately right to the x-th leftmost card on the table. In the case of x = 0, the card will be put on the leftmost of the sequence of cards on the table. Here, the parameter must satisfy -1 \le x \le l, where l is the current number of cards on the table. If not, your program will be judged as Wrong Answer [2].
- If the number of calls of the function DrawCard is not N + 1, your program will be judged as Wrong Answer [3].
The second file is Bruno.cpp. This file is intended to implement Bruno’s strategy and should implement the following function. The program should include Bruno.h using the preprocessor directive #include.
-
int Bruno(int N, int L, std::vector<int> C)This function is called exactly once after each call of the function Anna, totaling Q times. The i-th call (1 \le i \le Q) of this function corresponds to Bruno’s procedure in the i-th fortune-telling. It must return the number of cards with 1 among the cards Anna drew.
- The parameter
Nis the number of cards that Anna drew. - The parameter
Lis the number of cards on the table. - The parameter
Cis the array of length L, where \texttt{C}[l - 1] is the number written on the l-th leftmost card (1 \le l \le L) on the table. - If the return value of the function Bruno is not equal to the number of cards with 1 among the cards Anna drew, your program will be judged as Wrong Answer [4].
- The parameter
Important Notices
- Your program can implement other functions for internal use, or use global variables. Submitted files will be compiled with the grader, and become a single executable file. All global variables and internal functions should be declared in an unnamed namespace to avoid confliction with other files. When it is graded, it will be executed as two processes of Anna and Bruno. The process of Anna and the process of Bruno cannot share global variables.
- Your program must not use the standard input and the standard output. Your program must not communicate with other files by any method. However, your program may output debugging information to the standard error.
Compilation and Test Run
You can download an archive file from the contest webpage which contains the sample grader to test your program. The archive file also contains a sample source file of your program.
The sample grader is the file grader.cpp. In order to test your program, put grader.cpp, Anna.cpp, Bruno.cpp, Anna.h, Bruno.h in the same directory, and run the following command to compile your programs.
g++ -std=gnu++20 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp
Instead, you may run compile.sh contained in the archive file.
./compile.sh
When the compilation succeeds, the executable file grader is generated.
Note that the actual grader is different from the sample grader. The sample grader will be executed as a single process, which will read input data from the standard input and write the results to the standard output and the standard error output.
Input for the Sample Grader
The sample grader reads the following data from the standard input.
Q N
A_{1,1} A_{1,2} \cdots A_{1,N}
A_{2,1} A_{2,2} \cdots A_{2,N}
\vdots
A_{Q,1} A_{Q,2} \cdots A_{Q,N}
A_{i,j} (1 \le i \le Q, 1 \le j \le N) is the number written on the j-th card Anna draws in the i-th fortune telling.
Output of the Sample Grader
The sample grader outputs the following information to the standard output and the standard error output (quotes for clarity).
- If the program is judged as correct, the sample grader outputs the maximum value of the number of cards on the table in the format “
Accepted: 100”. - If the program is judged as wrong answer, the sample grader outputs the type of wrong answer in the format “
Wrong Answer [1]”.
If your program meets the conditions of several types of wrong answer, the sample grader reports only one of them. The sample grader may terminate the execution when one of the conditions for wrong answer is met.
Grading Considerations
The actual grader is not adaptive for all testcases. It means that the sequence of numbers written on the cards is fixed before the program’s execution.
Constraints
All the input data satisfy the following conditions.
- 1 \le Q \le 100.
- N = 900.
- A_{i,j} is either 0 or 1 (1 \le i \le Q, 1 \le j \le N).
Grading
If your program is judged as any type of Wrong Answer [1] – [4] (see Implementation Details), Time Limit Exceeded, Memory Limit Exceeded, or Runtime Error, in any testcase, your score is 0 points.
If your program is judged as correct for all testcases, your score is determined by the maximum number of calls for the function DrawCard with parameter 0 \le x, among all plays of the fortune-telling for all testcases. Let L be this number. Your score will be:
- 500 < L: 3 points
- 14 < L \le 500: \left\lfloor 100 \times \left(\dfrac{2.5}{L - 11.5}\right)^{0.35}\right\rfloor points
- L \le 14: 100 points
Sample Communication
Here is a sample input for the sample grader and corresponding function calls.
Sample Input 1
2 5 0 1 0 0 1 1 1 0 1 0
Sample Function Calls
| Call | Return Value | Call | Return Value |
|---|---|---|---|
Anna(5) |
|||
DrawCard(-1) |
0 |
||
DrawCard(0) |
1 |
||
DrawCard(-1) |
0 |
||
DrawCard(1) |
0 |
||
DrawCard(-1) |
1 |
||
DrawCard(1) |
-1 |
||
Bruno(5, 3, [0, 1, 0]) |
2 |
||
Anna(5) |
|||
DrawCard(-1) |
1 |
||
DrawCard(0) |
1 |
||
DrawCard(1) |
0 |
||
DrawCard(2) |
1 |
||
DrawCard(-1) |
0 |
||
DrawCard(1) |
-1 |
||
Bruno(5, 4, [1, 0, 1, 0]) |
3 |
The sample input consists of Q (= 2) plays of fortune-telling, and the number of cards Anna draws from the deck is N (= 5). In this example, in the first fortune-telling, Anna plays in the following procedure:
- Anna draws a card from the deck. The number written on the card is 0.
- Anna selects to put the card on the table, and puts it on the left of the sequence of cards on the table. Then, the sequence of cards becomes 0. Anna draws another card from the deck, and 1 is written on it.
- Anna selects to discard the card. Then, Anna draws another card from the deck, and 0 is written on it.
- Anna selects to put the card on the table, and puts the card immediately right to the 1-st leftmost card on the table. Then, the sequence of cards becomes 0, 0. Anna draws another card from the deck, and 0 is written on it.
- Anna selects to discard the card. Then, Anna draws another card from the deck, and 1 is written on it.
- Anna selects to put the card on the table, and puts the card immediately right to the 1-st leftmost card on the table. Then, the sequence of cards becomes 0, 1, 0.
Then, Bruno sees the sequence of cards: 0, 1, 0. Based on this information, Bruno guesses that the number of cards with 1 among the cards Anna drew is 2. Since this is correct, fortune-telling is a success. The number of cards Anna put on the table is L = 3.
In the second fortune-telling, the number of cards Anna put on the table is L = 4.
Note that this sample input does not satisfy the constraints of the problem. The file sample-01-in.txt, which can be downloaded from the contest site, corresponds to Sample Input 1. The file sample-02-in.txt, which can be downloaded from the contest site, is a sample input that satisfies the constraints.
AtCoder での提出方法
C++ を使用する場合
Anna.hとBruno.hを include し,全ての関数を 1 つのファイルに実装してください.- 標準入出力やファイルへの入出力を使用しないでください.
その他の言語を使用する場合
- ジャッジ
argv[1]を0として起動されたあなたのプログラム(Anna 側)argv[1]を1として起動されたあなたのプログラム(Bruno 側)の 3 つのプログラムが実行されます.実行時間・使用メモリはこれらの合計で計測されます.
Anna 側
argv[1]が0のとき,Anna 側として振る舞ってください.まず,以下の形式で入力を読み込んでください.
Qその後,Q 回の占いを行ってください.
占い
まず,以下の形式で入力を読み込んでください.
N次に,
-1を 1 行で出力してください.その後,以下を N 回繰り返してください.
- Anna が引いたカードに書かれた数 A が 1 行で与えられます.
- -1 \leqq x \leqq l を満たす整数 x を 1 行で出力してください.
最後に,
-1を含む 1 行を読み込んでください.Bruno 側
argv[1]が1のとき,Bruno 側として振る舞ってください.まず,以下の形式で入力を読み込んでください.
Qその後,Q 回の占いを行ってください.
占い
まず,以下の形式で入力を読み込んでください.
N L C[0] C[1] \cdots C[L - 1]その後,占いの結果を 1 行で出力してください.
その他
- 各出力の後には必ず flush をしてください.
- 出力の形式が正しくない場合や不正解の条件に当てはまったとき,与えられる入力は
-2となります.この場合,ただちにプログラムを終了してください.
配点 : 100 点
問題文
Anna と Bruno は占いが好きでいつも二人で様々な占いをしている.今日は 0 か 1 が書かれたカードを使って Q 回の占いを行うことにした.この占いは二人が協力して行う必要があり,1 回の占いを行う具体的な方法は次のようなものである.
- 0 か 1 が書かれたカードをたくさん用意し,シャッフルして山札にする.
- Anna は山札からカードを 1 枚ずつ,合計 N (=900) 枚引く.ここで,Anna と Bruno は N の値を知っている.Anna はカードを 1 枚引く度にそのカードを捨てるか,場に出して並べるかを選択する.
- 場に出して並べることを選択した場合は,すでに場に並べてあるカードの列の好きな位置に,今回並べるカードを挿入して並べる.
- 具体的には,すでに場に l 枚のカードが並べてある場合,非負整数 x (0 \leqq x \leqq l) を指定して,場に並べてあるカードの列の左から x 枚目のカードのすぐ右に挿入することができる.ただし x=0 のときはカードの列の一番左に挿入するとする.
- Anna が N 枚のカードを引き終わると,Anna の役割は終了である.引いた N 枚のカードのうち 1 の書かれたカードの枚数が占いの結果である.
- Bruno は最後に場に並べてあるカードの列のみを見て,占いの結果を推測する.Bruno が占いの結果を正しく答えることができれば占いは成功である.
この占いにおいては,場に出すカードの枚数が少ないほど上手な占いであるとされる.Anna と Bruno が Q 回の占いを成功させるための戦略を実装したプログラムを作成せよ.この課題では,Anna が場に出すカードの枚数が少ないほど,あなたは高得点を得る.
実装の詳細
あなたは 2 つのファイルを提出しなければならない.
1 つ目のファイルは Anna.cpp という名前である.このファイルは Anna の戦略を実装したファイルであり,以下の関数を実装していなければならない.また,#include プリプロセッサ指令によって Anna.h を読み込むこと.
-
void Anna(int N)この関数は,合計 Q 回呼び出される.i 回目 (1 \leqq i \leqq Q) の呼び出しは,i 回目の占いにおける Anna の手順に相当する. - 数
Nは,Anna が山札からカードを引く枚数 N である.
関数 Anna の 1 回の呼び出しについて,以下の関数を N+1 回呼び出さなければならない.
-
int DrawCard(int x)この関数を用いて,山札からカードを引き,そのカードを捨てるか,場に出して並べるかを選択する.j 回目 (1 \leqq j \leqq N) の呼び出しの戻り値で,j 枚目に引いたカードに書かれた数を受け取る.k 回目 (2 \leqq k \leqq N+1) の呼び出しの引数で k - 1 枚目に引いたカードに対する操作を指定する. - j 回目 (1\leqq j \leqq N) の呼び出しにおける戻り値は 0 または 1 であり,Anna が j 枚目に引いたカードに書かれた数を表す. - N+1 回目の呼び出しにおける戻り値は -1 であり,Anna が N 枚のカードを引き終えたことを表す. - 1 回目の呼び出しにおける引数 x は x=-1 を満たさなければならない.これが満たされない場合 不正解 [1] と判定される. - k 回目 (2\leqq k \leqq N+1) の呼び出しにおける引数 x は k - 1 枚目に引いたカードに対する操作を指定する.x=-1 のとき,k - 1 枚目に引いたカードを捨てることを表す.0\leqq x のとき,k - 1 枚目に引いたカードをすでに場にあるカードの列の左から x 枚目のカードのすぐ右に挿入することを表す.ただし x=0 のときはカードの列の一番左に挿入することを表す.ここで,すでに場にあるカードの枚数を l として -1 \leqq x \leqq l を満たさなければならない.これが満たされない場合,不正解 [2] と判定される. - 関数
Annaの実行の終了時に関数DrawCardの呼び出し回数が N+1 回でなかった場合,不正解 [3] と判定される.
2 つ目のファイルは Bruno.cpp という名前である.
このファイルは Bruno の戦略を実装したファイルであり,以下の関数を実装していなければならない.
また,#include プリプロセッサ指令によって Bruno.h を読み込むこと.
-
int Bruno(int N, int L, std::vector<int> C)この関数は,Anna が一連の占いの手順を終える度に 1 回,合計で Q 回呼び出される.i 回目 (1 \leqq i \leqq Q) の呼び出しは,i 回目の占いにおける Bruno の手順に相当する.Anna が山札から引いた 1 の書かれたカードの枚数を戻り値として返さなければならない. - 引数
Nは Anna が山札からカードを引いた枚数 N である. - 引数Lは場に並べられたカードの枚数 L である. - 引数Cは,長さ L の配列であり,\texttt{C}[l - 1] は場の左から l 番目 (1 \leqq l \leqq L) に並べられたカードに書かれた数を表す. - 関数Brunoの戻り値が Anna が山札から引いた 1 の書かれたカードの枚数と異なる場合,不正解 [4] と判定される.
重要な注意
- 内部での使用のために他の関数を実装したり,グローバル変数を宣言するのは自由である.ただし,提出された 2 つのプログラムは,採点プログラムとまとめてリンクされて 1 つの実行ファイルになるので,各ファイル内のすべてのグローバル変数と内部関数を無名名前空間内で宣言して,他のファイルとの干渉を避ける必要がある.採点時には,このプログラムは Anna 側,Bruno 側として 2 個のプロセスとして実行されるので,Anna 側と Bruno 側でプログラム中のグローバル変数を共有することはできない.
- あなたの提出したプログラムは,標準入力・標準出力,あるいは他のファイルといかなる方法でもやりとりしてはならない.ただし,標準エラー出力にデバッグ情報等を出力することは許される.
コンパイル・実行の方法
作成したプログラムをテストするための,採点プログラムのサンプルが,コンテストサイトからダウンロードできるアーカイブの中に含まれている.このアーカイブには,提出しなければならないファイルのサンプルも含まれている.
採点プログラムのサンプルは 1 つのファイルからなる.そのファイルは grader.cpp である.作成したプログラムをテストするには,grader.cpp,Anna.cpp,Bruno.cpp,Anna.h,Bruno.h を同じディレクトリに置き,次のようにコマンドを実行する.
g++ -std=gnu++20 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp
なお,アーカイブの中に含まれている compile.sh というファイルを代わりに実行してもよい.その場合,次のようにコマンドを実行する.
./compile.sh
コンパイルが成功すれば,grader という実行ファイルが生成される.
実際の採点プログラムは,採点プログラムのサンプルとは異なることに注意すること.採点プログラムのサンプルは単一のプロセスとして起動する.このプログラムは,標準入力から入力を読み込み,標準出力に結果を出力する.
採点プログラムのサンプルの入力
採点プログラムのサンプルは標準入力から以下の形式で入力を読み込む.
Q N
A_{1,1} A_{1,2} \cdots A_{1,N}
A_{2,1} A_{2,2} \cdots A_{2,N}
\vdots
A_{Q,1} A_{Q,2} \cdots A_{Q,N}
A_{i,j} (1 \leqq i \leqq Q,1 \leqq j \leqq N) は Anna が i 回目の占いで j 枚目に引くカードに書かれた数を表す.
採点プログラムのサンプルの出力
採点プログラムのサンプルは標準出力へ以下の情報を出力する (引用符は実際には出力されない).
- 正解の場合,すべての占いにおける Anna が場に出したカードの枚数 L の最大値が “
Accepted: 100” のように出力される. - 不正解の場合,不正解の種類が “
Wrong Answer [1]” のように出力される.
実行するプログラムが複数の不正解の条件を満たした場合, 表示される不正解の種類はそれらのうち 1 つのみである. 採点プログラムのサンプルは,不正解の条件を満たした場合,途中で実行を打ち切ることがある.
採点に関する注意
すべてのテストケースについて,実際の採点プログラムは適応的 (adaptive) ではない.これは,採点プログラムは初めから固定された山札から引くカードの列を持つということを意味する.
制約
すべての入力データは以下の条件を満たす.
- 1 \leqq Q \leqq 100.
- N = 900.
- A_{i,j} は 0 または 1 である (1 \leqq i \leqq Q,1 \leqq j \leqq N).
採点基準
この課題のテストケースの中で,1 つでも不正解 [1] ~ [4] (実装の詳細を参照) と判定されたものや, 実行時間制限超過,メモリ制限超過,実行時エラーと判定されたものがあった場合,0 点となる.
またこの課題におけるすべてのテストケースに正解した場合,この課題のすべてのテストケースで,
関数 Anna の 1 回の呼び出しについて引数 0 \leqq x で関数 DrawCard を呼び出した回数の最大値を L として,以下のように採点される.
- 500 < L のとき,3 点
- 14 < L \leqq 500 のとき,\left\lfloor 100 \times \left(\dfrac{2.5}{L - 11.5}\right)^{0.35} \right\rfloor 点
- L \leqq 14 のとき,100 点
やり取りの例
採点プログラムのサンプルが読み込む入力の例と,それに対応する関数の呼び出しの例を以下に示す.
入力例 1
2 5 0 1 0 0 1 1 1 0 1 0
関数の呼び出しの例
| 呼び出し | 戻り値 | 呼び出し | 戻り値 |
|---|---|---|---|
Anna(5) |
|||
DrawCard(-1) |
0 |
||
DrawCard(0) |
1 |
||
DrawCard(-1) |
0 |
||
DrawCard(1) |
0 |
||
DrawCard(-1) |
1 |
||
DrawCard(1) |
-1 |
||
Bruno(5, 3, [0, 1, 0]) |
2 |
||
Anna(5) |
|||
DrawCard(-1) |
1 |
||
DrawCard(0) |
1 |
||
DrawCard(1) |
0 |
||
DrawCard(2) |
1 |
||
DrawCard(-1) |
0 |
||
DrawCard(1) |
-1 |
||
Bruno(5, 4, [1, 0, 1, 0]) |
3 |
この入力例は Q (=2) 回の占いからなり,2 回の占いで Anna が山札から引くカードの枚数は N (=5) 枚である. この例では,1 回目の占いは Anna は次のような手順で占いを行う.
- Anna が山札からカードを 1 枚引く.引いたカードに書かれた数は 0 である.
- Anna は引いたカードを場に出して並べることを選択し,場に並べてあるカードの列の一番左に挿入する.場に並べられたカードの列は 0 になる.Anna は山札からカードを 1 枚引く,引いたカードに書かれた数は 1 である.
- Anna は引いたカードを捨てることを選択する.Anna は山札からカードを 1 枚引く,引いたカードに書かれた数は 0 である.
- Anna は引いたカードを場に出して並べることを選択し,場に並べてあるカードの列の左から 1 枚目のカードのすぐ右に挿入する.場に並べられたカードの列は 0,0 になる.Anna は山札からカードを 1 枚引く,引いたカードに書かれた数は 0 である.
- Anna は引いたカードを捨てることを選択する.Anna は山札からカードを 1 枚引く,引いたカードに書かれた数は 1 である.
- Anna は引いたカードを場に出して並べることを選択し,場に並べてあるカードの列の左から 1 枚目のカードのすぐ右に挿入する.場に並べられたカードの列は 0,1,0 になる.
Bruno は N の値と場に並べられたカードの列 0,1,0 をもとに,Anna が引いた 1 の書かれたカードの枚数が 2 であると答える. これは正しいため,占いは成功である.1 回目の占いで Anna が場に出したカードの枚数 L は 3 である.
2 回目の占いで Anna が場に出したカードの枚数 L は 4 である.
この入力例は制約を満たさないことに注意すること.
コンテストサイトからダウンロードできるファイルのうち,sample-01-in.txt は入力例 1 に対応する.
コンテストサイトからダウンロードできるファイルのうち,sample-02-in.txt は制約を満たす.