ストーリー

始まりは、ある夜のことだった。そのころ、僕といろはちゃんはカラフルなブロックを積むゲームにハマっていた。そのゲームは何の変哲もないものだったが、数多くのバグが存在していた。例えば、消えるはずのブロックが消えなかったり、風が吹いてブロックが飛んだり、変な浮島が現れたり。

その夜、僕といろはちゃんはこのゲームでオンライン対戦をしていたが、その対戦結果が変だった。「スコアを計算する部分にもバグがあるんじゃないですか？」いろはちゃんの一言を、僕は本当か確かめることにした。

問題文

このゲームは 4 人プレイにのみ対応しており、各ラウンドで 1 位～ 3 位になると順位に応じた得点が得られる。各ラウンドの対戦結果が引き分けになることは無い。スコア表示画面では各々の得点が加算された履歴を見ることができる。

例えば、あるプレイヤーについて「1 2 2」と表示されている場合、そのプレイヤーはどこかのラウンドで 1 位を取り、それ以降のどこかのラウンドで 2 位を取り、それ以降のどこかのラウンドで 2 位を取り、それ以降のラウンドでは得点を獲得していないことがわかる。

僕といろはちゃんは N ラウンドの対戦を行った。4 人それぞれについて、N ラウンドのスコアデータが入力されるので、そのゲーム結果があり得るかを出力せよ。また、あり得るならば各ラウンドの対戦結果の例を出力せよ。

制約

• 入力はすべて整数
• 0 \leq A,B,C,D \leq 100
• 1 \leq N \leq 100
• 1 \leq a_i \leq 3 (1 \leq i \leq A)
• 1 \leq b_i \leq 3 (1 \leq i \leq B)
• 1 \leq c_i \leq 3 (1 \leq i \leq C)
• 1 \leq d_i \leq 3 (1 \leq i \leq D)

入力例 1

1 1 1 1 0
1
3
2

出力例 1

Yes
4

入力例 2

1 0 0 0 0

出力例 2

No

入力例 3

10 8 7 8 7
1 3 1 3 1 3 1 2
3 3 1 2 3 3 3
2 2 2 1 1 2 2 1
1 2 3 2 2 1 3

出力例 3

Yes
4
2
4
3
3
2
1
4
1
2

解説

ストーリー

闇をつんざくような叫び声。僕もいろはちゃんもすぐに外の様子に気がついた。遠くの街のほうが赤く光って、異音を轟かせながら揺れる。「あれって…！」僕が"それ"に気がついたときには、いろはちゃんはもう走り出していた。

問題文

いろはちゃんのいる町には \(M+1\) 個の駅と \(N\) 個の電車があり、それぞれ \(1\) から \(M+1\)、\(1\) から \(N\) の番号が付けられている。

現在の時刻は \(0\) である。今いろはちゃんは駅 \(1\) におり、駅 \(M+1\) に行こうとしている。

電車 \(i\) は時刻 \(A_i\) に駅 \(1\) を出発し、駅 \(j+1\ (1≦j≦M)\) には時刻 \(A_i+B_i\times j\) に着く。

また、いろはちゃんは走ることで駅 \(k\ (1≦k≦M)\) と駅 \(k+1\) の間を \(L\) 単位時間かけて移動できる。

いろはちゃんは駅で移動手段を変えることができ、これにかかる時間は無視できる。駅以外の場所で移動手段を変えることはできない。

いろはちゃんが駅 \(M+1\) に着く最速の時刻を求めよ。

制約

• 入力はすべて整数
• \(1≦N≦10^5\)
• \(1≦M, L≦3\times10^8\)
• \(0≦A_i≦10^{17}\)
• \(1≦B_i≦3\times10^8\)

入力例 1

3 3 4
4 2
2 3
3 4

出力例 1

10

次のように移動すると、駅 \(M+1\ (=4)\) に時刻 \(10\) に着くことができる。

• 電車 \(2\) の出発を待つ ( 時刻 \(0\) - 時刻 \(2\) )
• 電車 \(2\) に乗って駅 \(2\) まで行く ( 時刻 \(2\) - 時刻 \(5\) )
• 電車 \(1\) を待つ ( 時刻 \(5\) - 時刻 \(6\) )
• 電車 \(1\) に乗って駅 \(4\) まで行く ( 時刻 \(6\) - 時刻 \(10\) )

入力例 2

3 3 3
4 2
2 3
3 4

出力例 2

9

次のように移動すると、駅 \(M+1\ (=4)\) に時刻 \(9\) に着くことができる。

• 駅 \(4\) まで走る ( 時刻 \(0\) - 時刻 \(9\) )

入力例 3

1 100 10
100 1

出力例 3

200

次のように移動すると、駅 \(M+1\ (=101)\) に時刻 \(200\) に着くことができる。

• 駅 \(2\) まで走る ( 時刻 \(0\) - 時刻 \(10\) )
• 駅 \(1\) まで走る ( 時刻 \(10\) - 時刻 \(20\) )
• 駅 \(4\) まで走る ( 時刻 \(20\) - 時刻 \(50\) )
• 駅 \(4\) で \(20\) 単位時間留まる ( 時刻 \(50\) - 時刻 \(70\) )
• 駅 \(1\) まで走る ( 時刻 \(70\) - 時刻 \(100\) )
• 電車 \(1\) に乗って駅 \(101\) まで行く ( 時刻 \(100\) - 時刻 \(200\) )

入力例 4

3 139128390 220019821
3162336416461334 196423673
2909210940940890 272140126
31923189201903829 68312342

出力例 4

30490445798837804

解説

ストーリー

駅に着いた僕が見たのは、異形と戦ういろはちゃんだった。まるで舞っているかのように動き回り、敵を翻弄している。

それでも、一向に異形の勢いは衰えない。敵の数が多すぎる。僕も、見てるだけじゃダメだ。君の、力に！

問題文

今、敵が M 体いて、 i 番目の敵は最初はあなたのいるところから x_i+0.5 だけ離れたところにいますが、1 秒ごとに 1 だけあなたに近づきます。敵との距離が 0 になるとあなたは死んでしまいます。厳密には、距離が 0.5 の敵にさらに近づかれたときあなたは死んでしまいます。
また、それぞれの敵は0と1からなる固有の文字列を持っており、 i 番目の敵が持っている文字列は s_iです。

あなたはぶきを持っており、ぶきも0と1からなる文字列 Sを持っています。 あなたはそのぶきを使って、次の 2 つのことができます。

• 一番自分に近い敵を倒す。ただし、敵の持つ文字列よりぶきの持つ文字列のほうが辞書順で大きくなければならない。
• 1 秒間かけてぶきに魔法をかけ、文字列を変更する。

ただし、攻撃にかかる時間は十分小さく、無視できるものとします。また、どちらの行動においてもあなたは最初にいた場所から移動することはありません。

あなたが使える魔法は、あなたのぶきの持つ文字列を、次のように変更します。

• 文字列の先頭に0を 2 つ加える。
• それぞれの文字の下に、右隣と左隣の数字が等しいなら0、異なるなら1を書く。ただし、右隣か左隣のどちらかの文字が存在しない場合は何も書かない。
• 下に書かれた文字列を、新しい文字列とする。

例えば、あなたのぶきが文字列1101を持っているときに魔法を使用すると、以下のようにして新しい文字列は1110となります。

M 体の敵の情報と、あなたのぶきが最初に持つ文字列 S が与えられるので、あなたが無事に生き残ることができるか判定してください。

制約

• 0 \leq M \leq 10^5
• 0 < x_1 \leq x_2 \leq \dots \leq x_M \leq 10^{18}
• 1 \leq |s_i| (i=1,2,\dots,M)
• \displaystyle\sum_{i=1}^M |s_i| \leq 10^5
• 1 \leq |S| \leq 10^5
• s_i および S はすべて0または1からなる文字列

入力例 1

1101
2
1 1001
2 1101

出力例 1

Yes

以下のようにして、すべての敵を倒すことができます。

• 一番近い敵を倒す。
• 1 秒かけてぶきに魔法をかける。ぶきの持つ文字列は1110となる。敵が 1 近づく。
• 一番近い敵を倒す。

入力例 2

1101
2
1 1001
2 1110

出力例 2

No

敵を倒すとき、ぶきの持つ文字列の方が辞書順で大きくなければなりません。

入力例 3

1111
4
1 1
2 011
3 1100
7 0000001

出力例 3

Yes

1 度も魔法を使わなくても全ての敵を倒せることもあります。

入力例 4

00000000
1
1000000000000000000 1

出力例 4

No

何度魔法を使っても倒せない敵がいることもあります。

入力例 5

0110011000
10
1 100
2 0111
3 0000
5 1
5 0
6 0000001
7 11
7 00
8 00
9 0101

出力例 5

No

解説

解説

ストーリー

「いったい、なんだったんでしょうか…」帰り道、いろはちゃんがぽつぽつと話し始める。 「さっきの化け物、明らかにおかしいです」「あんなの、この世界にいていいものじゃありません」「あれはまるで、バグ…」

彼女の言葉を遮るように、轟音が響き渡った。しかも、今度は何回も。僕たちは顔を見合わせ、走り出した。

問題文

\(T\) 個の街で、それぞれ敵が出現した。

\(i\) 番目の街で出現した敵は、一列に並んだマス状の形をしており、元々のマスの個数は \(1\) 個以上 \(L_i\) 個以下である。 街ではすでに敵のマスのうち \(0\) 個以上を破壊し、敵は破壊されたマスで分割されたいくつかの部分に分かれている。マスの個数が \(L\) の敵は、端から \(i\) 番目のマスを破壊されると、マスの個数がそれぞれ \(i-1\) と \(L-i\) の \(2\) つの敵に分割される(ただし、マスの個数が \(0\) の敵は消滅する)。

しかし、その敵は分割されると強くなってしまうものだった。具体的には、マスの個数が \(p_1, p_2, \dots, p_n\) である \(n\) 個の部分に分割されたとき、敵の強さは全体で \(p_1\times p_2\times\dots\times p_n\) になってしまう。

現在、\(i\) 番目の街では敵の強さが \(2^{A_i}\) 以上になってしまったという。敵の元々のマスの個数としてありうるものが何通りあるかを、\(T\) 個の街に現れた敵それぞれについて求めよ。

制約

• 入力はすべて整数
• \(1≦T≦300\)
• \(1≦L_i≦10^9,\ 0≦A_i≦10^9\)

入力例

4
9 3
13 4
11 6
11235813 213455

出力例

3
5
0
10702177

\(1\) 番目の街に出現した敵の元々のマスの個数は \(7, 8, 9\) の \(3\) 通りがあり得る。

それぞれ、敵が次のように破壊されたの場合に条件を満たす(oはマスが破壊されていないことを、xは破壊されていることを表す)。

• 敵の元々のマスの個数が \(7\) : ooxoooo (敵の強さは \(8\))
• 敵の元々のマスの個数が \(8\) : ooxooxoo (敵の強さは \(8\))
• 敵の元々のマスの個数が \(9\) : oooxoxooo (敵の強さは \(9\))

\(2\) 番目の街に出現した敵の元々のマスの個数は \(9, 10, 11, 12, 13\) の \(5\) 通りがあり得る。

それぞれ、次のような破壊のされ方の場合に条件を満たす。

• 敵の元々のマスの個数が \(9\) : ooooxoooo (敵の強さは \(16\))
• 敵の元々のマスの個数が \(10\) : ooxooxoooo (敵の強さは \(16\))
• 敵の元々のマスの個数が \(11\) : oooxooooxoo (敵の強さは \(24\))
• 敵の元々のマスの個数が \(12\) : oooooooooxoo (敵の強さは \(18\))
• 敵の元々のマスの個数が \(13\) : ooooxoooooooo (敵の強さは \(32\))

\(3\) 番目の街に出現した敵の元々のマスの個数は \(0\) 通りがあり得る。

解説

ストーリー

戦いの中、不思議と冴えた頭で思い出すのは昔のこと。

今からすれば他愛のない、単純な石取りゲームで打ち負かされ、泣いていた僕。その目の前に現れた、ヒーローのようなヒロイン。 それが僕にとっての憧れ、そして、彼女の隣にいたいという気持ちの芽生えだ。

問題文

次のようなゲームを考えます。

• 初期盤面として N 個の机があり、それぞれにりんごが 0 個以上 K 個以下乗っている。
• あなたから初めて、2 人は交互に次の行動をし、先にできなくなった方が負け。
  • 机を 1 つ選んで、それに乗っているりんごを 1 つ以上食べる。

2 人とも最善を尽くしたときにあなたが勝つような初期盤面は何通りあるでしょうか。答えは非常に大きくなる可能性があるため、 10^9+7 で割った余りを答えてください。

制約

• 入力はすべて整数
• 1 \leq N \leq 2000
• 0 \leq K \leq 10^{18}

入力例 1

3 2

出力例 1

20

N=3,K=2 のとき、条件を満たす初期盤面は次の 20 通りです。

(0,0,1), (0,0,2), (0,1,0), (0,1,2), (0,2,0), \\(0,2,1), (1,0,0), (1,0,2), (1,1,1), (1,1,2), \\(1,2,0), (1,2,1), (1,2,2), (2,0,0), (2,0,1), \\(2,1,0), (2,1,1), (2,1,2), (2,2,1), (2,2,2)

入力例 2

2 99

出力例 2

9900

入力例 3

3 5

出力例 3

188

N=3, K=5 のとき、条件を満たす初期盤面は 188 通りあります。

入力例 4

7 20

出力例 4

744195543

解説

解説

ストーリー

僕たちは敵の湧いてくる方角へと駆けた。敵を倒しながら獣道を行くと、酷く損傷して、辛うじて汽車のように見えるものがあった。

僕は急に、「行かねば」という焦燥感と、「行っていいのか」という不安との板挟みになった。

でも前へ、 それでも前へ。

問題文

N 両からなる汽車があります。 それぞれの車両には 3 つの部品があり、車両 k が出すことのできる速度はそれぞれの部品 A,B,C の持つパワー A_k,B_k,C_k の和で表されます。

どの部品も、0 以上 F 以下のパワーを持ちます。

汽車の各車両の出すことのできる速度が降順になっていないと、進む途中で汽車が崩壊してしまいます。

あなたといろはちゃんはなるべく少ない部品を改造して、汽車が崩壊しないようにしたいと思っています。改造しても、0 以上 F 以下のパワーを持った部品しか作ることはできません。
すべての i<j に対して、(車両 i が出すことのできる速度) \geq (車両 j が出すことのできる速度) となるように、改造する部品の個数の最小値を求めてください。

制約

• 入力はすべて整数
• 1 \leq N \leq 2\times10^5
• 1 \leq F \leq 10^{10}
• 0 \leq A_k, B_k, C_k \leq F

  (制約の上限が間違っていたため修正しました 修正日時 : 2019/05/03 19:06)

部分点

• N \leq 3000 を満たすテストケースすべてに正解した場合、300 点が与えられる。

入力例 1

3 100
80 100 60
30 50 70
90 10 80

出力例 1

1

例えば、車両 2 の部品 B のパワーを 85 に変えると、各車両の合計が 240, 185, 180 になり汽車が連結のまま進めるようになります。

入力例 2

4 100
30 10 40
10 50 90
20 60 50
30 50 80

出力例 2

2

例えば、車両 1 の部品 B のパワーを 90 にして、車両 4 の部品 C のパワーを 10 に変えると、各車両の合計が 170, 150, 130, 90 になり汽車が連結のまま進めるようになります。

入力例 3

4 100
0 0 0
0 0 100
100 100 0
100 100 100

出力例 3

4

全車両の出すことができる速度を同じにするのが最適な場合もあります。

入力例 4

10 100
100 37 49
100 37 49
100 37 49
100 37 49
100 37 49
100 37 49
100 37 49
100 37 49
100 37 49
100 37 49

出力例 4

0

入力例 5

5 10000000000
1701355307 429870732 6220675835
286943432 6531822025 3789827719
2265045229 9897189805 5070400071
8975758188 6810134144 5515765460
7476103030 3953670242 7426723712

出力例 5

4

解説

解説

制約

• 入力はすべて整数
• 1 \leq N \leq 300
• 0 \leq K \leq N
• 1 \leq a_i,b_i\leq 2N (i=1,2,\dots,K)
• a_1,a_2,..,a_K,b_1,b_2,..,b_Kはすべて異なる

入力例 1

3 0

出力例 1

5

魔法陣の複雑さの最小値は0です。
線分がひとつも交差しないようなペアの組み方は5通りあります。

7 3
1 13
3 11
9 4

4

複雑さの最小値は2です。 複雑さ2を達成するペアの組み方は以下の4通りです。
・(2,10),(5,6),(7,8),(12,14)
・(2,10),(5,8),(6,7),(12,14)
・(2,14),(5,6),(7,8),(10,12)
・(2,14),(5,8),(6,7),(10,12)

30 15
44 36
1 11
53 21
38 52
8 22
26 42
35 2
23 37
30 58
18 17
3 33
51 9
39 14
12 41
4 49

1136