A - ババ抜き

Time Limit: 20 sec / Memory Limit: 256 MB

特殊なトランプを使ったババ抜きを N 人で行う。
カードに記載される数字は1 ～ 8 までで、ジョーカーはJである。
N 人にカードが与えられるので、ババ抜きが終了するまでに、プレイヤーがカードを引いた総数を出力せよ。
ただしババ抜きが終了しない場合は-1と出力せよ。
このババ抜きのルールを以下に記載する。
各プレイヤーは、次のプレイヤーの手札から一番左のカードを引き、自分の手札の一番右に加える。
つまり、プレイヤー 1 はプレイヤー 2 からカードを引き、プレイヤー N はプレイヤー 1 からカードを引く。
その過程で、引いたカードと同じ数字のカードが自分の手札にあった場合、それらを両方捨てる。
もし、プレイヤーの手札がなくなったら、そのプレイヤーは上がりとし、以後、そのプレイヤーはいないものとして扱う。
例えば、プレイヤー 2の手札がなくなった場合、プレイヤー 1 は、プレイヤー 3 からカードを引く。
ジョーカー以外は偶数枚存在するが、ジョーカーだけはあるプレイヤーに 1 枚だけ配られる。
各プレイヤーの手札から、ジョーカー以外のすべてのカードがなくなったらゲーム終了である。

入力形式

入力の 1 行目にはテストケース数 T を示す。以降、T 個のテストケースが続く。
各テストケースの 1 行目は入力値の個数 N を示す。
次の行から N 行にわたって、入力値 c_1、c_2、...c_N が表示される。
c_i は、プレイヤー i の初期手札を意味し、文字列である。
たとえば、2746J18 は、左から順番に、2746J18を所持していることを表す。

出力形式

各テストケースに対して、ババ抜きが終了するまでにプレイヤーがカードを引いた総数を出力する。
ただしババ抜きが終了しない場合は-1と出力せよ。

入力制限

1≦T≦100
3≦N≦5
c_i は1～8に J を加えた文字列

サンプル入力

制約外のサンプル入力がありましたので、一部修正しました。

 3
3
16372
2746J18
348
4
1234
1234
1234
1234J
5
13645
643125
147
5137J
3245

サンプル出力

15
29
-1
B - ブロック並べ

Time Limit: 20 sec / Memory Limit: 256 MB

いま、赤のブロックが R 個、青のブロックは B 個ある。
あなたは赤と青のブロックを 1 列に並べる。
  1. 連続する rn 個以下のブロックのうち、 rk 個以上が赤のブロックになってはいけない。
  2. 連続する bn 個以下のブロックのうち、 bk 個以上が青のブロックになってはいけない。
上記 2 つの条件を全て満たすブロックの並べ方を 1,000,000,009で割った余りを求めよ。

入力形式

入力の 1 行目にはテストケース数 T を示す。以降、T 個のテストケースが続く。
各テストケースは R B rn rk bn bk の順に与えられる。

出力形式

条件を満たす並べ方を 1,000,000,009で割った余りを 1 行で出力する。

入力制限

1≦T≦50
1≦R,B≦20
1≦rn,bn≦9
1≦rk≦rn
1≦bk≦bn

サンプル入力

間違ったサンプル入力がありましたので、一部修正しました。
6
3 4 2 2 4 3
2 7 5 4 6 5
5 5 4 3 4 3
8 1 9 8 3 2
1 4 2 2 5 5
20 20 9 8 8 7

サンプル出力

1
3
4
0
5
299856304