0071 - チーム

問題

あるクラスには N ⼈の⽣徒がおり，0 から N - 1 までの番号がついている．このクラスでは，毎⽇先⽣が⽣徒にいくつかのプロジェクトを課している．それぞれのプロジェクトは何⼈かの⽣徒によるチームによって1⽇で完成させる．これらのプロジェクトは難しさがさまざまであり，先⽣は，それぞれのプロジェクトを⾏うためにはチームにちょうど何⼈必要なのかを把握している．

⽣徒によって所属するチームの⼈数に好みがあるかもしれない．正確に⾔うと，i 番⽬の⽣徒は A[i] ⼈以上 B[i] ⼈以下の⽣徒が所属するチームにのみ所属することができる．また，1⽇の中では，それぞれの⽣徒は最⼤でも1つのチームにしか所属することはできない．ただし，どのチームにも所属しない⽣徒がいるような⽇があってもかまわない．それぞれのチームは1つのプロジェクトのみを⾏うことができる．

先⽣はすでに今後 Q ⽇間に⾏うプロジェクトを決定している．この期間のうちそれぞれの⽇について，その⽇のすべてのプロジェクトに対し，1つのチームがそのプロジェクトを⾏うように⽣徒をチームに割り当てることが可能かどうかを決定せよ．

例 (Example)

この例では，N = 4 ⼈の⽣徒がおり，Q = 2 ⽇間のプロジェクトが決定している．それぞれの⽣徒が所属できるチームの構成⼈数の範囲は以下の表の通りである．

1 ⽇⽬は 2 つのプロジェクトが課される．それぞれのプロジェクトに必要なチームの⼈数は K[0] = 1 ⼈および K[1] = 3 ⼈である．これら 2 つのチームは，⽣徒 0 を 1 ⼈のチームに割り当て，残りの 3 ⼈を 3 ⼈のチームに割り当てることで構成できる．

2 ⽇⽬も 2 つのプロジェクトが課される．それぞれのプロジェクトに必要なチームの⼈数は K[0] = 1 ⼈および K[1] = 1 ⼈である．この場合，⽣徒を 2 つのチームに割り当てることは不可能である．なぜならば，構成⼈員が 1 ⼈のチームに所属することができる⽣徒が 1 ⼈しかいないからである．

課題 (Task)

あなたは⽣徒に関する情報 N， A， B，および Q ⽇間のプロジェクトの情報に対応する Q 個の質問が与えられる．それぞれの質問は，その⽇のプロジェクトの個数 M と，その⽇に必要なチームそれぞれの構成⼈数を表す⾧さ M の数列 K からなる．それぞれの質問に対し，あなたのプログラムはその⽇すべてのプロジェクトを⾏うことができるようにチームを構成できるかどうかを返さなければならない．

あなたは以下に⽰す関数 init および can を実装する必要がある．

• init(N, A, B) — 採点プログラムは最初に関数 init を 1 回だけ呼び出す．
• N: ⽣徒の⼈数である．
• A: ⾧さNの配列であり，A[i]は⽣徒 i の所属できるチームの構成⼈数の最⼩値である．
• B: ⾧さNの配列であり，B[i]は⽣徒 i の所属できるチームの構成⼈数の最⼤値である．
• この関数は戻り値をもたない．
• i = 0,...,N - 1 を満たすそれぞれの i に対し， A[i] ≤ B[i] ≤ Nを満たす．
• can(M, K) — initを1回だけ呼び出した後，採点プログラムはこの関数を Q 回呼び出す．これらの呼び出しには，それぞれの⽇に対応する質問が 1 回ずつ含まれる．
• M: その⽇のプロジェクトの個数である．
• K: その⽇のそれぞれのプロジェクトに対して必要とされているチームの構成⼈数を表す⾧さMの配列である．
• この関数は，もしその⽇のチームに⽣徒を割り当てることが可能ならば 1 を，そうでないならば 0 を返さなければならない．
• 1 ≤ M ≤ N ，および i = 0,...,M - 1 を満たすそれぞれの i に対し，1 ≤ K[i] ≤ N を満たす．また，K[i]の総和が N を超えるかもしれないことに注意せよ．

小課題 (Subtasks)

ここでは，すべてのcan(M, K)の呼び出しにおけるMの総和を S とする．

採点プログラムのサンプル

採点プログラムのサンプルは，以下のフォーマットで⼊⼒を読み込む：

• 1⾏⽬： N
• 2,..., N + 1 ⾏⽬： A[i] B[i]
• N + 2 ⾏⽬： Q
• N + 3,..., N + Q + 2 ⾏⽬： M K[0] K[1] ... K[M - 1]

それぞれの質問において，採点プログラムのサンプルはcanによる戻り値を出⼒する．

実行時に必要なファイル

• teams.h

ヘッダファイル

• grader.cpp grader.c

採点用プログラムのサンプル

• teams.cpp teams.c

実装ファイル(解答はここに実装)

• sample.in sample.out

サンプル入出力ファイル

コンパイルの方法

C++

g++ grader.cpp teams.cpp

C

gcc grader.c teams.c