問題
N人の人がいる（player 0 ... player N-1）。1 ~ 5N の数が書かれたカードが1枚ずつあり、入力で与えられる順に（A[0] ... A[5N-1]）山札に並んでいる。
次の方法で一人5枚づつ配る。
上から2N枚を2枚づつ配る、つまりA[0], A[1]をplayer 0に、A[2], A[3]をplayer1に、A[2N-2], A[2N-1]をplayer N-1に。
続く2N枚（A[2N]~A[4N-1]）を同様に2枚づつ配る。
残りのN枚を1枚づつ配る。
つまり、player 0にはA[0], A[1], A[2N], A[2N+1], A[4N]、player 1にはA[2], A[3], A[2N+2], A[2N+3], A[4N+1]が配られる。
配り終えたら終了判定を行う。
1から5のカードを全て持っているplayerがいたらそのplayerが勝利し、ゲームは終了する。
勝利者がいない場合、plater 0のカードが上に来るように順にカードを山札に並べる。
この一連の動作を1ターンとし、ゲームが終了するまで繰り返す。
ゲームが終了するのはどのplayerが勝利し、何ターン目にカードを配った時か求めよ。
ゲームが終了しない場合はそれを指摘せよ。
N<=1000
解法
1から5のカードについてそれぞれどの位置に何ターン目で配られるか求める。
するとA[i]の位置にj+1 (0<=j<=4)が来るターンは C[i]*x + B[i][j] (xは非負整数）という式ができる（到達しないカードと位置の組は適当に弾く）。
player kが勝つターンを求める。
勝つタイミングでの1~5のカードの並びをP[0]..P[4]とし、0<=j<=4について
C[5k+j]*x_j + B[5k+j][P[j]] = T
となるTを求めることになる。
これは
T = B[5k+j][P[j]] (mod C[5k+j])
を満たす1以上の最小の整数Tを求める問題であり、線形連立合同式、中国の剰余定理で解くことが可能。
全てのplayerの中で勝つターンが一番早い人の勝利である。
ただ、Pの並びをnext_permutaionで全て処理するとTLEしてしまったので、到達しないカードの組についての枝刈りを自前のnext_permutaionに組み入れて高速化した。
解くときに気がついたが某有名ライブラリの線形連立合同式間違ってると思う。
