A - 小石を取るゲーム

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

アリの Ant さんと Bug くんは小石を取るゲームをしています。このゲームのルールは以下の通りです。

  • 最初、N 個の小石が袋に入っています。
  • Ant さん、Bug さん、Ant さん・・・の順番で交互に袋から小石を取っていきます。
  • Ant さんは１回につきちょうど A 個の小石を取ります。ただし、袋の中の小石が A 個未満である場合は、袋の中の全ての小石だけを取ります。
  • Bug くんは１回につきちょうど B 個の小石を取ります。ただし、袋の中の小石が B 個未満である場合は、袋の中の全ての小石だけを取ります。
  • 自分のターンで袋を空にすると勝ちとなります。

Ant さんはどちらがこのゲームに勝つかを計算してみることにしました。

入力

入力は以下の形式で標準入力から与えられる。

N A B
  • 1 行目には、最初に袋に入っている小石の数を表した整数 N (1 ≦ N ≦ 1000) と、Ant さんが一度に取る小石の個数を表した整数 A (1 ≦ A ≦ 1000) と、Bug さんが一度に取る小石の個数を表した整数 B (1 ≦ B ≦ 1000) が空白区切りで与えられる。

出力

勝者が Ant さんである場合は Ant、勝者が Bug くんである場合は Bug と 1 行に出力せよ。出力の末尾に改行をいれること。

入力例1

5 1 2

出力例1

Bug

以下のようにゲームが進行します。

  • Ant さんが小石を 1 つ取り出す。袋には 4 個の小石が残る。
  • Bug くんが小石を 2 つ取り出す。袋には 2 個の小石が残る。
  • Ant さんが小石を 1 つ取り出す。袋には 1 個の小石が残る。
  • 袋には 1 個しか小石が入っていないので、Bug くんが小石を 1 つ取り出す。
  • Bug くんのターンで袋が空になったので Bug くんの勝ちとなる。

入力例2

10 3 4

出力例2

Ant

２回目の Ant さんのターンでちょうど袋が空になります。

B - 特別賞

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君はプログラミングコンテストを行い、N 人の人が参加しました。賞品がないと物足りないのではないかと思った高橋君は「i 位以上の人のうち、K 番目に若い人」に特別賞を出すことにしました。参加者全員の年齢は分かっています。K の値はもう既に決めているのですが、i の値はまだ決めていません。i の値を決めるために高橋君は、K 以上 N 以下の整数 i それぞれについて誰が特別賞を取ることが出来るのかを計算してみることにしました。

入力

入力は以下の形式で標準入力から与えられる。

N K
X_1 X_2 ... X_N
  • 1 行目には、コンテストに参加した人数を表した整数 N (1 ≦ N ≦ 100,000) と、整数 K (1 ≦ K ≦ N) が空白区切りで与えられる。
  • 2 行目には、参加者の年齢の情報を表す N 個の整数が空白区切りで与えられる。このうち i 番目の整数 X_i (1 ≦ X_i ≦ N) は、順位が i 位の参加者の年齢が全参加者のうち X_i 番目に若いことを表す。ただし、p \neq q のとき X_p \neq X_q であることが保証される。

部分点

この問題には部分点が設定されている。

  • N ≦ 1000 を満たすテストケースすべてに正解した場合は 40 点が与えられる。

出力

N-K+1 行に出力せよ。そのうち i 行目には、「i+K-1 位以上の人のうち、K 番目に若い人」の順位を表す 1 つの整数を出力せよ。

入力例1

5 2
4 5 3 1 2

出力例1

2
1
3
5

以下は、出力の各行についての説明です。

  • 1 行目： 2 位以上の人のうち 2 番目に若い人は 2 位の人です。
  • 2 行目： 3 位以上の人のうち 2 番目に若い人は 1 位の人です。
  • 3 行目： 4 位以上の人のうち 2 番目に若い人は 3 位の人です。
  • 4 行目： 5 位以上の人のうち 2 番目に若い人は 5 位の人です。

入力例2

3 1
2 3 1

出力例2

1
1
3
C - 高橋王国の分割統治

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋王国は N 個の町からなり、それぞれの町には 0 から N-1 までの番号がついています。また、２つの町を繋ぐ道が N-1 本あり、どの町からどの町へもいくつかの道を使うことで辿り着けるようになっています。

高橋王国の王様である高橋君は、首都にする町を決めようとしています。高橋君は首都を決める参考にするために「バランス値」を計算してみることにしました。町 v を首都としたときの「バランス値」は、町 v を通らずに相互に通行可能である町の集合の最大の大きさです。

例えば、下の図の町 1 を首都とした場合、{町 0, 町 4} や {町 2} や {町 3} などの町の集合において、町 1 を通らずに相互に通行することが可能となっています。そのうち最も大きい集合は {町 0, 町 4} であり、その大きさは 2 であるため、町 1 を首都としたときの「バランス値」は 2 となります。

figure

入力

入力は以下の形式で標準入力から与えられる。

N
p_1
p_2
:
p_{N-1}
  • 1 行目には、町の個数を表した整数 N (1 ≦ N ≦ 100,000) が与えられる。
  • 2 行目からの N-1 行では、道の情報が与えられる。このうち i 行目では１つの整数 p_i (0 ≦ p_i ≦ i-1) が与えられる。これは、町 i と 町 p_i を繋ぐ道があることを表す。

部分点

この問題には部分点が設定されている。

  • N ≦ 1000 を満たすテストケースすべてに正解した場合は 30 点が与えられる。

出力

N 行に出力せよ。そのうち i 行目には、町 i-1 を首都としたときの「バランス値」を表す 1 つの整数を出力せよ。

入力例1

5
0
1
1
0

出力例1

3
2
4
4
4

このケースでの入力は、問題文中の図のような道の情報を表しています。

入力例2

3
0
0

出力例2

1
2
2
D - 注文の多い高橋商店

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋商店では N 種類の商品が売られています。「どの種類の商品がいくつあるか」の情報が与えられるので、「合計 M 個の商品を選ぶ方法」の数を求めて下さい。ただし、同じ種類の商品は区別しないこととします。

いや、これは少し簡単過ぎるので、ちょっとした注文も追加しよう。整数 k, x からなる Q 個の注文を用意したので、それぞれについて「k_i 種類目の商品をちょうど x_i 個選ばなければならないとき、合計 M 個の商品を選ぶ方法」の数を求めて下さい。

入力

制約に誤りがあったため、修正しました。1 ≦ Q ≦ 100,000→1 ≦ Q ≦ 500,000（22:15）

入力は以下の形式で標準入力から与えられる。

N M Q
a_1 a_2 … a_N
k_1 x_1
k_2 x_2
:
k_Q x_Q
  • 1 行目には、商品の種類数を表した整数 N (1 ≦ N ≦ 2000) と、選ぶ商品の個数を表す整数 M (1 ≦ M ≦ 2000) と、注文の個数を表した整数 Q (1 ≦ Q ≦ 500,000) が空白区切りで与えられる。
  • 2 行目では、各種類の商品の個数の情報がスペース区切りで N 個与えられる。このうち i 番目では、i 種類目の商品の個数を表す整数 a_i (1 ≦ a_i ≦ M) が与えられる。
  • 3 行目からの Q 行では、注文に関する情報が与えられる。このうち i 行目では、2 つの整数 k_i (1 ≦ k_i ≦ N), x_i (1 ≦ x_i ≦ a_{k_i}) が空白区切りで与えられる。これは、i 個目の注文が「k_i 種類目の商品をちょうど x_i 個選ばなければならないとき、合計 M 個の商品を選ぶ方法の数を出力せよ」というものであることを表している。

部分点

この問題には部分点が設定されている。

  • N ≦ 100, M ≦ 100, Q ≦ 100 を満たすテストケースすべてに正解した場合は 10 点が与えられる。
  • N ≦ 100, M ≦ 100 を満たすテストケースすべてに正解した場合はさらに 20 点が与えられる。
  • Q ≦ 1000 を満たすテストケースすべてに正解した場合はさらに 50 点が与えられる。

出力

Q 行に出力せよ。そのうち i 行目には、i 個目の注文への答えを 1,000,000,007 (10^9+7) で割った余りを出力せよ。

入力例1

3 5 2
3 2 2
1 3
1 0

出力例1

3
0

1 つ目の注文は「1 種類目の商品をちょうど 3 個選ばなければならないとき、合計 5 個の商品を選ぶ方法の数を出力せよ」というもので、そのような方法は以下の 3 通りある。

  • 1 種類目の商品を 3 個、2 種類目の商品を 2 個、3 種類目の商品を 0 個選ぶ。
  • 1 種類目の商品を 3 個、2 種類目の商品を 1 個、3 種類目の商品を 1 個選ぶ。
  • 1 種類目の商品を 3 個、2 種類目の商品を 0 個、3 種類目の商品を 2 個選ぶ。

また 2 つ目の注文では 2 種類目と 3 種類目の商品から合計 5 個の商品を選ばなければならないが、商品が足りずそのような方法は存在しないため、0 と出力する。

入力例2

4 7 5
1 2 3 4
4 0
3 2
2 1
1 1
1 0

出力例2

0
5
5
9
6