A - 整数割り算
21:40追記：答えが 0 の時に
2 つの実数 A,\ B\ (B \neq 0) が与えられた時，その割り算の結果 A/B は誰もがよく知っていることと思います．
この問題では，2 つの整数 A,\ B\ (B \neq 0) が与えられた時，その整数割り算 A\ {\rm DIV}\ B を求めるプログラムを書いてください．
ここで，整数割り算 A\ {\rm DIV}\ B とは，A,\ B を実数と見た時の割り算の結果 A/B の小数点以下を無視して得られる整数のことである．
例えば，4\ {\rm DIV}\ 3 は 4/3 = 1.3333... の小数点以下を無視して 1 になり，4\ {\rm DIV}\ (-3) は 4/(-3) = -1.3333... の小数点以下を無視して -1 となる．
また，8/2 = 4 = 3.9999... だが，A/B が整数となる時 A\ {\rm DIV}\ B = A/B とする．つまり 8\ {\rm DIV}\ 2 = 4 である．
最初の行にはテストケースの数 T が与えられる．
その後の行には T 個のテストケースが続く．
各テストケースは 1 行のみからなり，半角スペース区切りで 2 つの整数 A,\ B が与えられる．
各テストケースに対して，整数の割り算 A\ {\rm DIV}\ B を出力せよ．
writer: laycrs
実行時間制限: 2 sec / メモリ制限: 64 MiB
-0を出力しないでください．(-1)\ {\rm DIV}\ 2 = 0 です．
問題文
この問題では，2 つの整数 A,\ B\ (B \neq 0) が与えられた時，その整数割り算 A\ {\rm DIV}\ B を求めるプログラムを書いてください．
ここで，整数割り算 A\ {\rm DIV}\ B とは，A,\ B を実数と見た時の割り算の結果 A/B の小数点以下を無視して得られる整数のことである．
例えば，4\ {\rm DIV}\ 3 は 4/3 = 1.3333... の小数点以下を無視して 1 になり，4\ {\rm DIV}\ (-3) は 4/(-3) = -1.3333... の小数点以下を無視して -1 となる．
また，8/2 = 4 = 3.9999... だが，A/B が整数となる時 A\ {\rm DIV}\ B = A/B とする．つまり 8\ {\rm DIV}\ 2 = 4 である．
入力
その後の行には T 個のテストケースが続く．
各テストケースは 1 行のみからなり，半角スペース区切りで 2 つの整数 A,\ B が与えられる．
制約
- 0 \leq T \leq 10^6
- -2^{63} \leq A, B < 2^{63}（つまり A,\ B は一般的な符号付き 64 ビット整数型に収まる範囲である）
- B \neq 0
出力
入力例
3 10 11 10 10 -3 -2
出力例
0 1 1
B - 一変数方程式
x に関する方程式 ax^2 + bx + c = 0 の実数解を全て求めてください．
最初の行にはテストケースの数 T が与えられる．
その後の行には T 個のテストケースが続く．
各テストケースは 1 行のみからなり，半角スペース区切りで 3 つの整数 a,\ b,\ c が与えられる．
各テストケースに対して，実数解の個数を出力し，その後，全ての実数解を小さい順に，半角スペース区切りで 1 行で出力せよ．
ただし，実数解が 3 個以上あるなら，
絶対誤差，または，相対誤差が 10^{-9} 以下であれば許容される．
writer: laycrs
実行時間制限: 2 sec / メモリ制限: 64 MiB
問題文
入力
その後の行には T 個のテストケースが続く．
各テストケースは 1 行のみからなり，半角スペース区切りで 3 つの整数 a,\ b,\ c が与えられる．
制約
- 0 \leq T \leq 2 \times 10^5
- -2^{31} \leq a, b, c < 2^{31}（つまり a,\ b,\ c は一般的な符号付き 32 ビット整数型に収まる範囲である）
出力
ただし，実数解が 3 個以上あるなら，
3とのみ（シングルクォーテーションを除いて）出力せよ．絶対誤差，または，相対誤差が 10^{-9} 以下であれば許容される．
入力例
3 1 -3 2 -10 30 -20 100 -300 200
出力例
2 1.000 2.000 2 1.000 2.000 2 1.000 2.000
C - 階乗と素因数
N! = 1 \times 2 \times ... \times N に含まれる素因数 p の個数を F(N,\ p) と書くことにする． (ただし p は素数である)
つまり，N!/p^k が整数となるような最大の非負整数 k が F(N,\ p) である．
例えば，N=12 のとき 12! = 479001600 = 2^{10} \times 3^5 \times 5^2 \times 7 \times 11 であるから，F(12,\ 2) = 10,\ F(12,\ 3) = 5,\ F(12,\ 47) = 0 などである．
今，素数 p と整数 x が与えられるので，N-F(N,\ p) = x となる最小の非負整数 N を求めてください．
なお，0! = 1 である．
最初の行にはテストケースの数 T が与えられる．
その後の行には T 個のテストケースが続く．
各テストケースは 1 行のみからなり，半角スペース区切りで p,\ x が与えられる．
各テストケースに対して，N-F(N,\ p) = x となる最小の非負整数 N を出力してください．
ただし，そのような N が存在しなければ
writer: laycrs
実行時間制限: 1 sec / メモリ制限: 31 MiB
問題文
つまり，N!/p^k が整数となるような最大の非負整数 k が F(N,\ p) である．
例えば，N=12 のとき 12! = 479001600 = 2^{10} \times 3^5 \times 5^2 \times 7 \times 11 であるから，F(12,\ 2) = 10,\ F(12,\ 3) = 5,\ F(12,\ 47) = 0 などである．
今，素数 p と整数 x が与えられるので，N-F(N,\ p) = x となる最小の非負整数 N を求めてください．
なお，0! = 1 である．
入力
その後の行には T 個のテストケースが続く．
各テストケースは 1 行のみからなり，半角スペース区切りで p,\ x が与えられる．
制約
- 0 \leq T \leq 5000
- 2 \leq p \leq 47 で p は素数である
- 0 \leq x \leq 50 で x は整数である
出力
ただし，そのような N が存在しなければ
-1 を（シングルクォーテーションを除いて）出力してください．入力例
2 5 0 47 50
出力例
0 51
D - 高橋くんレーシング
21:42追記：R 個のメモは同時刻のものはありません．つまり，同時に 2 回以上誰かが誰かを抜き去るということは起こりません．
高橋くんはレーサーで，
健気なサポーターである青木くんはラジオで高橋くんが参加しているレースのことを聞いていました．
ラジオでは，最初に，スタート直後の全員の順位を発表しました．
青木くんは全ての順位を聞くことはできませんでしたが，高橋くんの順位を聞き取りメモしました．
また，その後，ラジオでは誰かが誰かを抜いた時に，それを全て発表しました．
青木くんは全ての誰が誰を抜いたかという情報をメモしました．
青木くんのメモが与えられるので，高橋くんの最終順位を求めて下さい．
ただし，青木くんは間違えてメモした可能性もあるので，メモに矛盾があったらそれを指摘してください．
出場しているレーサーの名前は全て異なり，アルファベットの大文字と小文字は区別され別の文字とみなされます．
また，抜き去る一瞬を除いて，同じ順位になっているレーサーは 2 人以上はいないものとします．
最初の行にはテストケースの数 T が与えられる．
その後の行には T 個のテストケースが続く．
各テストケースの 1 行目には，出場したレーサーの数 N と，青木くんのメモに含まれる誰が誰を抜いたかという記録の数 R が与えられます．
その次の行には，
ここで，順位は 1 位から順番に
その後の R 行には，誰が誰を抜いたかという記録が時系列順に与えられ，各行は
ここで，
各テストケースに対して，メモに矛盾がある場合は
矛盾がない場合は，
ここで，
入力の形式は，入力の項に書かかれている形式に従います．
例えば，以下の入力は全てinvalidで，テストケースにこのような入力は含まれません．
writer: laycrs
実行時間制限: 15 sec / メモリ制限: 256 MiB
問題文
Takahashiという名前で，合計 N 人の参加者のいるレースに参加しました．健気なサポーターである青木くんはラジオで高橋くんが参加しているレースのことを聞いていました．
ラジオでは，最初に，スタート直後の全員の順位を発表しました．
青木くんは全ての順位を聞くことはできませんでしたが，高橋くんの順位を聞き取りメモしました．
また，その後，ラジオでは誰かが誰かを抜いた時に，それを全て発表しました．
青木くんは全ての誰が誰を抜いたかという情報をメモしました．
青木くんのメモが与えられるので，高橋くんの最終順位を求めて下さい．
ただし，青木くんは間違えてメモした可能性もあるので，メモに矛盾があったらそれを指摘してください．
出場しているレーサーの名前は全て異なり，アルファベットの大文字と小文字は区別され別の文字とみなされます．
また，抜き去る一瞬を除いて，同じ順位になっているレーサーは 2 人以上はいないものとします．
入力
その後の行には T 個のテストケースが続く．
各テストケースの 1 行目には，出場したレーサーの数 N と，青木くんのメモに含まれる誰が誰を抜いたかという記録の数 R が与えられます．
その次の行には，
Takahashi is the 順位をいう形の文字列が与えられ，高橋くんのスタート直後の順位を表す．ここで，順位は 1 位から順番に
1st place，2nd place，3rd place，4th place，5th place，...となり，N+1 位以下を指すことはありません．その後の R 行には，誰が誰を抜いたかという記録が時系列順に与えられ，各行は
名前1 overtakes 名前2という形をしている．ここで，
名前1と名前2は半角アルファベットのみからなり，名前1の名前のレーサーが名前2の名前のレーサーを追い抜いたことを表す．制約
- 0 \leq T \leq 10^4
- 1 \leq N < 2^{64}
- 0 \leq R \leq 4 \times 10^5
Takahashi is the 順位の順位は 1 位から N 位までのどれかを指し示す名前1，名前2は半角アルファベットのみからなる 1 文字以上 20 文字以下の文字列である- 1 つのテストファイルに含まれる R の和は 4 \times 10^5 を超えない
出力
The memo must be wrongと出力してください．矛盾がない場合は，
Takahashi might get the 順位と出力してください．ここで，
順位は，入力の項で説明されているものと同じ形式を用い，メモが正しい場合の高橋くんの最終順位を表してください．入力例
2 3 2 Takahashi is the 2nd place Takahashi overtakes Aoki HechoSamurai overtakes Aoki 2 1 Takahashi is the 1st place Takahashi overtakes Aoki
出力例
Takahashi might get the 1st place The memo must be wrong
注意
例えば，以下の入力は全てinvalidで，テストケースにこのような入力は含まれません．
1 3 0 Takahashikun starts with the 2nd place
1 3 1 Takahashi is the 2nd place Takahashi kicks Aokiただし，
名前1と名前2が異なるなどとは言及されていないことに注意してください．
E - 雲と影
xy 平面が地面であり，地面から鉛直上向きに z 軸を取る．
この問題では，太陽は点（点光源），雲は厚みのない多角形とみなすことにする．
この世界には太陽が 2 つあり，座標 ({8192}^{65536},\ {8192}^{65536},\ {8192}^{65536}) と (-{8192}^{65536},\ -{8192}^{65536},\ {8192}^{65536}) にある．
雲は，上空 H，つまり， z = H の平面上にあり，複数あっても良い．
雲は太陽の光を遮断し，どちらの太陽の光も届かない地面の場所には影ができる．
今，地面に多角形の形をした影が 1 つできた．
地面にできた影の形が与えられるので，雲の合計面積の最小値を求めてください．
最初の行にはテストケースの数 T が与えられる．
その後の行には T 個のテストケースが続く．
各テストケースの 1 行目には，影の多角形の頂点の数 N と，雲の位置の z 座標の値 H が半角スペース区切りで与えられる．
その後の N 行には，各頂点の x 座標と y 座標が半角スペース区切りで与えられる．
ここで，多角形の頂点は，時計回り，または，反時計回りで与えられる．
各テストケースに対して，雲の合計面積の最小値を出力してください．
その際，小数第 3 位を四捨五入し，小数第 2 位まで出力してください．
writer: laycrs
実行時間制限: 2 sec / メモリ制限: 64 MiB
問題文
この問題では，太陽は点（点光源），雲は厚みのない多角形とみなすことにする．
この世界には太陽が 2 つあり，座標 ({8192}^{65536},\ {8192}^{65536},\ {8192}^{65536}) と (-{8192}^{65536},\ -{8192}^{65536},\ {8192}^{65536}) にある．
雲は，上空 H，つまり， z = H の平面上にあり，複数あっても良い．
雲は太陽の光を遮断し，どちらの太陽の光も届かない地面の場所には影ができる．
今，地面に多角形の形をした影が 1 つできた．
地面にできた影の形が与えられるので，雲の合計面積の最小値を求めてください．
入力
その後の行には T 個のテストケースが続く．
各テストケースの 1 行目には，影の多角形の頂点の数 N と，雲の位置の z 座標の値 H が半角スペース区切りで与えられる．
その後の N 行には，各頂点の x 座標と y 座標が半角スペース区切りで与えられる．
ここで，多角形の頂点は，時計回り，または，反時計回りで与えられる．
制約
- T,\ N については以下の 2 つの条件のどちらか一方を満たす
- 0 \leq T \leq 4096 かつ 3 \leq N \leq 16
- T = 1 かつ N = 2048
- 1 \leq H \leq 64 で H は整数である
- 多角形の各頂点の座標の値の絶対値は 32 を超えない
- 多角形の各頂点の座標の値は小数点以下がちょうど 2 桁であるような小数で与えられる
- 多角形は単純である．つまり自己交差を持たない
- 多角形の連続する 3 つの頂点は一直線上にはない
出力
その際，小数第 3 位を四捨五入し，小数第 2 位まで出力してください．
入力例
2 4 5 0.00 1.00 1.00 1.00 1.00 0.00 0.00 0.00 3 64 0.00 1.00 1.00 0.00 0.00 0.00
出力例
2.00 1.00