A.txt

G(<= 50,000)人の客とW(<= 50,000)個の洗面所がある．
客にいずれかの洗面所に並ばせて使わせるとき，全員の待ち時間と洗面所を使う時間の総和をWSIという．
最初，それぞれの客の使用時間はわかっている．
そこに1人の客の使用時間を更新させるクエリがQ(<= 10,000)回くるので，更新されるごとにWSIを計算して出力しろ．

テストケース数T(T <= 16)

B.txt

N(<=60)人の先生が最大K(<=200)点の非負整数の点数をつけるとき，その平均をAとする．
そのときA点をつけた先生が少なくとも1人いるような場合をmatching eventsと呼ぶ．
すべての点数のつけかたのうち，matching eventsなものは何通りあるか．10^9+7で割ったあまりを答えろ．

テストケース数T(T <= 1001)

C.txt

3次元空間上で時刻T=0(ms)に粒子が原点からとんでいく．粒子は以下の規則に従う．
1. 粒子の飛ぶ向きは(0,0,0)を始点として直線方向
2. すべての粒子は時刻T = 0からとびだす．2つの粒子は同じ向きを持つことがあるが，その場合同じスピードにはならない
3. 粒子のスピードは変化しない
4. 粒子の個数は無制限
5. 粒子の速度はx, y, z方向の全てで正になる
6. 粒子は点として扱う
7. 粒子は整数時刻に格子点上に存在するときのみ観測される

格子点の各成分(x,y,z)がN以下になる位置で粒子を観測するとき，最大何個のdistinctな粒子を観測できるか．
各テストケースは5つの正整数からなり，それぞれをNとしたときの答えを出力しろ．
制約は4つ目まではN <= 20,000, 5つ目はN <= 80,000

D.txt

2人の友達が2次元座標上の格子点A, Bにいる．あなたは以下の条件を満す位置Cから写真をとりたい．
1. CはAともBとも違う
2. 線分AC上には端点を除いて格子点がない
3. 線分BC上には端点を除いて格子点がない
4. 三角形ABCは正の面積をもつ
5. 三角形ABCの内部(周上は含まない)には格子点がない

このようなCをK個みつけよ．
AとBの各成分をAx, Ay, Bx, Byとすると -10^9 <= Ax, Ay, Bx, By <= 10^9
テストケース数T(1 <= T <= 1,000)で，全てのテストケースのKの総和は20,000を越えない

テストケース数T(T <= 1000)

E.txt

N(<= 50,000)個の地域からなる街がある．N-1個の道が地域を結んでいて，木構造になっている．
各道にはそれぞれ重み(<= 100,000)が付いていて，地域Aから地域Bまで行くには，その経路上の辺の重みの中央値の税金がかかる．
今Q(<= 100,000)個の2つの地域のペアについて，それぞれの移動するときにかかる税金を答えろ．

テストケース数T(T <= 15)

F.txt

次のような2人ゲームを考える．
N(<= 50, 000)個の40文字以下の単語からなる辞書が与えられる．
2人プレイヤーは1つの単語X(辞書にある必要はない)を選ぶ．
Xをprefixに持つ単語全てからXの末尾の文字以降を削除する．
例えば，辞書が{ bangladesh, bangalore, band, bandana }で"bang"を選んだ場合，辞書は { ban, ban, band, bandana } となる．
先に辞書内にprefixが一致する単語が存在するような単語を選べなくなったほうが負け．
辞書にQ(<= 50,000)個の単語を順に追加していくとき，追加のごとに先手後手どちらが勝つか答えよ．

テストケース数T(T <= 10)

G.txt

以下の条件を満すようなビット列(0からはじまってもいい)は何通り考えられるか．10^9+7で割ったあまりを答えよ．
1. 長さはL以上R以下 (1 <= L <= R <= 10^18)
2. 長さはKで割りきれる (3 <= K <= 10^9)
3. 連続した1を持たない

テストケース数Tは (1 <= T <= 10,000)

H.txt

ノックアウトされるまで敵を1体ずつ倒し，倒した数を競う競技がある．
残りの体力を増やすポーションがあるが，ポーションには毒があり，また1度に1つしか飲めない．
今N(< = 8)個のポーションをもっている．
ポーションiを飲むとEi(1 <= Ei <= 100)だけ追加の体力得て(ただし100を越えない)，Pi(1 <= Pi <= 100)だけ毒が蓄積する．
毒の蓄積が100に到達すると，ノックアウトされる．
毒は1分経過すると1だけ消える．
ポーションは敵を倒した直後のみ残っているポーションのいずれかを飲むかどうか決定できる．
初期体力を100， 敵を倒すのに消費する体力をK(10 <= K <= 80)， かかる時間をM (M <= 100) とする．
残りの体力がKより大きいとき敵を倒せる．
最大何体の敵を倒せるか

テストケース数T(T <= 20)

I.txt

New BangkokはN(<= 100,000)個の街からなる．街の間には合計N-1個の道があり，どの街からどの街へもそれらの道を使って到達できるし，そのような道は常に1つしかない．
街Bから首都への経路上に街Aがあるとき，街Aは街Bからの税を扱う必要がある．
このとき以下のどちらかのクエリが合計Q(<= 50,000)回くるので処理しろ．
1. 首都をUに変更する
2. 街Uが扱う税の数を出力

テストケース数T(T <= 10)

J.txt

出版社はN冊の本をX日で出版しなければならない．
i番目の本は印刷を開始してから出版までにAi(<= 1,000,000)日かかり，Ci(<= 1,000,000)だけコストがかかる．
しかし，1日あたり追加でDi(<= 100)だけ払うと最短でBi(<= Ai)日まで短縮できる．
いくつかの組(u,v)が与えられて，vの印刷作業はuの出版より後に開始される必要がある．(組の数は最大でN*(N-1)/2)
N冊全ての本がX日以内に出版されるのに必要な費用が最小となる出版の方法について，各本の出版開始日と短縮させる日数を出力せよ．
そのような操作が存在しないときは"Impossible"と出力せよ．

テストケース数T(T <= 300)
85%のテストケースは (N <= 30)
3つのテストケースは (N = 200)
それ以外テストケースは (30 <= N <= 100)

K.txt

1からNまでの番号をそれぞれもつN(<= 100)個の頂点を考える．
それらの頂点のいくつかをランダムに選ぶ．各頂点には選ばれる確率が存在する．
選ばれたの頂点の集合について，2つの頂点はその番号のGCDが1より大きいとき，その間に辺をもつ．
その集合内で連結な成分の個数の期待値を求めよ．
ただし求められた期待値をEとして E * 100^N mod 1,000,000,007 で出力しろ．

テストケース数T(T <= 100)

L.txt

惑星Tabooは10^8x10^8のグリッドで，そこにある全ての反乱軍の基地の位置を特定しようとしている．位置は(x,y)の形式で表現される．
今，いくつかの反乱軍の基地を制圧して他の基地の場所を聞きだしているが，2つ基地がx方向とy方向でそれぞれいくら離れているかの情報しか得られなかった．
基地の位置として考えうるものを1つ出力しろ．
残りの基地の数N(1 <= N <= 100,000)
各距離dx, dy (-10^8 <= dx, dy <= 10^8)
出力は-10^9から10^9の範囲