パ研合宿2019　第4日「Teamwork」

A - 原稿用紙

実行時間制限: 1 sec / メモリ制限: 1024 MiB

配点: 100 点

問題文

原稿用紙 1 枚には，最大 400 文字を書くことができます．

N 文字の文章を書くのに，最小で何枚の原稿用紙を用意する必要があるか，計算してください．

制約

1 \leq N \leq 1 \ 000 \ 000．
N は整数

部分点

この問題には部分点は存在せず，すべてのテストケースに正解すると 100 点が与えられます．

入力

入力は以下の形式で標準入力から与えられます．

出力

最小で原稿用紙何枚を用意する必要があるか，整数で出力してください．

入力例 1

出力例 1

原稿用紙 3 枚を使うと，最大で 3 \times 400 = 1200 文字を書くことができます．

入力例 2

出力例 2

1 文字書くのにも，原稿用紙 1 枚必要です．

入力例 3

出力例 3

B - 情報の伝達

実行時間制限: 1 sec / メモリ制限: 1024 MiB

配点: 100 点

問題文

パ研市民は，重大な情報を知ったら，そのちょうど 1 分後に，まだ情報を得ていない 5 人の市民を集め，同時に重大な情報を伝えます．

さて，パ研市民のパ研君は，重大情報を手に入れました．彼は，パ研市民で初めてその情報を手に入れた者です．

パ研君が情報を得てから N 分後には，最大で何人の市民に情報が伝わっているでしょうか．ただし，ちょうど N 分後に情報を得た人も含めて数えるものとします．また，パ研市民の数は十分に多いものとします．

制約

1 \leq N \leq 20．
N は整数

部分点

この問題はいくつかの小課題に分けられ，その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます．
提出したソースコードの得点は，正解した小課題の点数の合計となります．

(50 点) N = 1．
(50 点) 追加の制約はない．

入力

入力は以下の形式で標準入力から与えられます．

出力

N 分後には何人の市民に情報が伝わっているか，整数で出力してください．

入力例 1

出力例 1

1 分後には，パ研君と，彼から情報を伝えられた 5 人の，合計 6 人の市民に重大情報が伝わっています．

入力例 2

出力例 2

1 分後には 1 \times 5 = 5 人に，新たに情報が伝わります．
2 分後には 5 \times 5 = 25 人に，新たに情報が伝わります．
合計で，1+5+25=31 人に情報が伝わります．

入力例 3

出力例 3

C - 罰ゲーム

実行時間制限: 1 sec / メモリ制限: 1024 MiB

配点: 100 点

問題文

A 君は，L_1 以上 R_1 以下の整数が等確率で出るサイコロを一つ持っています．

B 君は，L_2 以上 R_2 以下の整数が等確率で出るサイコロを一つ持っています．

C 君は，L_3 以上 R_3 以下の整数が等確率で出るサイコロを一つ持っています．

さて，三人がそれぞれ持っているサイコロを振り，一番小さい目が出た人は，罰ゲームを受けなければなりません．ただし，そのような人が二人以上いた場合は，誰も罰ゲームを受ける必要はありません．

A 君が罰ゲームを受ける確率を計算してください．

制約

1 \leq L_1 \leq R_1 \leq 100 \ 000．
1 \leq L_2 \leq R_2 \leq 100 \ 000．
1 \leq L_3 \leq R_3 \leq 100 \ 000．
入力はすべて整数

部分点

(16 点) L_2 = R_2 = L_3 = R_3 = 10．
(35 点) R_1, R_2, R_3 \leq 200
(29 点) R_1, R_2, R_3 \leq 4 \ 000
(20 点) 追加の制約はない．

入力

入力は以下の形式で標準入力から与えられます．

L_1 R_1
L_2 R_2
L_3 R_3

出力

A 君が罰ゲームを受ける確率を出力してください．
絶対誤差または相対誤差が 10^{-5} 未満であれば，正解となります．

入力例 1

1 100
10 10
10 10

出力例 1

0.090000000000000

A 君のサイコロの出目が 1, 2, 3, 4, 5, 6, 7, 8, 9 のいずれかである場合，彼が罰ゲームを受けなければなりません．
そのような確率は \frac{9}{100} = 0.09 です．

入力例 2

1 6
1 6
1 6

出力例 2

‭0.254629629629630

例えば，A 君のサイコロの出目が 2，B 君のサイコロの出目が 3，C 君のサイコロの出目が 6 の場合は，A 君が罰ゲームを受けなければなりません．

入力例 3

2212 3741
1725 2601
1644 2479

出力例 3

0.009579046784

D - リミックスジュース

実行時間制限: 1 sec / メモリ制限: 1024 MiB

配点: 100 点

問題文

ひらきち君は，以下の問題を作りました．

n 個のりんごが一列に並んでおり，i 番目のりんごの大きさは a_i です．
ここから連続する 1 つ以上のりんごを選ぶ選び方のうち，大きさの和が k 以下になるものはいくつありますか？
制約:
    入力はすべて整数
    1 \leq n \leq 1000
    0 \leq a_i \leq 10^9
    0 \leq k \leq 10^9

ところで，ひらきち君は悪夢を見ました．夢の中で世界は PAKEN 連邦に支配されており，あなたは不幸にも捕まってしまいます．あなたをかばい，すべての責任を負うひらきち君に対し，PAKEN 連邦の指導者 E666666 に言い渡された釈放の条件とは...

E666666「なに？貴様は競技プログラミングの選手だと？それなら答えてみろ:

上述の問題の入力であって，n=N かつ答えが X となるものがあるか判定し，あるならば 1 つ示せ。

できたら許してやる．できなかったらミックスジュースだ．」

あなたはミックスジュースになりたくないので，疲れて寝てしまったひらきち君の代わりに上の質問に答えることにしました．

制約

N は 1 以上 1000 以下の整数
X は 0 以上 \frac{N(N+1)}{2} 以下の整数

部分点

この問題はいくつかの小課題に分けられ，その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます．

提出したソースコードの得点は，正解した小課題の点数の合計となります．

(20 点) N \leq 20 を満たす．
(6 点) X=1 を満たす．
(15 点) X=\frac{S(S-1)}{2} を満たす整数 S が存在する．
(59 点) 追加の制約はない．

入力

入力は以下の形式で標準入力から与えられます．

N X

出力

条件にあてはまる入力が存在しなければ -1 と出力してください．

存在するならば，一例を次のように出力してください．

k
a_1 a_2 \dots a_N

入力例 1

6 14

出力例 1

15
8 6 9 1 2 0

E - IOI のために

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点: 100 点

問題文

時は 20XX 年．IOI (International Olympiad in Iconoclasm) はいまや誰もが知る有名な大会となり，毎年の夏と冬に開催されています．

20XX 年の IOI は Kclc 王国で開かれます．IOI 王国委員会の管理人を務めるスクエアは，エクスカージョンの道のりを考えることにしました．

IOI で使用できる Kclc 王国の土地は N 個あり，この間には M 本の道路が通っています．土地には 1 から N の，道路には 1 から M の番号がつけられています．どの 2 土地の間も，道路をいくつか通って行き来できます．

道路 i は土地 A_i と土地 B_i を双方向につないでおり，通行にかかる時間は夏のとき S_i，冬のとき W_i です．

土地 1 から出発し土地 N に到着する道のりを 遠足ルート と呼ぶことにします．

夏か冬の少なくとも片方の季節に次の条件を満たすような遠足ルートは何通りあるでしょうか．

通行にかかる総時間がより短いような遠足ルートが存在しない．

答えは非常に大きくなることがあるので，10^9+7 で割ったあまりを出力してください．

制約

入力はすべて整数
2 \leq N \leq 2 \times 10^5
1 \leq M \leq 2 \times 10^5
1 \leq A_i, B_i \leq N\ (1 \leq i \leq M)
どの 2 土地の間も，道路をいくつか通って行き来できる
1 \leq S_i, W_i \leq 10^9\ (1 \leq i \leq M)

部分点

この問題はいくつかの小課題に分けられ，その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます．

提出したソースコードの得点は，正解した小課題の点数の合計となります．

(5 点) M=N-1 を満たす．
(15 点) N \leq 10 を満たす．
(20 点) 任意の 1 \leq i \leq M について，S_i = W_i を満たす．
(35 点) N \leq 1000 を満たす．
(25 点) 追加の制約はない．

入力

入力は以下の形式で標準入力から与えられます．

N M
A_1 B_1 S_1 W_1
:
A_M B_M S_M W_M

出力

夏か冬の少なくとも片方の季節に条件を満たすような遠足ルートの個数を 10^9+7 で割ったあまりを出力してください．

入力例 1

出力例 1

条件を満たす遠足ルートは以下の 6 つです．

道路 1, 7 の順に通る．夏と冬の両方で条件を満たす．
道路 2, 5, 7 の順に通る．夏と冬の両方で条件を満たす．
道路 2, 6, 7 の順に通る．冬のときのみ条件を満たす．
道路 3, 5, 7 の順に通る．冬のときのみ条件を満たす．
道路 3, 6, 7 の順に通る．冬のときのみ条件を満たす．
道路 2, 8 の順に通る．夏のときのみ条件を満たす．

入力例 2

出力例 2

入力例 3

20 77
9 16 65551022 36847141
4 8 169905126 234841269
8 18 61782163 101070315
8 9 763292109 656192270
1 18 76893781 240632078
3 19 601597138 476288881
5 19 595403102 581080612
3 6 980642190 183697163
6 9 663706146 95151932
11 18 679581087 523262198
12 16 293035618 152800086
3 7 814717585 273291118
1 2 853500661 870996856
2 3 526446904 394372085
2 9 75096934 115522990
4 9 599545324 421351001
1 13 282807719 968765138
6 15 458441410 364130005
1 4 178858403 334122865
4 4 242708006 509603317
8 13 368467895 338762793
13 17 697663167 640858525
11 20 238453071 271106570
2 17 126970225 114980011
14 18 279244522 277866206
11 20 238453071 271106570
5 20 714162258 622887639
4 12 694170286 610998228
9 16 65551022 36847141
15 15 341887831 393369008
3 8 311942139 377343175
1 8 15111618 99281596
2 4 674642258 536873991
2 16 9545912 78675849
1 8 15111618 99281596
12 20 121899250 49599586
14 20 638789636 516502562
5 17 699705205 614143827
7 13 480049964 311871500
9 14 422265424 394103067
7 10 230695689 160298785
2 20 141427278 488804437
9 16 65551022 36847141
2 4 746378429 794786225
1 13 684196511 438044389
9 19 97765056 384638724
8 14 599920464 622509237
16 20 446862361 693104823
2 20 141427278 250722614
17 18 964998636 785624956
11 20 238453071 271106570
1 3 327053757 476624771
1 5 327955959 908911545
3 11 429421111 769824924
7 19 113311100 202997763
13 18 205913938 237692478
1 17 980470886 985976867
3 12 545974932 468496322
6 19 312631863 292591718
11 15 651379358 427422180
3 8 311942139 377343175
8 17 965359268 886695271
3 20 667874182 518095908
12 17 107442197 40855774
2 10 321338667 306331990
4 13 103949316 103921524
9 10 246241733 165856762
7 14 406719380 271697772
7 8 747746065 755010172
1 9 778403727 755473866
8 17 965359268 886695271
5 11 475709187 351781069
8 11 751809642 869885243
5 19 595403102 581080612
19 20 118759156 41807027
3 19 646592547 476288881
3 12 850613737 468496322

出力例 3

F - イーハチはやる

実行時間制限: 3 sec / メモリ制限: 1024 MiB

配点: 100 点

問題文

Pakenomy 社は N 個の部屋と N-1 本の廊下から成り，部屋は 1 から N の，廊下は 1 から N-1 の番号がついています．廊下 i は部屋 A_i と部屋 B_i を双方向に結んでいます．廊下を何本か通ることで任意の 2 部屋の間を移動できるようになっています．

Pakenomy 社では多くの怪物を管理しており，緊急事態が起こるとそれらが廊下に侵入することが想定されます．イーハチはこのような状況において騒動の鎮圧を担当する職員ですが，前もって振る舞いを調べようと考えています．

イーハチが廊下 e を通るとき，体力が C_e 減ります．ここで体力が 0 以下になった場合，「蘇生」イベントが起き，体力が K になります．

Q 個の質問が与えられ，i 番目の質問は以下の通りです．

イーハチがはじめ体力 K の状態で部屋 S_i にいて，廊下を何回か通って部屋 T_i に移動するとき，「蘇生」イベントが起こる回数は最小で何回か？

あなたの仕事は，Q 個の質問全てに答えることです．

制約

入力はすべて整数
2 \leq N \leq 2 \times 10^5
1 \leq K \leq 10^9
1 \leq A_i, B_i \leq N\ (1 \leq i \leq N-1)
廊下を何本か通ることで任意の 2 部屋の間を移動できる
0 \leq C_i \leq 10^9\ (1 \leq i \leq N-1)
1 \leq Q \leq 2 \times 10^5
1 \leq S_i, T_i \leq N\ (1 \leq i \leq Q)
S_i \neq T_i\ (1 \leq i \leq Q)

部分点

この問題はいくつかの小課題に分けられ，その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます．

提出したソースコードの得点は，正解した小課題の点数の合計となります．

(5 点) N=2, Q=1 を満たす．
(18 点) N \leq 4000, Q \leq 4000 を満たす．
(12 点) N \leq 4000 を満たす．
(33 点) 任意の i\ (1 \leq i \leq N-1) について，A_i=i および B_i=i+1 を満たす．
(32 点) 追加の制約はない．

入力

入力は以下の形式で標準入力から与えられます．

N K
A_1 B_1 C_1
:
A_{N-1} B_{N-1} C_{N-1}
Q
S_1 T_1
:
S_Q T_Q

出力

Q 行出力してください．i 行目には，i 番目の質問に対する答えを出力してください．

入力例 1

出力例 1

2
1
0

部屋 3 から部屋 6 に向かうとき，体力は次のように変動します．

廊下 2 を通って体力が 5 - 10 = -5 になり，「蘇生」イベントにより体力が 5 になる．
廊下 1 を通って体力が 5 - 3 = 2 になる．
廊下 5 を通って体力が 2 - 2 = 0 になり，「蘇生」イベントにより体力が 5 になる．

部屋 4 から部屋 7 に向かうとき，体力は次のように変動します．

廊下 3 を通って体力が 5 - 3 = 2 になる．
廊下 1 を通って体力が 2 - 3 = -1 になり，「蘇生」イベントにより体力が 5 になる．
廊下 4 を通って体力が 5 - 1 = 4 になる．
廊下 6 を通って体力が 4 - 1 = 3 になる．

部屋 7 から部屋 6 に向かうとき，体力は次のように変動します．

廊下 6 を通って体力が 5 - 1 = 4 になる．
廊下 4 を通って体力が 4 - 1 = 3 になる．
廊下 5 を通って体力が 3 - 2 = 1 になる．

入力例 2

7 5
1 2 30843382
1 3 31046102
1 4 31236232
2 5 31487860
2 6 32171282
5 7 33077326
3
3 6
4 7
7 6

出力例 2

3
4
3

廊下を通るたびに蘇生することになります．

入力例 3

出力例 3

G - 三つの条件

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点: 100 点

問題文

僕は，寿司が好きです．

ところで，整数 X は n 桁の a 進数です．最も上の桁が 0 となることもあり得ます．
また，F(X) は X の a 進数表記での桁和を 10 進数で表したものとします．例えば，a = 7, X = 562 の場合，F(X) = 13 です．

さて，次の 3 つの条件を同時に満たすような X として考えられる整数を，小さい順から K 個出力してください．

F(X) = m．
X' \ mod \ p = t．(ただし，X' は X を 10 進数に直した整数)
s_i = 0 であるような全ての整数 i (1 \leq i \leq n) について，整数 X の a^{n-i} の位は 0 である．
- 例えば，n = 7，a = 10，s = 1110110 の場合，X の 1000 の位と 1 の位は 0 でなければならない．

ただし，そのような整数が K 個未満しか存在しない場合，条件を満たす整数を小さい順にすべて出力した後，最後に -1 と出力してください．

出力形式について，詳しくは「出力」の項をご覧ください．

制約

1 \leq n \leq 100．
2 \leq a \leq 1 \ 000 \ 000．
0 \leq m \leq 600．
2 \leq p \leq 600．
0 \leq t < p．
1 \leq K \leq 2 \ 000．
s_i は 0 または 1．
n, a, m, p, t, K は 10 進数で表記された整数である．

部分点

(7 点) m = 1．
(8 点) n \leq 6，a \leq 10．
(24 点) n \leq 32，a = 2．
(29 点) n \leq 50，a \leq 10，m \leq 50，p \leq 50．
(23 点) a \geq m．
(9 点) 追加の制約はない．

入力

入力は以下の形式で標準入力から与えられます．

n a m p t K
s_1s_2s_3s_4...s_n

出力

条件を満たす整数が K 個以上ある場合は，以下の形式で出力してください．

(小さい方から 1 番目の整数の情報)
(小さい方から 2 番目の整数の情報)
(小さい方から 3 番目の整数の情報)
:
(小さい方から K 番目の整数の情報)

また，条件を満たす整数が K 個に満たない場合は，以下の形式で出力してください．（ここでは，条件を満たす整数の個数を K' としています．）

(小さい方から 1 番目の整数の情報)
(小さい方から 2 番目の整数の情報)
(小さい方から 3 番目の整数の情報)
:
(小さい方から K' 番目の整数の情報)
-1

ただし，整数の情報は，出力するべき整数が g_{n-1}a^{n-1}+g_{n-2}a^{n-2}+...+g_0a^0 (0 \leq g_i \leq a-1) で表されるとき，以下の形式で一行に出力して下さい．

g_{n-1} g_{n-2} g_{n-3} ... g_{0}

入力例 1

3 10 1 5 0 2
111

出力例 1

0 1 0
1 0 0

条件を満たす整数は，10, 100 しかありません．
10 は 2 桁の整数ですが，最も上の桁が 0 となってもよいので，010 と見なせば条件を満たします．なお，この入力例は小課題 1 の制約を満たします．

入力例 2

6 10 26 241 74 25
111110

出力例 2

0 6 6 5 9 0
0 8 8 2 8 0
1 0 9 9 7 0
1 9 6 7 3 0
2 8 3 4 9 0
3 2 6 8 7 0
3 4 8 5 6 0
3 9 1 9 4 0
4 7 8 7 0 0
5 4 3 7 7 0
5 6 5 4 6 0
5 8 7 1 5 0
6 0 8 8 4 0
6 7 3 9 1 0
6 9 5 6 0 0
7 1 7 2 9 0
7 6 0 6 7 0
7 8 2 3 6 0
8 2 5 7 4 0
8 4 7 4 3 0
8 6 9 1 2 0
8 9 0 8 1 0
9 3 4 1 9 0
-1

この入力例において，条件を満たす整数は 23 個しか存在しません．
K=25 個より少ないので，最後の行に -1 を出力すると正解になります．

入力例 3

3 2 3 7 0 2000
111

出力例 3

1 1 1
-1

入力例 4

40 23 166 240 130 1117
1000000000100000000010000000001000000000

出力例 4

-1

条件を満たす整数が 0 通りの場合もあります．

H - 板の重なり

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点: 100 点

問題文

N 枚の板があり，それぞれ板 1，板 2，...，板 N と番号づけられております．

板 i の長さは L_i センチメートルであり，左から数えて，j-1 センチメートルから j センチメートルまでの区間は，色 S_{i, j} で塗られております．S_{i, j} = 0 のとき透明，S_{i, j} = 1 のとき赤です．

さて，あなたは N 枚の板を適当な位置に置き，重ねることができます．
「i 枚目の板は，左端が原点から m_i センチメートルの位置に来るように置く」とするとき，各板について，m_i は 0 以上 10 \ 000 以下の整数で決めることができます．

重なっている板を上から見ると，板の赤い部分が 1 枚以上重なっている部分は，赤く見えます．
上から見たときの，連続する「赤く見える部分」の長さの最大が，できるだけ大きくなるような置き方を，一つ求めてください．ただし，最適なものを求める必要はありません．

制約

N = 300．
31 \leq L_i \leq 62．
S_{i, j} は 0 または 1．

テストケース生成について

テストケースは，以下のステップに基づいて生成されます．

L_i の値を，31 以上 62 以下の整数の中から，一様ランダムに選ぶ．
B を，0.15 以上 0.55 以下の一様な確率分布に基づいて決定された，ランダムな値とする．
各 j (1 \leq j \leq L_i) について独立に S_{i, j} の値が決められる．確率 B で S_{i, j} = \ 1 となり，確率 1-B で S_{i, j} = \ 0 となる．(23:11 訂正)
得られた S_{i, 1}, S_{i, 2}, S_{i, 3}, ..., S_{i, L_i} が全部 0 の場合は，ステップ 1. からやり直す．

得点

提出に対する得点は，以下のように決定されます．

採点に使われる 10 個のテストケースのうち，1 つでも条件を満たさない出力（0 \leq m_i \leq 10 \ 000 を満たさない，不正な出力フォーマットなど）があれば，0 点となります．
そうでない場合，i 個目のテストケースの得点を a_i 点とするとき，提出に対する得点は \frac{a_{1}+a_{2}+a_{3}+...+a_{10}}{10} 点を小数点以下切り捨てた値となります．

なお，各テストケースに対する得点は，以下のようになります．（100 点を超える場合があります．）ただし，連続する「赤く見える部分」の長さの最大を D とします．

D \leq 199 のとき，5 点．
200 \leq D \leq 4 \ 209 のとき，100 - 30log_2(\frac{4810 - D}{600}) 点を小数点以下切り捨てた得点．
4 \ 210 \leq D のとき，100 + \frac{D - 4 \ 210}{10} 点．

入力

入力は以下の形式で標準入力から与えられます．

N
s_{1,1}s_{1,2}s_{1,3}...s_{1,L_{1}}
s_{2,1}s_{2,2}s_{2,3}...s_{2,L_{2}}
s_{3,1}s_{3,2}s_{3,3}...s_{3,L_{3}}
:
s_{N,1}s_{N,2}s_{N,3}...s_{N,L_{N}}

出力

以下の形式で出力してください．

m_1
m_2
m_3
:
m_N

ただし，m_i は 0 以上 10 \ 000 以下の整数でなければなりません．

入出力例

例えば，以下の入力例を考えましょう．(N, L_i が制約の条件を満たさないため，採点に用いられるデータには含まれません．)

出力例 1

4
7
3

この出力に対応する図は，以下のようになります．

左から数えて，7 センチメートルから 10 センチメートルまでの，長さ 3 センチメートルの区間が，連続して赤く見えます．また，これが最大の長さです．そのため，この出力をした場合のスコアは 5 点となります．

なお，この入力例は，N = 300，31 \leq L_i \leq 62 の条件を満たさないため，テストデータには含まれません．
採点に用いられるすべてのテストケースは，N = 300，31 \leq L_i \leq 62 を満たします．