実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
ビーバーのビ太郎はビーバーランドに住むごく普通のビーバーである.ビーバーランドでは,時間の単位としてビョウを用いている.
ビーバーランドは平らな土地であり,地面の標高はどこでも 0\:\textrm{m} である.ビーバーランドには,ロケット発射基地が 1 つとビルが N 棟あり,ビルには 1 から N までの番号が付けられている.ビル i (1 \leqq i \leqq N) はビ太郎の家から X_{i}\:\textrm{m} 離れた地点に地面と垂直に建っており,高さは H_{i}\:\textrm{m} である.各ビルには,はしごがついていて,はしごを使うことで地面から屋上まで上ることができる.ビ太郎は地面を毎ビョウ 1\:\textrm{m} の速さで移動でき,はしごを使って毎ビョウ 1\:\textrm{m} の速さでビルを上ることができる.
明日,ビーバーランド初の木星探査機を載せたロケットがロケット発射基地から打ち上げられる.これを知ったビ太郎は,はしごを使ってビルを上ることで,できる限り高い所で打ち上げを見ることにした.
しかし,ビ太郎は目覚まし時計を持っていないため,明日いつ起きられるか分からない.そのため,Q 個の場合について計画を立てることにした.j 個目 (1 \leqq j \leqq Q) の計画では,ロケット打ち上げのちょうど T_{j} ビョウ前にビ太郎がビ太郎の家から移動を開始した場合に,ロケット打ち上げの瞬間に最大で標高何 m の地点に辿り着けるかを求めたい.
ビルとビ太郎の計画の情報が与えられるので,各計画についてロケット打ち上げの瞬間にビ太郎が最大で標高何 m の地点に辿り着けるかを求めるプログラムを作成せよ.
入力
入力は以下の形式で標準入力から与えられる.
N Q
X_{1} H_{1}
X_{2} H_{2}
\vdots
X_{N} H_{N}
T_{1}
T_{2}
\vdots
T_{Q}
出力
標準出力に Q 行出力せよ.j 行目 (1 \leqq j \leqq Q) には,ロケット打ち上げのちょうど T_{j} ビョウ前にビ太郎がビ太郎の家から移動を開始した場合に,ロケット打ち上げの瞬間に最大で標高何 m の地点に辿り着けるかを表す整数を出力せよ.
制約
- 1 \leqq N \leqq 300\,000.
- 1 \leqq Q \leqq 300\,000.
- 1 \leqq X_{i} \leqq 10^{9} (1 \leqq i \leqq N).
- 1 \leqq H_{i} \leqq 10^{9} (1 \leqq i \leqq N).
- 1 \leqq T_{j} \leqq 10^{9} (1 \leqq j \leqq Q).
- 入力される値はすべて整数である.
小課題
- (10 点) N \leqq 1\,000,Q \leqq 1\,000.
- (15 点) X_{i} \leqq 30 (1 \leqq i \leqq N).
- (16 点) H_{i} \leqq 30 (1 \leqq i \leqq N).
- (29 点) X_{i} < X_{i+1},H_{i} < H_{i+1} (1 \leqq i \leqq N - 1).
- (30 点) 追加の制約はない.
入力例 1
4 3 3 2 4 4 1 2 2 3 2 1 10
出力例 1
1 0 4
1 個目の計画では,ビ太郎は以下のように移動すると,ロケット打ち上げの瞬間に標高 1\:\textrm{m} の地点に辿り着くことができる.
- 1 ビョウかけて地面をビル 3 まで移動する.
- 1 ビョウかけてはしごを使ってビル 3 を 1\:\textrm{m} 上る.
ロケット打ち上げの瞬間に 1\:\textrm{m} より標高が高い位置にいることはできないので,1 行目には 1 を出力する.
2 個目の計画では,どのように移動してもビ太郎はロケット打ち上げの瞬間に標高 0\:\textrm{m} の地点にいることになる.よって,2 行目には 0 を出力する.
3 個目の計画では,ビ太郎は 4 ビョウかけてビル 2 まで移動し,はしごを使うことでビル 2 を 4 ビョウ間上ってビル 2 の屋上に行き,更にそこで 2 ビョウ待つと,ロケット打ち上げの瞬間に標高 4\:\textrm{m} の地点にいることができる.ロケット打ち上げの瞬間に 4\:\textrm{m} より標高が高い位置にいることはできないので,3 行目には 4 を出力する.
この入力例は小課題 1, 2, 3, 5 の制約を満たす.
入力例 2
3 1 2 2 2 3 2 2 6
出力例 2
3
この入力例は小課題 1, 2, 3, 5 の制約を満たす.
入力例 3
3 4 2 2 4 3 5 4 6 3 9 7
出力例 3
2 1 4 3
この入力例はすべての小課題の制約を満たす.
入力例 4
6 8 254859174 143139414 93613293 194935142 357382831 801995983 975916146 20247892 739377425 753031505 735561543 682006760 595240078 728158226 31923474 128550227 52197244 332004808 814747290 951530008
出力例 4
237857247 370775395 0 34936934 0 194935142 457364459 594147177
この入力例は小課題 1, 5 の制約を満たす.
出典
JOIG 2022/2023 春季トレーニング Contest Day1 問題1実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
JOI 研究所には部屋が N 部屋あり,各部屋には 1 から N までの番号が付けられている.これらの部屋のうち,部屋 1,部屋 2,\ldots,部屋 N - 1 にはいくつかのテレポーターが置かれている.部屋 i (1 \leqq i \leqq N - 1) には A_{i} 個のテレポーターが置かれている.部屋 i の j 番目 (1 \leqq j \leqq A_{i}) のテレポーターの行き先は部屋 P_{i,j} または部屋 Q_{i,j} のいずれかに設定することができる.ただし,P_{i,j} = Q_{i,j} となる場合もあることに注意せよ.
JOI 研究所の職員であるビ太郎とビバ子は,これらの部屋とテレポーターを使ってゲームを行う.ゲームは以下のように進行する.
- ビ太郎はゲーム開始時,部屋 1 にいる.
- ラウンドが繰り返し行われる.それぞれのラウンドは以下のように進行する.
- 現在,ビ太郎が部屋 x にいるとする.ビ太郎は部屋 x に置かれている A_{x} 個のテレポーターのうちの 1 つを選ぶ.
- ビ太郎が部屋 x の y 番目のテレポーターを選んだとする.ビバ子はそのテレポーターの行き先を部屋 P_{x,y} または部屋 Q_{x,y} に設定する.どちらを選ぶかはラウンドごとに異なっていてもよい.
- ビ太郎が部屋 x の y 番目のテレポーターを利用する.ビ太郎はビバ子によって選ばれた行き先(部屋 P_{x,y} または部屋 Q_{x,y} のいずれか)に移動する.
- ビ太郎が部屋 N に移動した場合,あるいはこのラウンドが 10^{100} ラウンド目である場合,ゲームが終了する.
このゲームにおけるビ太郎の目的は,ゲームが終了するまでに行われるラウンドの数をなるべく少なくすることである.それに対して,ビバ子の目的はゲームが終了するまでに行われるラウンドの数をなるべく多くすることである.
JOI 研究所の情報が与えられたとき,両者が最善を尽くしたときに何ラウンド目にゲームが終了するかを求めるプログラムを作成せよ.
入力
入力は以下の形式で標準入力から与えられる.
N
A_{1}
P_{1,1} Q_{1,1}
P_{1,2} Q_{1,2}
\vdots
P_{1,A_{1}} Q_{1,A_{1}}
A_{2}
P_{2,1} Q_{2,1}
P_{2,2} Q_{2,2}
\vdots
P_{2,A_{2}} Q_{2,A_{2}}
\vdots
\vdots
A_{N - 1}
P_{N - 1,1} Q_{N - 1,1}
P_{N - 1,2} Q_{N - 1,2}
\vdots
P_{N - 1,A_{N - 1}} Q_{N - 1,A_{N - 1}}
出力
標準出力に,両者が最善を尽くしたとき何ラウンド目にゲームが終了するかを 1 行で出力せよ.ただし, 10^{100} ラウンド目にゲームが終了する場合は,代わりに -1 を出力せよ.
制約
- 2 \leqq N \leqq 200\,000.
- A_{i} \geqq 1 (1 \leqq i \leqq N - 1).
- A_{1} + A_{2} + \cdots + A_{N - 1} \leqq 200\,000.
- 1 \leqq P_{i,j} \leqq N (1 \leqq i \leqq N - 1,1 \leqq j \leqq A_{i}).
- 1 \leqq Q_{i,j} \leqq N (1 \leqq i \leqq N - 1,1 \leqq j \leqq A_{i}).
- 入力される値はすべて整数である.
小課題
- (13 点) P_{i,j} = Q_{i,j} (1 \leqq i \leqq N - 1,1 \leqq j \leqq A_{i}).
- (19 点) P_{i,j} > i,Q_{i,j} > i (1 \leqq i \leqq N - 1,1 \leqq j \leqq A_{i}).
- (22 点) N \leqq 2\,000,A_{1} + A_{2} + \cdots + A_{N - 1} \leqq 2\,000.
- (30 点) A_{i} = 1 (1 \leqq i \leqq N - 1).
- (16 点) 追加の制約はない.
入力例 1
3 2 2 2 3 2 1 3 3
出力例 1
2
両者が最善を尽くしたとき,例えば以下のようにゲームは進行する.
- 最初,ビ太郎は部屋 1 にいる.
- 1 回目のラウンドは以下のように進行する.
- ビ太郎は部屋 1 の 2 番目のテレポーターを選ぶ.このテレポーターの行き先は部屋 3 または部屋 2 に設定できる.
- ビバ子は部屋 1 の 2 番目のテレポーターの行き先を部屋 2 に設定する.
- ビ太郎は部屋 1 の 2 番目のテレポーターを利用する.ビ太郎は部屋 2 に移動する.
- 2 回目のラウンドは以下のように進行する.
- ビ太郎は部屋 2 の 1 番目のテレポーターを選ぶ.このテレポーターの行き先は部屋 3 または部屋 3 に設定できる.
- ビバ子は部屋 2 の 1 番目のテレポーターの行き先を部屋 3 に設定する.
- ビ太郎は部屋 2 の 1 番目のテレポーターを利用する.ビ太郎は部屋 3 に移動する.
- ビ太郎が部屋 3 に移動したため,ゲームが終了する.
このとき,ゲームは 2 ラウンド目に終了するため,2 を出力する.
この入力例は小課題 2, 3, 5 の制約を満たす.
入力例 2
2 1 1 2
出力例 2
-1
両者が最善を尽くしたとき,ゲームは 10^{100} ラウンド目に終了するため,-1 を出力する.
この入力例は小課題 3, 4, 5 の制約を満たす.
入力例 3
5 3 4 4 2 2 1 1 1 3 3 2 1 1 5 5 2 5 5 3 3
出力例 3
2
この入力例は小課題 1, 3, 5 の制約を満たす.
出典
JOIG 2022/2023 春季トレーニング Contest Day1 問題2実行時間制限: 3 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
JOI 市議会には N 人の議員がおり,それぞれ 1 から N までの番号が付けられている.これから議会が開かれ,M 個の条例案について採決が行われる.条例案にはそれぞれ 1 から M までの番号が付けられている.A_{i,j} = 1 のとき,議員 i (1 \leqq i \leqq N) は条例案 j (1 \leqq j \leqq M) に対して賛成票を投じる予定であり,A_{i,j} = 0 のとき,議員 i は条例案 j に対して反対票を投じる予定である.
JOI 市議会は以下のように執り行われる.
- くじ引きで N 人の議員の中から議長を 1 人ランダムに決める.
- 議長は自分以外の N - 1 人の議員の中から副議長を 1 人指名する.
- M 個の条例案について採決を取る.議長と副議長以外の N - 2 人の議員が賛成票か反対票のどちらかを投じ,過半数(\left\lfloor \frac{N}{2} \right\rfloor 票以上)の賛成票を得た条例案が可決される.ここで,\lfloor x \rfloor は x を超えない最大の整数を表す.
JOI 市の K 市長は,この議会でできるだけ多くの条例が成立してほしいと考えている.K 市長は,各議員がそれぞれの条例案に対して賛成か反対かの情報を集めた.
各議員が投じる予定の票の情報が与えられたとき,それぞれの議員に対して,その議員が議長に選ばれた場合に可決される条例案の個数として考えられる最大値を求めるプログラムを作成せよ.
入力
入力は以下の形式で標準入力から与えられる.
N M
A_{1,1} A_{1,2} \cdots A_{1,M}
A_{2,1} A_{2,2} \cdots A_{2,M}
\vdots
A_{N,1} A_{N,2} \cdots A_{N,M}
出力
標準出力に N 行出力せよ.i 行目 (1 \leqq i \leqq N) には,議員 i が議長に選ばれた場合に可決される条例案の個数として考えられる最大値を出力せよ.
制約
- 3 \leqq N \leqq 300\,000.
- 1 \leqq M \leqq 20.
- 0 \leqq A_{i,j} \leqq 1 (1 \leqq i \leqq N,1 \leqq j \leqq M).
- 入力される値はすべて整数である.
小課題
- (13 点) N \leqq 300.
- (17 点) N \leqq 3\,000.
- (10 点) M \leqq 2.
- (18 点) M \leqq 10.
- (12 点) M \leqq 14.
- (22 点) M \leqq 17.
- (8 点) 追加の制約はない.
入力例 1
3 3 1 0 0 1 1 0 1 1 1
出力例 1
3 3 2
- 議員 1 が議長に選ばれた場合,議員 2 を副議長に選ぶと条例案 1, 2, 3 の 3 個が,議員 3 を副議長に選ぶと条例案 1, 2 の 2 個が可決される.よって,可決される条例案の個数の最大値は 3 個であるから,1 行目には 3 を出力する.
- 議員 2 が議長に選ばれた場合,議員 1 を副議長に選ぶと条例案 1, 2, 3 の 3 個が,議員 3 を副議長に選ぶと条例案 1 の 1 個が可決される.よって,可決される条例案の個数の最大値は 3 個であるから,2 行目には 3 を出力する.
- 議員 3 が議長に選ばれた場合,議員 1 を副議長に選ぶと条例案 1, 2 の 2 個が,議員 2 を副議長に選ぶと条例案 1 の 1 個が可決される.よって,可決される条例案の個数の最大値は 2 個であるから,3 行目には 2 を出力する.
この入力例は小課題 1, 2, 4, 5, 6, 7 の制約を満たす.
入力例 2
4 12 1 1 1 0 1 1 0 1 0 1 1 0 1 1 0 1 1 0 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0
出力例 2
5 4 6 6
この入力例は小課題 1, 2, 5, 6, 7 の制約を満たす.
入力例 3
16 4 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1
出力例 3
3 3 3 2 3 2 2 1 3 2 2 1 2 1 1 0
この入力例は小課題 1, 2, 4, 5, 6, 7 の制約を満たす.
入力例 4
4 2 1 0 0 1 1 1 1 1
出力例 4
2 2 1 1
この入力例はすべての小課題の制約を満たす.
出典
JOIG 2022/2023 春季トレーニング Contest Day1 問題3実行時間制限: 5 sec / メモリ制限: 1024 MiB
AtCoder での提出方法
C++ を使用する場合
conveyor.hを include し,すべての関数を 1 つのファイル内で実装してください.標準入出力を使用する場合
はじめに,以下の形式で入力が与えられます.
N A_0 A_1 \cdots A_{N - 2} B_0 B_1 \cdots B_{N - 2}Query
以下の形式で出力してください.
Q x_0 x_1 \cdots x_{N - 2} y_0 y_1 \cdots y_{N - 1}以下の形式で入力が与えられます.
z_0 z_1 \cdots z_{N - 1}Answer
以下の形式で出力してください.
A a_0 a_1 \cdots a_{N - 2}
0が 1 行で与えられます.文字
Fを出力してプログラムを終了してください.その他
- 出力の形式が正しくない場合や不正解の条件に当てはまった場合,与えられる入力は
-1になります.この場合,ただちにプログラムを終了してください.- 各出力の後には必ず flush をしてください.
配点 : 100 点
問題文
JOI 社の工場には N 個の台があり,0 から N - 1 までの番号が付けられている.また,工場には N - 1 本のベルトコンベアがあり,0 から N - 2 までの番号が付けられている.ベルトコンベア i (0 \leqq i \leqq N - 2) は台 A_i と台 B_i のいずれか一方から他方へ製品を運搬するが,どちらの向きに運搬するか見ることはできない.ベルトコンベアの向きを無視すると,どの 2 つの台も,いくつかのベルトコンベアを通じて繋がっている.
工場長の IOI 君はそれぞれのベルトコンベアがどちらの向きに製品を運搬するか忘れてしまったため,以下の一連の操作を何回か行うことにした.
- いくつかのベルトコンベアを選び,それらの運搬の向きを反転させる.
- いくつかの台を選び,それらの台に製品を 1 つずつ置く.
- 製品が置かれているそれぞれの台について同時に,次のことが起こる.
- その台から他の台に向かうベルトコンベアがない場合は,何も起こらない.
- その台から他の台に向かうベルトコンベアがある場合は,製品がそのうちの 1 本に乗って移動し,移動した先の台で停止する.このあと,製品が再び移動することはない.
- IOI 君はそれぞれの台に製品が 1 つ以上存在するか確認し,製品をすべて回収する.
- 1. で反転させたベルトコンベアの向きを元に戻す.
IOI 君はこの操作を 30 回以下行うことで,それぞれのベルトコンベアが最初どちらを向いていたかを特定したい.
それぞれのベルトコンベアが繋ぐ台の情報が与えられたとき,30 回以下の操作を行うことでそれぞれのベルトコンベアの向きを特定する IOI 君の戦略を実装したプログラムを作成せよ.
実装の詳細
あなたは 1 つのファイルを提出しなければならない.
あなたの提出するファイルは conveyor.cpp という名前である.そのプログラムは #include プリプロセッサ指令によって conveyor.h を読み込むこと.
conveyor.cpp は以下の関数を実装していなければならない.
-
void Solve(int N, std::vector<int> A, std::vector<int> B)この関数は各テストケースにおいて 1 回だけ呼び出される.- 引数
Nは台の個数 N である. - 引数
A,Bは長さ N - 1 の配列であり,ベルトコンベアが繋ぐ台の情報を表す.
あなたのプログラムは以下の関数を呼び出すことができる.
std::vector<int> Query(std::vector<int> x, std::vector<int> y)この関数を用いて,工場での操作を行う.- 引数
xは長さ N - 1 の配列である.0 \leqq i \leqq N - 2 について,x[i]が 1 のときベルトコンベア i の向きを反転させることを,0 のとき反転させないことを表す. - 引数
yは長さ N の配列である.0 \leqq j \leqq N - 1 について,y[j]が 1 のとき台 j に製品を置くことを,0 のとき置かないことを表す. - 戻り値を
zとすると,zは長さ N の配列である.0 \leqq j \leqq N - 1 について,z[j]が 1 のとき台 j に製品が 1 つ以上存在することを,0 のとき存在しないことを表す. - 引数
xの長さは N - 1 でなければならない.これが満たされていない場合,不正解 [1] と判定される. - 引数
xの各要素は,0 または 1 でなければならない.これが満たされていない場合,不正解 [2] と判定される. - 引数
yの長さは N でなければならない.これが満たされていない場合,不正解 [3] と判定される. - 引数
yの各要素は,0 または 1 でなければならない.これが満たされていない場合,不正解 [4] と判定される. - 関数
Queryを 30 回を超えて呼び出してはならない.30 回を超えて呼び出した場合,不正解 [5] と判定される.
- 引数
void Answer(std::vector<int> a)この関数を用いて,ベルトコンベアの最初の向きを解答する.- 引数
aは長さ N - 1 の配列である.0 \leqq i \leqq N - 2 について,a[i]が 0 のときベルトコンベア i が A_i から B_i に製品を運搬していることを,1 のとき B_i から A_i に運搬していることを表す. - 引数
aの長さは N - 1 でなければならない.これが満たされていない場合,不正解 [6] と判定される. - 引数
aの各要素は,0 または 1 でなければならない.これが満たされていない場合,不正解 [7] と判定される. - 誤った向きを回答した場合,不正解 [8] と判定される.
- 関数
Answerは丁度 1 回呼び出さなければならない.関数Answerを 2 回以上呼び出した場合,不正解 [9] と判定される.関数Solveの実行の終了時に関数Answerが 1 回も呼び出されていなかった場合,不正解 [10] と判定される.
- 引数
- 引数
重要な注意
- 内部での使用のために他の関数を実装したり,グローバル変数を宣言するのは自由である.
- あなたの提出したプログラムは,標準入力・標準出力,あるいは他のファイルといかなる方法でもやりとりしてはならない.ただし,標準エラー出力にデバッグ情報等を出力することは許される.
コンパイル・実行の方法
作成したプログラムをテストするための,採点プログラムのサンプルが,コンテストサイトからダウンロードできるアーカイブの中に含まれている.このアーカイブには,提出しなければならないファイルのサンプルも含まれている.
採点プログラムのサンプルは 1 つのファイルからなる.そのファイルは grader.cpp である.作成したプログラムをテストするには,これらのファイル grader.cpp, conveyor.cpp, conveyor.h を同じディレクトリに置き,次のようにコマンドを実行する.なお,アーカイブの中に含まれている compile.sh というファイルを代わりに実行してもよい.
g++ -std=gnu++17 -O2 -o grader grader.cpp conveyor.cpp
コンパイルが成功すれば,grader という実行ファイルが生成される.
実際の採点プログラムは,採点プログラムのサンプルとは異なることに注意すること.採点プログラムのサンプルは単一のプロセスとして起動する.このプログラムは,標準入力から入力を読み込み,標準出力に結果を出力する.
採点プログラムのサンプルの入力
採点プログラムのサンプルは標準入力から以下の形式で入力を読み込む.
N
A_0 A_1 \cdots A_{N - 2}
B_0 B_1 \cdots B_{N - 2}
C_0 C_1 \cdots C_{N - 2}
C_i (0 \leqq i \leqq N - 2) は,ベルトコンベア i が台 A_i から台 B_i に向けて製品を運搬するとき 0,台 B_i から台 A_i に運搬するとき 1 である.
採点プログラムのサンプルの出力
採点プログラムのサンプルは標準出力へ以下の情報を出力する(引用符は実際には出力されない).
- 正解の場合,関数
Queryの呼び出し回数がAccepted: 22のように出力される. - 不正解の場合,不正解の種類が
Wrong Answer [4]のように出力される.
実行するプログラムが複数の不正解の条件を満たした場合,表示される不正解の種類はそれらのうち 1 つのみである.
採点プログラムのサンプルにおいては,それぞれの製品の移動に用いられるベルトコンベアは,製品がある台から他の台に向かうベルトコンベアのうち 1 本が,実行ごとに結果が変わらない疑似乱数を用いて一様に無作為に選ばれる.シードの値を変更したい場合は,
./grader 2023
のように 1 個目の引数に整数値を与えて実行せよ.
採点に関する注意
いくつかのテストケースについて,実際の採点プログラムは適応的 (adaptive) である.これは,採点プログラムは初めから固定された答えを持たず,それ以前の Query 関数の呼び出しに応じて採点プログラムが応答するということである.ただし,すべての応答に矛盾しないような答えが少なくとも 1 つ存在するということが保証される.
制約
すべての入力データは以下の条件を満たす.
- 0 \leqq A_i \leqq N - 1 (0 \leqq i \leqq N - 2).
- 0 \leqq B_i \leqq N - 1 (0 \leqq i \leqq N - 2).
- ベルトコンベアの向きを無視すると,どの 2 つの台も,いくつかのベルトコンベアを通じて繋がっている.
小課題
- (5 点) N = 2.
- (20 点) N = 30.
- (15 点) N = 100\,000,A_i = i (0 \leqq i \leqq N - 2),B_i = i + 1 (0 \leqq i \leqq N - 2).
- (60 点) N = 100\,000.
やりとりの例
採点プログラムのサンプルが読み込む入力の例と,それに対応する関数の呼び出しの例を以下に示す.
入力例 1
3 0 2 2 1 1 0
関数の呼び出しの例
| 呼び出し(採点プログラム) | 呼び出し(提出プログラム) | 戻り値 |
|---|---|---|
Solve(3, [0, 2], [2, 1]) |
||
Query([0, 0], [0, 0, 1]) |
[1, 0, 0] |
|
Query([1, 0], [1, 0, 1]) |
[0, 1, 1] |
|
Query([1, 1], [0, 0, 1]) |
[0, 0, 1] |
|
Query([0, 1], [1, 1, 1]) |
[1, 0, 1] |
|
Answer([1, 0]) |
1 回目の Query の呼び出しの戻り値は,[1, 0, 0] の他に [0, 1, 0] となる可能性もある.
2 回目の Query の呼び出しにおいて,台 0 に置かれた製品はベルトコンベア 0 を通って台 2 に移動して停止する.この製品が続けてベルトコンベア 1 を通って台 1 に移動することはないことに注意すること.
この入力例はどの小課題の制約も満たさないことに注意すること.
コンテストサイトからダウンロードできるファイルのうち,sample-02.txt は小課題 1 の制約を満たし,sample-03.txt は小課題 2 の制約を満たす.
出典
JOIG 2022/2023 春季トレーニング Contest Day1 問題4実行時間制限: 1 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
JOI 高校の生徒である葵は,1 から N までの番号が付けられた N 台のスマートフォンをレンタルしており,それぞれのスマートフォンには使用日数制限が設けられている.スマートフォン i (1 \leqq i \leqq N) は,明日を 1 日目としたとき,A_{i} 日目から B_{i} 日目までの B_{i} - A_{i} + 1 日のうち 1 日単位で最大 C_{i} 日まで選んで使用することができる.このとき,使用する日は連続していなくても構わない.
今レンタルしているスマートフォンはすべて K + 1 日目に返却しなくてはならない.そこで,葵はスマートフォンを最大限使用するために明日から K 日分の使用計画を立てようと思ったが,難しかったため,あなたに頼むことにした.
葵がレンタルしているスマートフォンの台数 N,使用計画を立てる日数 K,それぞれのスマートフォンの使用日数制限が与えられる.葵が K 日の間で 1 台以上のスマートフォンを使用することのできる最大日数を求めるプログラムを作成せよ.
入力
入力は以下の形式で標準入力から与えられる.
N K
A_{1} B_{1} C_{1}
A_{2} B_{2} C_{2}
\vdots
A_{N} B_{N} C_{N}
出力
標準出力に,葵が 1 台以上のスマートフォンを使用することのできる最大日数を 1 行で出力せよ.
制約
- 1 \leqq N \leqq 300\,000.
- 1 \leqq K \leqq 10^{15}.
- 1 \leqq A_{i} \leqq B_{i} \leqq K (1 \leqq i \leqq N).
- 1 \leqq C_{i} \leqq B_{i} - A_{i} + 1 (1 \leqq i \leqq N).
- 入力される値はすべて整数である.
小課題
- (5 点) N \leqq 1\,000,K \leqq 1\,000,B_{i} < A_{j} または B_{j} < A_{i} (1 \leqq i < j \leqq N).
- (10 点) C_{i} = B_{i} - A_{i} + 1 (1 \leqq i \leqq N).
- (10 点) N \leqq 1\,000,K \leqq 1\,000,A_{i} = 1 (1 \leqq i \leqq N).
- (30 点) N \leqq 1\,000,K \leqq 1\,000.
- (15 点) K \leqq 300\,000.
- (30 点) 追加の制約はない.
入力例 1
5 15 1 6 3 2 3 1 2 2 1 3 7 3 11 13 2
出力例 1
9
例えば次のようにすると,葵は 9 日 1 台以上のスマートフォンを使用することができる.この表において,〇,\times はそれぞれ該当のスマートフォンを使う日,使わない日を表す.
| 日数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| スマートフォン 1 | 〇 | \times | \times | 〇 | 〇 | \times | |||||||||
| スマートフォン 2 | \times | 〇 | |||||||||||||
| スマートフォン 3 | 〇 | ||||||||||||||
| スマートフォン 4 | \times | \times | 〇 | 〇 | 〇 | ||||||||||
| スマートフォン 5 | \times | 〇 | 〇 |
10 日以上 1 台以上のスマートフォンを使用することはできないので,9 を出力する.
この入力例は小課題 4, 5, 6 の制約を満たす.
入力例 2
4 8 1 2 2 1 3 3 1 3 3 1 5 5
出力例 2
5
例えば次のようにすると,葵は 5 日 1 台以上のスマートフォンを使用することができる.この表において,〇,\times はそれぞれ該当のスマートフォンを使う日,使わない日を表す.
| 日数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| スマートフォン 1 | 〇 | 〇 | ||||||
| スマートフォン 2 | 〇 | 〇 | 〇 | |||||
| スマートフォン 3 | \times | \times | \times | |||||
| スマートフォン 4 | 〇 | 〇 | 〇 | 〇 | 〇 |
6 日以上 1 台以上のスマートフォンを使用することはできないので,5 を出力する.
この入力例は小課題 2, 3, 4, 5, 6 の制約を満たす.
入力例 3
3 6 1 1 1 2 3 2 4 6 2
出力例 3
5
この入力例は小課題 1, 4, 5, 6 の制約を満たす.
入力例 4
3 7 4 6 3 4 6 1 4 6 2
出力例 4
3
この入力例は小課題 4, 5, 6 の制約を満たす.
入力例 5
15 4768558 3025257 4432949 1319859 3066618 4509446 1254699 3417684 3665318 139375 914550 2131942 1143715 729276 928089 139749 4634629 4763389 30565 3554868 4214881 168515 3206967 4721972 519481 4595561 4755647 139316 1423715 2437121 87927 2355901 3933477 584228 3076814 3150827 40891 3280648 3632366 177447 2224458 2296486 47900 2693763 4283443 832253
出力例 5
3826780
この入力例は小課題 6 の制約を満たす.
出典
JOIG 2022/2023 春季トレーニング Contest Day2 問題1実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
N 個のライトが横一列に並んでおり,左から順に 1 から N までの番号が付けられている.それぞれのライトの色は赤,緑,青のいずれかである.ライトの色は文字列 S によって表され,ライト i (1 \leqq i \leqq N) の色は,S の i 文字目が ‘R’ のとき赤,‘G’ のとき緑,‘B’ のとき青である.
最初すべてのライトは点灯している.葵は,「1 個以上 K 個以下の連続するライトを選んですべて消灯させる」という操作を何度でも行うことができる.このとき,既に消灯しているライトを再び選んでも構わない.
葵は,遠くからこのライトの列を見たときにきれいな白色に見えるようにしたい.そのためには,点灯しているライトを左から見たときの色の並びが “\texttt{RGBRGB}\ldots\texttt{RGB}” のように “RGB”(赤緑青)の繰り返しになっている必要がある.ただし,1 つも点灯しているライトが存在しない場合も条件を満たすものとする. “GBRGBR” や “RGBRG” などの色の並びは条件を満たさないことに注意せよ.
ライトと操作に関する情報が与えられたとき,葵が最小で何回操作を行う必要があるかを求めるプログラムを作成せよ.
入力
入力は以下の形式で標準入力から与えられる.
N K S
出力
標準出力に,葵が最小で何回操作を行う必要があるかを 1 行で出力せよ.
制約
- 1 \leqq K \leqq N \leqq 200\,000.
- S は ‘
R’,‘G’,‘B’ からなる長さ N の文字列である. - N, K は整数である.
小課題
- (10 点) N \leqq 16,K = 1.
- (26 点) K = 1.
- (26 点) K \leqq 100.
- (38 点) 追加の制約はない.
入力例 1
8 1 BRGBRRGB
出力例 1
2
例えば以下のように 2 回の操作を行ったとき,点灯しているライトの色が “RGB” の繰り返しになる.消灯しているライトを ‘-’ で表す.
- ライト 1 を選び,消灯させる.それぞれのライトの状態は文字列 “
-RGBRRGB” で表される. - ライト 5 を選び,消灯させる.それぞれのライトの状態は文字列 “
-RGB-RGB” で表される.
1 回以下の操作で点灯しているライトの色を “RGB” の繰り返しにすることはできないため,2 を出力する.この入力例はすべての小課題の制約を満たす.
入力例 2
8 2 RGGGBBGR
出力例 2
3
例えば以下のように 3 回の操作を行ったとき,点灯しているライトの色が “RGB” の繰り返しになる.消灯しているライトを ‘-’ で表す.
- ライト 2, 3 を選び,消灯させる.それぞれのライトの状態は文字列 “
R--GBBGR” で表される. - ライト 6, 7 を選び,消灯させる.それぞれのライトの状態は文字列 “
R--GB--R” で表される. - ライト 8 を選び,消灯させる.それぞれのライトの状態は文字列 “
R--GB---” で表される.
2 回以下の操作で点灯しているライトの色を “RGB” の繰り返しにすることはできないため,3 を出力する.この入力例は小課題 3, 4 の制約を満たす.
入力例 3
11 8 RGBBRGBBRGB
出力例 3
1
この入力例は小課題 3, 4 の制約を満たす.
入力例 4
10 3 RRRRRRRRRR
出力例 4
4
この入力例は小課題 3, 4 の制約を満たす.
入力例 5
6 1 RGBRGB
出力例 5
0
この入力例はすべての小課題の制約を満たす.
出典
JOIG 2022/2023 春季トレーニング Contest Day2 問題2実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
JOI 市には 1 本の十分に長い道路がある.この道路は数直線とみなすことができ,各地点は 1 個の実数による座標で表される.また,JOI 市にはこの道路に沿って N 箇所の観光地があり,座標の小さい順に 1 から N までの番号が付けられている.観光地 i (1 \leqq i \leqq N) は座標 X_i に位置する.
ビ太郎は,これから JOI 市のすべての観光地を訪ねようとしている.貪欲をスローガンとして生きているビ太郎は,すべての観光地を訪ねるまで以下の行動を繰り返す.
- 現在のビ太郎の座標を x としたとき,まだ訪ねていない観光地のうち現在のビ太郎からの距離 |x - X_i| を最小とする観光地 i がある場所まで移動し,その観光地を訪ねる.ただし,そのような観光地が複数ある場合は座標が小さいほうを選ぶ.ここで,|t| は t の絶対値を表す.
しかしビ太郎は,長年の経験から,このような方法で移動を繰り返すと予想外に移動距離が長くなってしまうことがあることを知っていた.移動距離はビ太郎がスタートする座標によって変化することがあるので,Q 個の座標 S_1, S_2, \ldots, S_Q について,その座標からビ太郎がスタートした場合の移動距離を調べることにした.
ビ太郎を助けるために,JOI 市の観光地の情報とビ太郎がスタートする座標の候補の情報が与えられたとき,それぞれの候補について,その座標からビ太郎がスタートした場合の移動距離を求めるプログラムを作成せよ.
入力
入力は以下の形式で標準入力から与えられる.
N X_1 X_2 \cdots X_N Q S_1 S_2 \vdots S_Q
出力
標準出力に Q 行出力せよ.j 行目 (1 \leqq j \leqq Q) には,座標 S_j からビ太郎がスタートした場合,すべての観光地を訪ねるまでにビ太郎が移動する距離を出力せよ.
制約
- 1 \leqq N \leqq 200\,000.
- 1 \leqq Q \leqq 200\,000.
- 0 \leqq X_i \leqq 10^9 (1 \leqq i \leqq N).
- X_i < X_{i+1} (1 \leqq i \leqq N - 1).
- 0 \leqq S_j \leqq 10^9 (1 \leqq j \leqq Q).
- 入力される値はすべて整数である.
小課題
- (8 点) Q = 1,N \leqq 2\,000.
- (16 点) Q = 1.
- (32 点) X_{i+1} - X_i \leqq 100 (1 \leqq i \leqq N - 1).
- (44 点) 追加の制約はない.
入力例 1
5 0 5 6 7 9 1 7
出力例 1
15
ビ太郎が座標 7 からスタートすると,ビ太郎は以下の手順で観光地を訪ねる.
- まだ訪ねていない観光地は観光地 1, 2, 3, 4, 5 であり,ビ太郎からの距離はそれぞれ 7, 2, 1, 0, 2 である.このうちビ太郎からの距離が最小の観光地は観光地 4 であるから,ビ太郎は座標 7 に留まり,観光地 4 を訪ねる.
- まだ訪ねていない観光地は観光地 1, 2, 3, 5 であり,ビ太郎からの距離はそれぞれ 7, 2, 1, 2 である.このうちビ太郎からの距離が最小の観光地は観光地 3 であるから,ビ太郎は座標 7 から座標 6 へ移動し,観光地 3 を訪ねる.
- まだ訪ねていない観光地は観光地 1, 2, 5 であり,ビ太郎からの距離はそれぞれ 6, 1, 3 である.このうちビ太郎からの距離が最小の観光地は観光地 2 であるから,ビ太郎は座標 6 から座標 5 へ移動し,観光地 2 を訪ねる.
- まだ訪ねていない観光地は観光地 1, 5 であり,ビ太郎からの距離はそれぞれ 5, 4 である.このうちビ太郎からの距離が最小の観光地は観光地 5 であるから,ビ太郎は座標 5 から座標 9 へ移動し,観光地 5 を訪ねる.
- まだ訪ねていない観光地は観光地 1 である.このうちビ太郎からの距離が最小の観光地は観光地 1 であるから,ビ太郎は座標 9 から座標 0 へ移動し,観光地 1 を訪ねる.
ビ太郎が移動した距離は合計で 15 であるから,15 を出力する.
この入力例はすべての小課題の制約を満たす.
入力例 2
10 1 2 3 4 5 6 7 8 9 10 10 1 2 3 4 5 6 7 8 9 10
出力例 2
9 10 11 12 13 14 15 16 17 9
この入力例は小課題 3, 4 の制約を満たす.
出典
JOIG 2022/2023 春季トレーニング Contest Day2 問題3実行時間制限: 2 sec / メモリ制限: 1024 MiB
AtCoder での提出方法
Anna.h,Bruno.hを include し,すべての関数を 1 つのファイル内で実装してください.グローバル変数を両者の間で共有しないでください.このジャッジは C++ 以外に対応していません.
配点 : 100 点
問題文
JOI 放送局が開催する人気バラエティ番組 JOICup は,いよいよ最終ラウンドを迎えることになった.最終ラウンドでは「メッセンジャーゲーム」が行われ,予選を勝ち抜いた Anna と Bruno の 2 人からなるチームのみが出場する.
メッセンジャーゲームは,8 行 8 列のマス目を介して情報を伝えるゲームである.マス目の各行には 0 から 7 までの行番号が,各列には 0 から 7 までの列番号が付けられている.
メッセンジャーゲームでは,Anna と Bruno が別の部屋に隔離された状態で Q 回のチャレンジが行われる.i 回目 (1 \leqq i \leqq Q) のチャレンジは次のように進行する.
- Anna は司会のビ太郎から,3 つの整数 X_i, Y_i, N_i (0 \leqq X_i \leqq 7,0 \leqq Y_i \leqq 7,1 \leqq N_i \leqq 43) および
AとBからなる N_i 文字の文字列 S_i が書かれたカードと,すべてのマスが白で塗られた 8 行 8 列のマス目を受け取る. - Anna は,行番号が X_i でなく列番号が Y_i でない 49 個のマスについて,各マスを青か赤で塗る.
- Anna はマス目を司会のビ太郎に渡す.
- ビ太郎は,行番号が X_i または列番号が Y_i である 15 個のマスについて,各マスを青か赤で塗る.この操作は Anna や Bruno から見えない場所で行われる.
- Bruno は司会のビ太郎から,整数 N_i のみが書かれたカードとマス目を受け取る.
- Bruno はある文字列を紙に書く.書いた文字列が S_i と一致していれば,Anna と Bruno の勝利となる.
チャレンジの進行については,以下の図も参照せよ.
Anna と Bruno が「メッセンジャーゲーム」で勝利するための戦略を実装せよ.なお,この課題の採点方法については,採点基準の項を参照すること.
実装の詳細
あなたは 2 つのファイルを提出しなければならない.
1 つ目のファイルは Anna.cpp という名前である.このファイルは Anna の戦略を実装したファイルであり,以下の関数を実装していなければならない.また,#include プリプロセッサ指令によって Anna.h を読み込むこと.
-
void Anna(int X, int Y, int N, std::string S)この関数は合計 Q 回呼び出される.i 回目 (1 \leqq i \leqq Q) の呼び出しは,ゲームにおける i 回目のチャレンジの手順 1.,手順 2.,手順 3. に相当する.- 引数
Xは,i 回目のチャレンジの手順 1. で Anna が受け取るカードに書かれた整数 X_i である. - 引数
Yは,i 回目のチャレンジの手順 1. で Anna が受け取るカードに書かれた整数 Y_i である. - 引数
Nは,i 回目のチャレンジの手順 1. で Anna が受け取るカードに書かれた整数 N_i である. - 引数
Sは,i 回目のチャレンジの手順 1. で Anna が受け取るカードに書かれた文字列 S_i である.
関数
Annaの 1 回の呼び出しについて,以下の関数を,行番号が X_i でなく列番号が Y_i でない 49 個のマスそれぞれについて 1 回ずつ,合計 49 回呼び出さなければならない.void Paint(int a, int b, int c)- 引数
a, bは,行番号が a で列番号が b のマスに色を塗ることを表す.ここで,0 \leqq a \leqq 7,0 \leqq b \leqq 7,a \neq X,b \neq Y を満たさなければならない.これが満たされない場合,不正解 [1] と判定される. - 引数
cは,c = 0 のとき青,c = 1 のとき赤で塗ることを表す.ここで,0 \leqq c \leqq 1 を満たさなければならない.これが満たされない場合,不正解 [2] と判定される. - 関数
Paintを同じ (a, b) で 2 回呼び出した場合,不正解 [3] と判定される. - 関数
Annaの実行の終了時に関数Paintの呼び出し回数が 49 回でなかった場合,不正解 [4] と判定される.
- 引数
- 引数
2 つ目のファイルは Bruno.cpp という名前である.このファイルは Bruno の戦略を実装したファイルであり,以下の関数を実装していなければならない.また,#include プリプロセッサ指令によって Bruno.h を読み込むこと.
std::string Bruno(int N, std::vector<std::vector<int>> T)この関数は Anna がマス目を塗り終わるたびに 1 回,合計で Q 回呼び出される.i 回目 (1 \leqq i \leqq Q) の呼び出しは,ゲームにおける i 回目のチャレンジの手順 5.,手順 6. に相当する.- 引数
Nは,i 回目のチャレンジの手順 5. で Bruno が受け取るカードに書かれた整数 N_i である. - 引数
Tは,i 回目のチャレンジの手順 5. で Bruno が受け取るマス目の各マスの色を表す 8 \times 8 の 2 次元配列である.行番号が a (0 \leqq a \leqq 7) で列番号が b (0 \leqq b \leqq 7) のマスの色は,T[a][b] = 0であれば青,T[a][b] = 1であれば赤である. - 戻り値は,Bruno が紙に書く文字列である.
- 戻り値が 44 文字以上の文字列である場合,不正解 [5] と判定される.
- 戻り値に
AとB以外の文字が含まれている場合,不正解 [6] と判定される.
- 引数
重要な注意
- 内部での使用のために他の関数を実装したり,グローバル変数を宣言するのは自由である.ただし,提出された 2 つのプログラムは,採点プログラムとまとめてリンクされて 1 つの実行ファイルになるので,各ファイル内のすべてのグローバル変数と内部関数を無名名前空間内で宣言して,他のファイルとの干渉を避ける必要がある.採点時には,このプログラムは Anna 側,Bruno 側として 2 個のプロセスとして実行されるので,Anna 側と Bruno 側でプログラム中のグローバル変数を共有することはできない.
- あなたの提出したプログラムは,標準入力・標準出力,あるいは他のファイルといかなる方法でもやりとりしてはならない.ただし,標準エラー出力にデバッグ情報等を出力することは許される.
コンパイル・実行の方法
作成したプログラムをテストするための,採点プログラムのサンプルが,コンテストサイトからダウンロードできるアーカイブの中に含まれている.このアーカイブには,提出しなければならないファイルのサンプルも含まれている.
採点プログラムのサンプルは 1 つのファイルからなる.そのファイルは grader.cpp である.作成したプログラムをテストするには,grader.cpp,Anna.cpp,Bruno.cpp,Anna.h,Bruno.h を同じディレクトリに置き,次のようにコマンドを実行する.なお,アーカイブの中に含まれている compile.sh というファイルを代わりに実行してもよい.
g++ -std=gnu++17 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp
コンパイルが成功すれば,grader という実行ファイルが生成される.
実際の採点プログラムは,採点プログラムのサンプルとは異なることに注意すること.特に,ビ太郎が各マスを塗る色が無作為に選ばれるとは限らない.採点プログラムのサンプルは単一のプロセスとして起動する.このプログラムは,標準入力から入力を読み込み,標準出力に結果を出力する.
採点プログラムのサンプルの入力
採点プログラムのサンプルは標準入力から以下の形式で入力を読み込む.
Q X_1 Y_1 N_1 S_1 X_2 Y_2 N_2 S_2 \vdots X_Q Y_Q N_Q S_Q
採点プログラムのサンプルの出力
採点プログラムのサンプルは標準出力へ以下の情報を出力する(引用符は実際には出力されない).
- 正解の場合,L^{\ast} の値が
Accepted: 28のように出力される.L^{\ast} の値については採点基準の項を参照せよ. - 不正解の場合,不正解の種類が
Wrong Answer [1]のように出力される.
実行するプログラムが複数の不正解の条件を満たした場合,表示される不正解の種類はそれらのうち 1 つのみである.
採点プログラムのサンプルにおいては,それぞれのチャレンジでビ太郎が各マスを塗る色が,実行ごとに結果が変わらない疑似乱数を用いて無作為に選ばれる.シードの値を変更したい場合は,
./grader 2023
のように 1 個目の引数に整数値を与えて実行せよ.
制約
- 1 \leqq Q \leqq 20\,000.
- 0 \leqq X_i \leqq 7 (1 \leqq i \leqq Q).
- 0 \leqq Y_i \leqq 7 (1 \leqq i \leqq Q).
- 1 \leqq N_i \leqq 43 (1 \leqq i \leqq Q).
- Q, X_i, Y_i, N_i は整数である.
- S_i (1 \leqq i \leqq Q) は
AとBからなる N_i 文字の文字列である.
採点基準
この課題のテストケースの中で,1 つでも不正解 [1] 〜 [6](実装の詳細を参照)と判定されたものや,実行時エラー(実行時間制限超過,メモリ制限違反,異常終了など)と判定されたものがあった場合,他のテストケースでどのチャレンジに勝利したかにかかわらず無条件で 0 点となる.
そうでない場合,この課題のすべてのテストケースに対する以下の値の最小値を L^{\ast} とするとき,下表のように得点が与えられる.
- N_i \leqq L を満たすすべてのチャレンジについて勝利したような最大の整数 L.ただし,テストケース内のすべてのチャレンジに勝利した場合は L = 43 とする.
| L^{\ast} | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 得点 | 0 | 10 | 15 | 19 | 23 | 25 | 27 | 29 | 31 | 33 | 35 | 37 | 39 | 41 | 43 | 45 | 47 | 49 | 51 | 53 | 55 | 57 | 59 | 61 | 63 | 65 | 67 | 69 | 70 | 72 | 73 | 75 | 76 | 78 | 79 | 81 | 82 | 84 | 86 | 88 | 90 | 93 | 96 | 100 |
やりとりの例
採点プログラムのサンプルが読み込む入力の例と,それに対応する関数の呼び出しの例を以下に示す.ただし,関数 Bruno の呼び出しにおける引数 T は省略されている.
入力例 1
2 0 0 1 B 5 7 8 AAAABBBB
関数の呼び出しの例
| Anna の呼び出し | Bruno の呼び出し | Bruno の戻り値 |
|---|---|---|
Anna(0, 0, 1, "B") |
||
Paint(1, 1, 0) |
||
Paint(1, 2, 1) |
||
| \ldots | ||
Paint(7, 7, 1) |
||
Bruno(1, ...) |
||
"B" |
||
Anna(5, 7, 8, "AAAABBBB") |
||
Paint(0, 0, 1) |
||
Paint(0, 1, 1) |
||
| \ldots | ||
Paint(7, 6, 0) |
||
Bruno(8, ...) |
||
"AAAABBBB" |
この入力例は Q (= 2) 回のチャレンジからなる.
- 1 回目のチャレンジでは X_1 = 0,Y_1 = 0,N_1 = 1,S_1 = {}
"B"であるため,Anna は行番号が 0 でなく列番号が 0 でない 49 個のマスに色を塗らなければならない. - 2 回目のチャレンジでは X_2 = 5,Y_2 = 7,N_2 = 8,S_2 = {}
"AAAABBBB"であるため,Anna は行番号が 5 でなく列番号が 7 でない 49 個のマスに色を塗らなければならない.
たとえば,1 回目のチャレンジで Paint(0, 2, 1) を呼び出した場合,行番号が 0 のマスを指定しているため不正解 [1] となることに注意せよ.
また,採点プログラムのサンプルが読み込む入力のもう 1 つの例を以下に示す.
入力例 2
30 3 1 1 A 1 4 1 A 6 6 2 AA 1 1 2 BB 3 1 3 BAB 7 4 3 AAB 6 4 4 BAAB 6 7 4 BABA 3 3 5 BABBA 1 5 5 ABBBA 4 3 6 ABBBBB 2 1 6 ABAAAA 6 0 7 AAABABA 6 6 7 BBABBAA 0 4 8 AABAABAB 2 1 8 AABBBBBA 2 0 9 BABABBAAA 1 5 9 BBAAABABB 6 7 10 BAAABAAABB 1 7 10 BBBBBBBABA 2 6 12 AABAABABABAB 3 4 15 BBAABAAAABABAAB 5 6 18 BAAAABBABABBBABBAB 7 0 22 BABBAABAAABBABBBBBBABA 2 0 26 AAAABBABBAAAAABABABBAABAAA 0 7 30 AAABBBAAABAABBBBAABBAAABBBABBB 2 7 34 BABAABBAABABBABAABBABBABAABBBBABBB 2 5 38 BBBBAABAABAABABABBBBBAAABBABAAABAAABBB 5 2 41 AABABBAAABBABAAAABBABABBAAAAAABBABBABBABA 1 0 43 AABBABBBBABABBBABBBBAAAAAABABAAABBBAABBAAAB