競技プログラミングの鉄則　演習問題集

A01 - The First Problem

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

整数 N が与えられるので、一辺の長さが N であるような正方形の面積を出力するプログラムを作成してください。

制約

N は 1 以上 100 以下の整数

入力

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

出力

正方形の面積を整数で出力してください。

入力例 1

出力例 1

一辺の長さが 2 である正方形の面積は 2 \times 2 = 4 です。

入力例 2

出力例 2

一辺の長さが 8 である正方形の面積は 8 \times 8 = 64 です。

入力例 3

出力例 3

一辺の長さが 100 である正方形の面積は 100 \times 100 = 10000 です。

A02 - Linear Search

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

N 個の整数 A_1, A_2, \cdots, A_N の中に、整数 X が含まれるかどうかを判定するプログラムを作成してください。

制約

N は 1 以上 100 以下の整数
X は 1 以上 100 以下の整数
A_1, A_2, \cdots, A_N は 1 以上 100 以下の整数

入力

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

N X
A_1 A_2 \cdots A_N

出力

整数 X が含まれるとき Yes、含まれないとき No と出力してください。

入力例 1

5 40
10 20 30 40 50

出力例 1

Yes

この入力例では、N=5, X=40, (A_1, A_2, A_3, A_4, A_5) = (10, 20, 30, 40, 50) となっています。
A_4 の値が X と一致するため、Yes と出力すれば正解です。

入力例 2

6 28
30 10 40 10 50 90

出力例 2

No

整数 30, 10, 40, 10, 50, 90 の中に X=28 は含まれないので、No と出力すれば正解です。

A03 - Two Cards

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

赤いカードが N 枚あり、それぞれ整数 P_1, P_2, \cdots, P_N が書かれています。
また、青いカードが N 枚あり、それぞれ整数 Q_1, Q_2, \cdots, Q_N が書かれています。

太郎君は、赤いカードの中から 1 枚、青いカードの中から 1 枚、合計 2 枚のカードを選びます。
選んだ 2 枚のカードに書かれた整数の合計が K となるようにする方法は存在しますか。

制約

N は 1 以上 100 以下の整数
K は 1 以上 100 以下の整数
P_1, P_2, \cdots, P_N は 1 以上 100 以下の整数
Q_1, Q_2, \cdots, Q_N は 1 以上 100 以下の整数

入力

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

N K
P_1 P_2 \cdots P_N
Q_1 Q_2 \cdots Q_N

出力

合計を K にする方法が存在するとき Yes、そうでないとき No を出力してください。

入力例 1

3 100
17 57 99
10 36 53

出力例 1

No

この入力例では、3 枚の赤いカードと 3 枚の青いカードがあります。

赤いカードにはそれぞれ 17, 57, 99 が書かれています。
青いカードにはそれぞれ 10, 36, 53 が書かれています。

各色のカードを 1 枚ずつ選び、合計を K=100 にする方法は存在しないので、No が正解です。

入力例 2

5 53
10 20 30 40 50
1 2 3 4 5

出力例 2

Yes

50 と書かれた赤いカードと、3 と書かれた青いカードを選べば良いです。

A04 - Binary Representation 1

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

整数 N が 10 進法表記で与えられます。
N を 2 進法に変換した値を出力するプログラムを作成してください。

制約

N は 1 以上 1000 以下の整数

入力

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

出力

N を 2 進法に変換した値を、10 桁で出力してください。
桁数が足りない場合は、左側を 0 で埋めてください。

入力例 1

出力例 1

0000001101

13 を 2 進法に変換した値は 1101 ですので、左側に 0 を付けて 10 桁にした 0000001101 を出力すれば正解となります。

入力例 2

出力例 2

0000100101

37 を 2 進法に変換した値は 100101 ですので、左側に 0 を付けて 10 桁にした 0000100101 を出力すれば正解となります。

入力例 3

出力例 3

1111101000

A05 - Three Cards

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

赤・青・白の 3 枚のカードがあります。
太郎君は、それぞれのカードに 1 以上 N 以下の整数を書かなければなりません。
3 枚のカードの合計を K にするような書き方は何通りありますか。

制約

N は 1 以上 3000 以下の整数
K は 3 以上 9000 以下の整数

入力

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

N K

出力

答えを整数で出力してください。

入力例 1

3 6

出力例 1

合計を 6 にする書き方として、以下の 7 通りが考えられます。

(赤, 青, 白) = (1, 2, 3)
(赤, 青, 白) = (1, 3, 2)
(赤, 青, 白) = (2, 1, 3)
(赤, 青, 白) = (2, 2, 2)
(赤, 青, 白) = (2, 3, 1)
(赤, 青, 白) = (3, 1, 2)
(赤, 青, 白) = (3, 2, 1)

入力例 2

3000 4000

出力例 2

A06 - How Many Guests?

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

遊園地「ALGO-RESORT」では N 日間にわたるイベントが開催され、 i 日目 (1 \leq i \leq N) には A_i 人が来場しました。

以下の合計 Q 個の質問に答えるプログラムを作成してください。

1 個目の質問：L_1 日目から R_1 日目までの合計来場者数は？
2 個目の質問：L_2 日目から R_2 日目までの合計来場者数は？
:
Q 個目の質問：L_Q 日目から R_Q 日目までの合計来場者数は？

制約

1 \le N,Q \le 10^5
1 \le A_i \le 10000
1 \le L_i \le R_i \le N
入力はすべて整数

入力

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

N Q
A_1 A_2 \cdots A_N
L_1 R_1
L_2 R_2
 :
L_Q R_Q

出力

全体で Q 行出力してください。

i 行目 (1 \leq i \leq Q) には、i 個目の質問への答えを整数で出力してください。

入力例 1

10 5
8 6 9 1 2 1 10 100 1000 10000
2 3
1 4
3 9
6 8
1 10

出力例 1

この入力には 5 個の質問が含まれています。

1 個目の質問は 2 日目から 3 日目までの合計来場者数を尋ねるもので、これに対する答えは 6+9=15 です。
2 個目の質問は 1 日目から 4 日目までの合計来場者数を尋ねるもので、これに対する答えは 8+6+9+1=24 です。

A07 - Event Attendance

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

ある会社では D 日間にわたってイベントが開催され，N 人が出席します．参加者 i は L_i 日目から R_i 日目まで出席する予定です．各日の出席者数を出力するプログラムを作成してください．

制約

1\leq D,N\leq 10^5
1\leq L_i\leq R_i\leq D
入力はすべて整数

入力

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

D
N
L_1 R_1
\vdots
L_N R_N

出力

D 行にわたって出力してください．d 行目には，d 日目の出席者数を出力してください．

入力例 1

出力例 1

A08 - Two Dimensional Sum

Time Limit: 10 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

H\times W のマス目があります．上から i 行目，左から j 列目にあるマス (i, j) には，整数 X_{i, j} が書かれています．これについて，以下の Q 個の質問に答えるプログラムを作成してください．

i 個目の質問：左上 (A_i, B_i) 右下 (C_i, D_i) の長方形領域に書かれた整数の総和は？

制約

1\leq H,W\leq 1500
1\leq Q\leq 100000
0\leq X_{i,j}\leq 9
1\leq A_i\leq C_i\leq H
1\leq B_i\leq D_i\leq W
入力はすべて整数

入力

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

H W
X_{1, 1} X_{1, 2} \cdots X_{1, W}
\vdots
X_{H, 1} X_{H, 2} \cdots X_{H, W}
Q
A_1 B_1 C_1 D_1
\vdots
A_Q B_Q C_Q D_Q

出力

Q 行にわたって出力してください．i 行目には，質問 i の答えを出力してください．

入力例 1

出力例 1

25
56

A09 - Winter in ALGO Kingdom

Time Limit: 10 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

ALGO 王国は H\times W のマス目で表されます．最初は，どのマスにも雪が積もっていませんが，これから N 日間にわたって雪が降り続けます．

上から i 行目，左から j 列目のマスを (i, j) とするとき，t 日目には「マス (A_t, B_t) を左上とし，マス (C_t, D_t) を右下とする長方形領域」の積雪が 1cm だけ増加することが予想されています．最終的な各マスの積雪を出力するプログラムを作成してください．

制約

1\leq H,W\leq 1500
1\leq N\leq 100000
1\leq A_i\leq C_i\leq H
1\leq B_i\leq D_i\leq W
入力はすべて整数

入力

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

H W N
A_1 B_1 C_1 D_1
A_2 B_2 C_2 D_2
\vdots
A_N B_N C_N D_N

出力

マス (i, j) の最終的な積雪を Z_{i, j} とするとき，以下の形式で出力してください．

Z_{1, 1} Z_{1, 2} \cdots Z_{1, W}
\vdots
Z_{H, 1} Z_{H, 2} \cdots Z_{H, W}

入力例 1

5 5 2
1 1 3 3
2 2 4 4

出力例 1

A10 - Resort Hotel

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

あるリゾートホテルには，1 号室から N 号室までの N 個の部屋があります． i 号室は A_i 人部屋です．このホテルでは D 日間にわたって工事が行われることになっており， d 日目は L_d 号室から R_d 号室までの範囲を使うことができません． d=1,2,\cdots D について，d 日目に使える中で最も大きい部屋は何人部屋であるか，出力するプログラムを作成してください．

制約

3\leq N\leq 100000
1\leq D\leq 100000
1\leq A_i\leq 100
2\leq L_i\leq R_i\leq N - 1
入力はすべて整数

入力

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

N
A_1 A_2 \cdots A_N
D
L_1 R_1
\vdots
L_D R_D

出力

D 行にわたって出力してください．d 行目には，d 日目に使える中で最も大きい部屋は何人部屋であるかを出力してください．

入力例 1

7
1 2 5 5 2 3 1
2
3 5
4 6

出力例 1

3
5

A11 - Binary Search 1

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

小さい順に並べられている、要素数 N の配列 A = [A_1, A_2, \cdots, A_N] があります。要素 X は配列 A の何番目に存在するかを出力してください。

なお、この問題は単純な全探索（→1.2節）でも解けますが、ここでは二分探索法を使って実装してください。

制約

1 \leq N \leq 100000
1 \leq A_1 < A_2 < \cdots < A_N \leq 10^9
整数 X は A_1, A_2, \ldots, A_N のいずれかである

入力

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

N X
A_1 A_2 \cdots A_N

出力

要素 X は配列 A の何番目に存在するかを出力してください。

入力例 1

15 47
11 13 17 19 23 29 31 37 41 43 47 53 59 61 67

出力例 1

A_{11} の値が 47 になっています。

入力例 2

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

出力例 2

A12 - Printer

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

N 台のプリンターがあり、1 から N までの番号が付けられています。プリンター i は A_i 秒ごとにチラシを 1 枚印刷します。すなわち、スイッチを入れてから A_i 秒後、2A_i 秒後、3A_i 秒後･･･に印刷します。すべてのプリンターのスイッチを同時に入れたとき、K 枚目のチラシが印刷されるのは何秒後でしょうか。

制約

1 \leq N \leq 100\,000
1 \leq K \leq 10^9
1 \leq A_i \leq 10^9
答えは 10^9 を超えない
入力はすべて整数

入力

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

N　K
A_1　A_2　\cdots　A_N

出力

何秒後に K 枚目のチラシが印刷されるかを一行で出力してください。

入力例 1

4 10
1 2 3 4

出力例 1

A13 - Close Pairs

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

N 個の整数が黒板に書かれています。書かれた整数は小さい順に A_1, A_2, \cdots, A_N です。異なる 2 つの整数のペアを選ぶ方法は全部で N(N-1)/2 通りありますが、その中で差が K 以下であるような選び方は何通りありますか。

制約

1 \leq N \leq 100\,000
1 \leq K \leq 10^9
1 \leq A_1 < A_2 < \cdots < A_N \leq 10^9
入力はすべて整数

入力

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

N K
A_1 A_2 \cdots A_N

出力

差が K 以下である整数のペアの選び方を一行に出力してください。

入力例 1

7 10
11 12 16 22 27 28 31

出力例 1

A14 - Four Boxes

Time Limit: 5 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

A・B・C・D の 4 つの箱があります。各箱には、以下の N 枚のカードが入っています。

箱 A には整数 A_1, A_2, \cdots, A_N が書かれたカードがある。
箱 B には整数 B_1, B_2, \cdots, B_N が書かれたカードがある。
箱 C には整数 C_1, C_2, \cdots, C_N が書かれたカードがある。
箱 D には整数 D_1, D_2, \cdots, D_N が書かれたカードがある。

あなたはそれぞれの箱から 1 枚ずつカードを取り出します。取り出した 4 枚のカードに書かれた整数の合計が K となる可能性はあるか、判定してください。

制約

1 \leq N \leq 1\,000
1 \leq K \leq 10^8
1 \leq A_x, B_y, C_z, D_w \leq 10^8

入力

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

N　K
A_1　A_2　\cdots　A_N
B_1　B_2　\cdots　B_N
C_1　C_2　\cdots　C_N
D_1　D_2　\cdots　D_N

出力

合計が K となる可能性がある場合 Yes、そうでない場合 No を出力してください。

入力例 1

出力例 1

Yes

A15 - Compression

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

配列 A = [A_1, A_2, \cdots, A_N] が与えられます。大小関係を崩さないように、配列をできるだけ圧縮してください。

ここで圧縮とは、以下の条件をすべて満たす配列 B = [B_1, B_2, \cdots, B_N] を求める操作です。なお、このような配列 B は 1 通りに決まります。

条件1　B_1, B_2, \cdots, B_N は 1 以上の整数である。
条件2　A_i < A_j であるような組 (i, j) については、B_i < B_j である。
条件3　A_i = A_j であるような組 (i, j) については、B_i = B_j である。
条件4　A_i > A_j であるような組 (i, j) については、B_i > B_j である。
条件5　条件 1～4 を満たす中で、配列 B の最大値をできるだけ小さくする。

制約

1 \leq N \leq 100\,000
1 \leq A_i \leq 10^9

入力

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

N
A_1　A_2　\cdots　A_N

出力

整数 B_1, B_2, \cdots, B_N を空白区切りで出力してください。

入力例 1

5
46 80 11 77 46

出力例 1

2 4 1 3 2

A = [46, 80, 11, 77, 46] の大小関係を崩さずに圧縮すると、B = [2, 4, 1, 3, 2] になります。

A16 - Dungeon 1（※初版第 1 刷の B22 も同じ問題です）

Time Limit: 1 sec / Memory Limit: 1024 MB

配点 : 1000 点

注意

書籍の版によっては、書籍内の入力例が正しくない場合があります。正誤表を参照してください。

問題文

あるダンジョンには N 個の部屋があり、1 から N までの番号が付けられています。このダンジョンは一方通行であり、通路を介して 1 つ先または 2 つ先の部屋に移動することができます。各通路における移動時間は以下の通りです。

部屋 i - 1 から部屋 i に向かう通路を通るのに A_i 分 (2 ≤ i ≤ N) かかる。
部屋 i - 2 から部屋 i に向かう通路を通るのに B_i 分 (3 ≤ i ≤ N) かかる。

太郎君が部屋 1 から部屋 N に移動するのに、最短何分かかりますか。答えを求めるプログラムを作成してください。

制約

3 ≤ N ≤ 100\,000
1 ≤ A_i ≤ 100 (2 ≤ i ≤ N)
1 ≤ B_i ≤ 100 (3 ≤ i ≤ N)
入力される値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

N
A_2 A_3 A_4 \cdots A_N
B_3 B_4 \cdots B_N

出力

答えを整数で出力してください。

入力例 1

5
2 4 1 3
5 3 7

出力例 1

入力例 2

10
1 19 75 37 17 16 33 18 22
41 28 89 74 98 43 42 31

出力例 2

A17 - Dungeon 2

Time Limit: 1 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

部屋 i - 1 から部屋 i に向かう通路を通るのに A_i 分 (2 ≤ i ≤ N) かかる。
部屋 i - 2 から部屋 i に向かう通路を通るのに B_i 分 (3 ≤ i ≤ N) かかる。

太郎君が部屋 1 から部屋 N へ最短時間で移動する方法を 1 つ出力するプログラムを作成してください。

制約

3 ≤ N ≤ 100\,000
1 ≤ A_i ≤ 100 (2 ≤ i ≤ N)
1 ≤ B_i ≤ 100 (3 ≤ i ≤ N)
入力される値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

N
A_2 A_3 A_4 \cdots A_N
B_3 B_4 \cdots B_N

出力

部屋 P_1 → 部屋 P_2 → ･･･ → 部屋 P_K という経路で移動する場合、以下の形式で出力してください。特に、P_1=1、P_K=N でなければならないことに注意してください（詳しくは入出力例へ）。

K
P_1 P_2 \cdots P_K

入力例 1

5
2 4 1 3
5 3 3

出力例 1

4
1 2 4 5

部屋 1 \to 2 \to 4 \to 5 という経路や、部屋 1 \to 3 \to 5 という経路を通ると、8 分でゴールにたどり着けます。

入力例 2

10
1 19 75 37 17 16 33 18 22
41 28 89 74 98 43 42 31

出力例 2

7
1 2 4 5 6 8 10

A18 - Subset Sum

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

N 枚のカードが一列に並べられており、左から i 番目のカード（以下、カード i とする）には整数 A_i が書かれています。

カードの中からいくつかを選んで、書かれた整数の合計が S となるようにする方法は存在しますか。

制約

1 \leq N \leq 60
1 \leq S \leq 10000
1 \leq A_i \leq 10000
入力はすべて整数

部分点

1 \leq N \leq 20 を満たすケースで正解すると、500 点を獲得することができます。

入力

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

N S
A_1 A_2 \cdots A_N

出力

書かれた整数の合計が S となるようなカードの選び方が存在すれば Yes、そうでなければ No と出力してください。

入力例 1

3 7
2 2 3

出力例 1

Yes

たとえばカード 1・カード 2・カード 3 を選んだ場合、書かれた整数の合計は 2+2+3=7 となります。したがって、Yes と出力すれば正解です。

入力例 2

4 11
3 1 4 5

出力例 2

No

A19 - Knapsack 1

Time Limit: 10 sec / Memory Limit: 1024 MB

配点: 1000 点

この問題は、Educational DP Contest D - Knapsack 1 と同じ問題です。

問題文

宝箱には N 個の品物が入っており、それぞれ 1 から N までの番号が付けられています。
品物 i の重さは w_i であり、価値は v_i です。

太郎君は、いくつかの品物を選んで持ち帰りたいと考えています。
しかし、彼のナップザックには容量制限があるので、重さの合計が W 以下になるようにする必要があります。
価値の合計としてあり得る最大の値はいくつですか。

制約

1 \leq N \leq 100
1 \leq W \leq 100000
1 \leq w_i \leq W
1 \leq v_i \leq 10^9
入力はすべて整数

入力

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

N W
w_1 v_1
w_2 v_2
 :
w_N v_N

出力

答えを整数で出力してください。

入力例 1

出力例 1

たとえば品物 1・品物 2・品物 4 を選んだ場合、価値の合計は 13+17+10=40 となります。
価値の合計を 41 以上にする方法は存在しません。

入力例 2

出力例 2

すべての品物を選ぶことができます。

入力例 3

出力例 3

A20 - LCS

Time Limit: 10 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

文字列 S と T が与えられます。
S と T の共通部分列（S の部分列かつ T の部分列）のうち、最長のものは何文字かを出力するプログラムを作成してください。

ただし、ある文字列の 部分列 とは、その文字列から順番を変えずに一部の文字を取り出したものを指します。
たとえば grain は programming の部分列です（4, 5, 6, 9, 10 文字目を取り出す）。

制約

S の文字数は 1 以上 2000 以下
T の文字数は 1 以上 2000 以下
S, T は英小文字からなる

入力

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

S
T

出力

最長の共通部分列は何文字か、整数で出力してください。

入力例 1

mynavi
monday

出力例 1

3 文字の文字列 mna は、mynavi と monday 両方の部分列となっています。

入力例 2

tokyo
kyoto

出力例 2

A21 - Block Game

Time Limit: 10 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

N 個のブロックが並べられており、左から順に 1, 2, \cdots, N と番号が付けられています。
あなたは、以下の 2 種類の操作を何回か行うことで、すべてのブロックを取り除きたいです。

今ある中で 一番左 のブロックを取り除く。
今ある中で 一番右 のブロックを取り除く。

ブロック i (i = 1, 2, \cdots, N) をブロック P_i より先に取り除いた場合、A_i 点が得られます。
合計得点としてあり得る最大値を出力するプログラムを作成してください。

制約

2 \leq N \leq 2000
1 \leq P_i \leq N
P_i \neq i
1 \leq A_i \leq 100
入力はすべて整数

入力

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

N
P_1 A_1
P_2 A_2
 \cdots
P_N A_N

出力

合計得点の最大値を、整数で出力してください。

入力例 1

出力例 1

ブロック 1 \to ブロック 4 \to ブロック 3 \to ブロック 2 の順番に取り除けば良いです。

入力例 2

出力例 2

A22 - Sugoroku

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

注意

書籍の版によっては、書籍内のコードが正しくない場合があります。正誤表を参照してください。

問題文

ある双六には N 個のマスがあり、スタートから順に 1 から N までの番号が付けられています。
この双六では、あなたがマス i (i = 1, 2, \cdots, N-1) にいるとき、以下の 2 種類の行動のうち一方を選ぶことができます。

マス A_i に進み、スコア 100 を得る
マス B_i に進み、スコア 150 を得る

ゴールにたどり着くまでに得られる合計スコアの最大値を出力するプログラムを作成してください。

制約

2 \leq N \leq 100000
i+1 \leq A_i \leq B_i \leq N
入力はすべて整数

入力

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

N
A_1 A_2 \cdots A_{N-1}
B_1 B_2 \cdots B_{N-1}

出力

ゴールにたどり着くまでに得られるスコアの最大値を、整数で出力してください。

入力例 1

7
2 4 4 7 6 7
3 5 6 7 7 7

出力例 1

以下のように移動すれば、合計スコア 100 + 150 + 100 + 150 = 500 を得ることができます。

マス 1 からマス 2 に移動する。スコア 100 を得る。
マス 2 からマス 5 に移動する。スコア 150 を得る。
マス 5 からマス 6 に移動する。スコア 100 を得る。
マス 6 からマス 7 に移動する。スコア 150 を得る。

入力例 2

2
2
2

出力例 2

A23 - All Free

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

注意

書籍の版によっては、書籍内のコードが正しくない場合があります。正誤表を参照してください。

問題文

情報商店では N 種類の品物を扱っています。それぞれ 1 から N までの番号が付けられています。
この店では、いくつかの指定された品物を無料で買えるクーポン券が配布されています。

太郎君は M 枚のクーポン券を持っています。
クーポン券 i (i = 1, 2, \cdots, M) の情報は以下の通りです。

A_{i, j} = 1 のとき：品物 j は無料で買える対象に含まれている。
A_{i, j} = 0 のとき：品物 j は無料で買える対象に含まれていない。

最小何枚のクーポン券を使うことで、N 種類すべての品物を買うことができますか。

制約

1 \leq N \leq 10
1 \leq M \leq 100
0 \leq A_{i, j} \leq 1
入力はすべて整数

入力

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

N M
A_{1,1} A_{1,2} \cdots A_{1,N}
A_{2,1} A_{2,2} \cdots A_{2,N}
 :
A_{M,1} A_{M,2} \cdots A_{M,N}

出力

必要なクーポン券の最小枚数を出力してください。
ただし、N 種類すべての品物を無料で買う方法が存在しない場合、代わりに -1 を出力してください。

入力例 1

出力例 1

クーポン券 1, 4 を使うのが最適です。

入力例 2

10 2
1 1 1 1 0 0 0 0 0 0
0 0 0 0 1 1 1 1 0 0

出力例 2

-1

すべてのクーポン券を使っても、全品物を無料で買うことはできません。

A24 - LIS

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

配列 A = [A_1, A_2, \cdots, A_N] の最長増加部分列の長さを求めてください。

制約

1 \leq N \leq 100000
1 \leq A_i \leq 500000
入力はすべて整数

入力

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

N
A_1 A_2 \cdots A_N

出力

答えを整数で出力してください。

入力例 1

6
2 3 1 6 4 5

出力例 1

列 [2, 3, 4, 5] が最長増加部分列です。

入力例 2

10
1 1 1 1 1 1 1 1 1 1

出力例 2

A25 - Number of Routes

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

縦 H 行、横 W 列のマス目があります。
上から i 行目・左から j 列目のマス (i, j) は色 c_{i, j} で塗られています。
ここで c_{i, j} が . ならば白、c_{i, j} が # ならば黒を意味します。

マス (1, 1) から出発し、右方向または下方向の移動のみを繰り返して、マス (H, W) まで行く方法は何通りありますか。
ただし、黒いマスを通ることはできないものとします。

制約

2 \leq H \leq 30
2 \leq W \leq 30
c_{i, j} は . または # である
c_{1, 1} は . である
c_{H, W} は . である

入力

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

H W
c_{1,1}c_{1,2}\cdotsc_{1,W}
c_{2,1}c_{2,2}\cdotsc_{2,W}
 :
c_{H,1}c_{H,2}\cdotsc_{H,W}

出力

何通りの移動方法があるか、整数で出力してください。

入力例 1

4 8
.....#..
........
..#...#.
#.......

出力例 1

入力例 2

2 8
....#...
....#...

出力例 2

入力例 3

30 30
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................

出力例 3

30067266499541040

A26 - Prime Check

Time Limit: 1 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

以下の Q 個の質問に答えるプログラムを作成してください。

質問 1 ：整数 X_1 は素数ですか？
質問 2 ：整数 X_2 は素数ですか？
質問 3 ：整数 X_3 は素数ですか？
\dots
質問 Q ：整数 X_Q は素数ですか？

制約

入力は全て整数
1 \le Q \le 10000
2 \le X_i \le 300000

入力

入力は以下の形式で標準入力から与えられる。

Q
X_1
\vdots
X_Q

出力

Q 行にわたって出力してください。
i 行目には、整数 X_i が素数であれば Yes 、合成数（素数ではない数）であれば No を出力してください。

入力例 1

出力例 1

Yes
Yes
No
No

A27 - Calculate GCD

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

A と B の最大公約数を求めてください。

制約

1 \leq A, B \leq 10^9
A, B は整数

入力

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

A B

出力

A と B の最大公約数を出力してください。

入力例 1

33 88

出力例 1

33 と 88の最大公約数は 11 です。よって、11 と出力すれば正解となります。

入力例 2

123 777

出力例 2

123 と 777 の最大公約数は 3 です。よって、3 と出力すれば正解となります。

A28 - Blackboard

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

最初、黒板に 0 という整数が書かれています。太郎君は整数に対して N 回の操作を行います。
i 回目の操作は文字 T_i と整数 A_i で表され、その内容は以下の通りです。

T_i= + のとき：黒板に書かれた数に A_i を足す。
T_i= - のとき：黒板に書かれた数から A_i を引く。
T_i= * のとき：黒板に書かれた数に A_i を掛ける。

各操作が終わった後について、黒板に書かれた数を 10000 で割った余りを出力するプログラムを作成してください。

制約

N,A_i は整数
1 \le N \le 100000
T_i は +, -, * のいずれかである
1 \le A_i \le 100
黒板に書かれた整数は常に 0 以上である

入力

入力は以下の形式で標準入力から与えられる。

N
T_1 A_1
\vdots
T_N A_N

出力

N 行にわたって出力してください。
i 行目には、i(1 \le i \le N) 回目の操作が終わった直後に書かれた整数を 10000 で割った余りを出力してください。

入力例 1

出力例 1

A29 - Power

Time Limit: 1 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

a^b を 1000000007 (=10^9+7) で割った余りを計算してください。

制約

1 \le a \le 100
1 \le b \le 10^9
入力はすべて整数

入力

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

a b

出力

答えを整数として出力してください。

入力例 1

5 23

出力例 1

871631629

5^{23}=11920928955078125 ですが、これを 10^9+7 で割った余りである 871631629 を出力してください。

入力例 2

97 998244353

出力例 2

934801994

b の値は大きくなることがあります。

Source Name

AOJ NTL_ 1 _B - Power

A30 - Combination

Time Limit: 1 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

N! = 1 \times 2 \times \dots \times N（ N の階乗といいます）とするとき、以下の式の値を 1000000007 （素数）で割った余りを出力してください。

_n\rm{C}_r = \frac{n!}{r! \times (n-r)!}

なお、答えは「 n 個のモノの中から r 個を選ぶ方法の数」と一致することが知られています。

制約

n,r は整数
1 \le n \le 100000
1 \le r \le n

入力

入力は以下の形式で標準入力から与えられる。

n r

出力

答えを 1000000007 で割った余りを出力してください。

入力例 1

4 2

出力例 1

入力例 2

77777 44444

出力例 2

409085577

1000000007 で割った余りを出力してください。

A31 - Divisors

Time Limit: 1 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

1 以上 N 以下の整数のうち、 3,5 のいずれかで割り切れるものは何個ありますか。

制約

N は 1 以上 10^{12} 以下の整数

入力

入力は以下の形式で標準入力から与えられる。

出力

答えを整数として出力してください。

入力例 1

出力例 1

10 以下の整数のうち 3,5 のいずれかで割り切れるものは、 3,5,6,9,10 の 5 個です。

入力例 2

出力例 2

入力例 3

100000000000

出力例 3

46666666667

A32 - Game 1

Time Limit: 1 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

N 個の石が積まれた山があり、 2 人のプレイヤーが交互に石を取り合います。
各プレイヤーは 1 回のターンで、以下のいずれかの操作をすることができます。

山から A 個の石を取り除く。
山から B 個の石を取り除く。

先に石を取り除けなくなった方が負けです。両者が最善を尽くしたとき、先手と後手どちらが勝ちますか。

制約

N,A,B は整数
2 \le N \le 100000
1 \le A < B \le N

入力

入力は以下の形式で標準入力から与えられる。

N A B

出力

先手が勝つ場合は First 、後手が勝つ場合は Second と出力してください。

入力例 1

8 2 3

出力例 1

First

入力例 2

6 2 3

出力例 2

Second

A33 - Game 2

Time Limit: 1 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

石の山が N 個あり、山 i(1 \le i \le N) には A_i 個の石が積まれています。
このゲームでは、 2 人のプレイヤーが交互に次の操作を行います。

好きな石の山を 1 つ選び、選んだ山から 1 個以上の石を取る。

すべての石がなくなり、操作を行えなくなった方が負けです。
両者が最善を尽くしたとき、先手と後手どちらが勝ちますか。

制約

入力は全て整数
2 \le N \le 100000
1 \le A_i \le 10^9

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \dots A_N

出力

先手が勝つ場合は First 、後手が勝つ場合は Second と出力してください。

入力例 1

2
7 7

出力例 1

Second

入力例 2

2
5 8

出力例 2

First

A34 - Game 3

Time Limit: 1 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

石の山が N 個あり、山 i(1 \le i \le N) には A_i 個の石が積まれています。
このゲームでは、 2 人のプレイヤーが交互に次の操作を行います。

好きな石の山を 1つ選び、選んだ山から X 個または Y 個の石を取る。

すべての山にある石の数が X 個未満になり、操作を行えなくなった方が負けです。
両者が最善を尽くしたとき、先手と後手どちらが勝ちますか。

制約

入力は全て整数
1 \le N \le 100000
1 \le X < Y \le 100000
1 \le A_i \le 100000

入力

入力は以下の形式で標準入力から与えられる。

N X Y
A_1 A_2 \dots A_N

出力

先手が勝つ場合は First 、後手が勝つ場合は Second と出力してください。

入力例 1

2 2 3
5 8

出力例 1

First

入力例 2

2 2 3
7 8

出力例 2

Second

A35 - Game 4

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

下図のような N 段のピラミッドがあり、最下段には左から順に整数 A_1,A_2,\dots,A_N が書かれています。また、最上段には 1 つのコマが置かれています。
太郎君と次郎君は、このピラミッドを使ってゲームをします。コマが最下段に到達するまで、各プレイヤーは交互に以下のいずれかの操作を行います（太郎君が先手です）。

コマを左下方向に 1 つ移動させる。
コマを右下方向に 1 つ移動させる。

ゲーム終了時のコマの位置に書かれた整数を スコア とします。太郎君はスコアを最大化し、次郎君はスコアを最小化するとき、スコアはいくつになりますか。

制約

入力は全て整数
2 \le N \le 2000
1 \le A_i \le 100000

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \dots A_N

出力

両者が最善を尽くした場合のスコアを、整数で出力してください。

入力例 1

4
20 10 30 40

出力例 1

A36 - Travel

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

N \times N のマス目があります。「上下左右に隣り合うマスに移動する」という操作をちょうど K 回行うことで、左上のマスから右下のマスまで移動できるかどうかを判定してください。

制約

2 \leq N \leq 10^9
1 \leq K \leq 10^9
入力中の値はすべて整数

入力

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

N K

出力

移動できる場合は Yes、そうでない場合は No と出力してください。

入力例 1

5 10

出力例 1

Yes

下図のような方法で移動を行った場合、ちょうど 10 手で右下のマスにたどり着きます。

Sample01

A37 - Travel 2

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

ALGO 市には N 個の駅と M 個のバス停があり、下図のように道路で結ばれています。すべての組 (i,j) に対して「駅 i からバス停 j までの所要時間」を足した値はいくつですか？

Statement

制約

1 \leq N, M \leq 2 \times 10^5
1 \leq B \leq 100
1 \leq A_i \leq 100 (1 \leq i \leq N)
1 \leq C_j \leq 100 (1 \leq j \leq M)
入力はすべて整数

入力

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

N M B
A_1 A_2 \cdots A_N
C_1 C_2 \cdots C_M

出力

答えを整数で出力してください。

入力例 1

2 3 100
10 20
1 2 3

出力例 1

答えは 111+112+113+121+122+123=702 分です。

A38 - Black Company 1

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

株式会社 KYOPRO-MASTER で働いている太郎君は、今後 D 日間の労働計画を立てることにしました。彼は今期の人事評価を上げるため、より多く働きたいと思っています。しかし、働きすぎると労働基準監督署に怒られてしまいます。具体的には、i = 1,2, ... ,N に対して、以下の条件を満たす必要があります。

条件 i：L_i ～ R_i 日目について、最も多く働いた日でも H_i 時間以下

太郎君の D 日間の合計労働時間として考えられる最大値は何時間でしょうか。ただし、1 日は 24 時間であるものとします。

制約

1 \leq D \leq 365
0 \leq N \leq 10000
1 \leq L_i \leq R_i \leq D
10 \leq H_i \leq 24
入力はすべて整数

入力

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

D N
L_1 R_1 H_1
\vdots
L_N R_N H_N

出力

答えを整数で出力してください。

入力例 1

出力例 1

A39 - Interval Scheduling Problem

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

今日は N 本の映画が上映されます。i 番目の映画は時刻 L_i に開始し、時刻 R_i に終了します。

最大いくつの映画を最初から最後まで見ることができますか。

ただし、映画を見終わった直後に次の映画を見始めることはできますが、同時に複数の映画を見ることはできないものとします。

制約

1 \le N \le 300000
0 \le L_i < R_i \le 86400
入力はすべて整数

部分点

N \leq 2000 を満たすケースで正解すると、500 点が得られます。

入力

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

N
L_1 R_1
L_2 R_2
\vdots
L_N R_N

出力

最大いくつの映画を最初から最後まで見ることができるか出力してください。

入力例 1

3
123 86399
1 86400
86399 86400

出力例 1

以下のようにすると、2 個の映画を最初から最後まで見ることができます。

まず、映画 1 を時刻 123 から時刻 86399 まで見る。
次に、映画 3 を時刻 86399 から時刻 86400 まで見る。

3 個すべての映画を最初から最後まで見る方法はありません。

A40 - Triangle

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

机の上に N 本の棒が置かれています。左から i 番目の棒（棒 i とする）の長さは A_i メートルです。

3 つの異なる棒を選んで正三角形を作る方法は何通りありますか。

制約

3 \leq N \leq 2 \times 10^5
1 \leq A_i \leq 100
入力はすべて整数

入力

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

N
A_1 A_2 \cdots A_N

出力

答えを整数で出力してください。

入力例 1

7
1 2 1 2 1 2 1

出力例 1

正三角形を作る方法として、以下の 5 通りがあります。

棒 1・棒 3・棒 5 を選ぶ。一辺の長さが 1 である正三角形ができる。
棒 1・棒 3・棒 7 を選ぶ。一辺の長さが 1 である正三角形ができる。
棒 1・棒 5・棒 7 を選ぶ。一辺の長さが 1 である正三角形ができる。
棒 3・棒 5・棒 7 を選ぶ。一辺の長さが 1 である正三角形ができる。
棒 2・棒 4・棒 6 を選ぶ。一辺の長さが 2 である正三角形ができる。

A41 - Tile Coloring

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

N 枚のタイルがあり、最初はすべて白色で塗られています。太郎君は以下の操作を繰り返すことで、左から i 番目のタイルの色を文字 S_i（R のとき赤色、 B のとき青色）にしたいです。

連続する 3 つのタイルを赤色で塗り替える
連続する 3 つのタイルを青色で塗り替える

太郎君が目的を達成できるかどうかを判定するプログラムを作成してください。

制約

3 \leq N \leq 200000
文字 S_i は R または B のいずれかである

入力

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

N
S_1 S_2 \cdots S_N

出力

太郎君が目的を達成できるとき Yes、そうでないとき No を出力してください。

入力例 1

7
BBRRRBB

出力例 1

Yes

たとえば以下のような順序で操作を行えば、目的を達成できます。

左から 1, 2, 3 番目のタイルを青色で塗る（現在の盤面：青青青白白白白）
左から 5, 6, 7 番目のタイルを青色で塗る（現在の盤面：青青青白青青青）
左から 3, 4, 5 番目のタイルを赤色で塗る（現在の盤面：青青赤赤赤青青）

入力例 2

5
RBRBR

出力例 2

No

A42 - Soccer

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

情報高校の 1 年 1 組には N 人の生徒が在籍しています。各生徒には体力と気力を表す整数値が定められており、生徒 i \ (1 \leq i \leq N) の体力は A_i、気力は B_i です。

1 年 1 組の担任である太郎君は、レクリエーションの一環として、生徒のうち何人かを選んでサッカーをすることにしました。もし参加者のレベル差が大きい場合、一部の人だけが活躍して面白くないので、以下の条件を満たすようにしたいです。

どの 2 人の参加者も、体力の差が K 以下である
どの 2 人の参加者も、気力の差が K 以下である

最大何人でサッカーをすることができるか、出力するプログラムを作成してください。

制約

1 \leq N \leq 300
1 \leq K \leq 100
1 \leq A_i \leq 100 \ (1 \leq i \leq N)
1 \leq B_i \leq 100 \ (1 \leq i \leq N)
入力に含まれる値は全て整数である

入力

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

N K
A_1 B_1
\vdots
A_N B_N

出力

答えを整数で出力してください。

入力例 1

出力例 1

生徒 1、生徒 2、生徒 4 の 3 人でサッカーをすることができます。

A43 - Travel 3

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

全長 L メートルの ALGO トンネルには、現在 N 人がいます。人 i は西端から A_i メートルの位置におり、方向 B_i へ歩いています（E のとき東、W のとき西）。

トンネルの幅は狭いため、2 人が同じ位置に来たら移動方向を変えます。全員が秒速 1 メートルで歩くとき、最後の人がトンネルの外に出るのは何秒後ですか。

制約

1 \leq N \leq 200000
1 \leq A_1 < A_2 < \cdots < A_N < L \leq 10^9
B_i は E または W である
N, A_i は整数

入力

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

N L
A_1 B_1
\vdots
A_N B_N

出力

答えを整数で出力してください。

入力例 1

出力例 1

人 2 が 80 秒後、3 人のうちで最後にトンネルの外に出ることになります。

A44 - Change and Reverse

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

長さ N の配列 A = [A_1, \ldots, A_N] があり、最初はすべての i について A_i = i となっています。あなたは配列に対して Q 回の操作を行います。j 回目の操作は文字列 Query_j で表されます。

変更操作：Query_j = \ 1 x y のとき、A_x の値を y に変更する
反転操作：Query_j = \ 2 のとき、配列 A を逆順にする
取得操作：Query_j = \ 3 x のとき、A_x の値を答える

すべての取得操作に対して、正しく答えるプログラムを作成してください。

制約

1 \leq N \leq 200000
1 \leq Q \leq 200000
どのタイミングでも、配列 A の要素は 1 以上 10^9 以下の整数である

入力

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

N Q
Query_1
\vdots
Query_Q

出力

取得操作に対する答えを順番に出力してください。詳しくは入出力例をご覧ください。

入力例 1

出力例 1

2
8

配列 A は [1, 2, 3, 4, 5] \rightarrow [1, 2, 3, 8, 5] \rightarrow [5, 8, 3, 2, 1] と変化します。

A45 - Card Elimination

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

太郎君は N 枚のカードを持っています。i 枚目 (1 \leq i \leq N) のカードの色は文字 A_i で表され、R が赤、B が青、W が白に対応します。

彼は、下図の 6 種類の操作を行うことができます。たとえば右下の操作は「青 1 枚と赤 1 枚を、白 1 枚に交換する操作」です。ここで、操作を N - 1 回行うと 1 枚のカードが残ります。最後に残ったカードの色を C にすることが可能かどうか、判定するプログラムを作成してください。

制約

2 \leq N \leq 200000
文字 C は R・B・W のいずれか
文字 A_i は R・B・W のいずれか

入力

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

N C
A_1 A_2 \cdots A_N

出力

最後のカードの色を C にできるとき Yes、そうでないとき No を出力してください。

入力例 1

4 B
WBBR

出力例 1

Yes

次の手順で操作をすると最後に青色のカードが残ります。

青 1 枚と赤 1 枚を白 1 枚に交換する
- 残りの手持ちのカードは WBW になる
白 2 枚を白 1 枚に交換する
- 残りの手持ちのカードは WB になる
白 1 枚と青 1 枚を青 1 枚に交換する
- 残りの手持ちのカードは B になる

A46 - Heuristic 1

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

二次元平面上に N 個の都市があり、1 から N までの番号が付けられています。

都市 i は座標 (X_i, Y_i) にあり、都市 i から都市 j までの距離は \sqrt{(X_i-X_j)^2+(Y_i-Y_j)^2} です。

都市 1 から出発し、すべての都市を一度ずつ通った後、都市 1 へ戻ってくる経路のうち、合計距離ができるだけ短いものを出力してください。

制約

N=150
0 \leq X_i, Y_i \leq 1000

入力

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

N
X_1 Y_1
 :
X_N Y_N

出力

N+1 行にわたって、通った都市の番号を出力してください。
特に、1 行目と N+1 行目は　1 である必要があります。
詳しくは入力例・出力例を参照してください。

得点

各テストケースに対して、以下のように得点が定められます。ただし、合計距離を D とします。

出力が条件を満たさない場合：0 点
出力が条件を満たす場合：\lfloor 10^6 \div D \rfloor 点

全部で 50 個のテストケースがあり、最終的な得点はそれらの合計となります。

入力データ生成方法

すべての採点用入力データは、以下の手順で生成されています。

X_i は 0 以上 1000 以下の整数の中から一様ランダムに選ばれる
Y_i は 0 以上 1000 以下の整数の中から一様ランダムに選ばれる

入力例 1

出力例 1

これは説明用のテストケースであり、制約を満たしていない（採点用テストケースに含まれない）ことに注意してください。

入力例 2

出力例 2

A49 - Heuristic 2

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

長さ 20 の配列 X = [X_1, X_2, \cdots, X_{20}] があります。最初は、すべての要素がゼロとなっています。
あなたは配列に対して T 回の操作を行います。i 手目では、以下のいずれかを選択します。

操作A：X_{P_i}, X_{Q_i}, X_{R_i} に +1 を加算する。
操作B：X_{P_i}, X_{Q_i}, X_{R_i} に -1 を加算する。

各操作が終わった後、「X_j=0 となる j の個数」だけスコアが加算されます。すなわち、スコアの加算は全部で T 回行われます。
できるだけスコアが大きくなるような操作手順を求めてください。

制約

T=100
1 \leq P_i < Q_i < R_i \leq 20
入力はすべて整数

入力

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

T
P_1 Q_1 R_1
 :
P_T Q_T R_T

出力

T 行にわたって出力してください。
i 行目には、i 手目に行う操作の番号（A または B）を出力してください。

得点

各テストケースに対して、スコアと同じ点数が得られます。全部で 50 個のテストケースがあり、最終的な得点はそれらの合計となります。

入力データ生成方法

すべての採点用入力データは、以下の手順で生成されています。

i=1, 2, \cdots, N の順に、以下の処理を行う
P_i を、1 以上 20 以下の整数の中から一様ランダムに選ぶ
Q_i を、1 以上 20 以下の整数の中から一様ランダムに選ぶ
R_i を、1 以上 20 以下の整数の中から一様ランダムに選ぶ
P_i < Q_i < R_i を満たせば終了。そうでなければ 1. に戻る。

入力例 1

出力例 1

A
B
A

これは説明用のテストケースであり、制約を満たしていない（採点用テストケースに含まれない）ことに注意してください。

入力例 2

出力例 2

B
A
B
A
B
A
B
A
B
A
B
B
A
B
A
A
B
B
A
B
A
A
A
B
A
B
A
B
B
B
B
B
B
A
B
A
A
A
A
A
A
A
B
B
A
A
B
A
B
A
B
B
B
B
A
A
B
B
A
A
A
B
A
B
A
B
B
A
A
B
A
A
B
B
A
A
B
B
B
B
B
A
A
B
A
A
B
B
B
A
B
A
A
B
A
A
B
B
B
A

A50 - 山型足し算

Time Limit: 6 sec / Memory Limit: 1024 MB

配点 : 10000000000 点

問題文

N 行 N 列のマス目 A が与えられます。一番左上のマスの位置を (0,0) と定義します。
このとき、左上のマスから下に i\ (0 ≦ i ≦ N-1) マス、右に j\ (0 ≦ j ≦ N-1) マス進んだマスの位置は (j,i) で表されます。
また，各マスに整数が書かれており、位置 (j,i) のマスに書かれている整数を A_{i,j} で表します。

ここで、マス目に対して全てのマスに書かれている整数が 0 である状態を「初期マス目」と定義します。
また、マス目 P に対する「山型足し算」 (X,Y,H) を以下のように定義します。

まず，山の中心となるマスの位置 (X,Y)\ (0 ≦ X,Y ≦ N-1) と山の高さを表す整数 H\ (1 ≦ H ≦ N) を指定します。
その後、全てのマスの P_{y,x} を P_{y,x} + max(0, H - |x-X| - |y-Y|) に書き換えます。

例として、8 行 8 列の初期マス目であるマス目 Q を考えます。
マス目 Q に対して、 3 回の山型足し算 (X,Y,H) = (1,2,5),(5,1,3),(6,6,2) を行った後のマス目を以下の図に示します。

図山型足し算の例 (空白のマスは 0 を表す。)

与えられたマス目 A は、N 行 N 列の初期マス目に対して、山型足し算を 1000 回行って生成されたマス目です。
あなたの目的は、マス目 A にできる限り近いマス目を生成する山型足し算の手順を求めることです。

具体的にはまず、N 行 N 列の初期マス目であるマス目 B を用意します。
次に、あなたはマス目 B に対して山型足し算を最大 1000 回まで行うことができます。
そして、マス目 A とマス目 B を比較したときを最小化する山型足し算の手順を求めることを目的とします。
さらに、マス目 A を生成するような山型足し算の手順が複数存在する場合には、山型足し算の回数を最小化することを目指してください。

採点方法

各テストケースの得点は以下のように計算される。

縦 N マス、横 N マスの初期マス目に対し、あなたのプログラムが出力した山型足し算の手順に従い、マス目 B を生成する。
まず、基本点として点が得られる。
マス目 A とマス目 B に書かれている整数が全てのマスで一致した場合、山型足し算の回数を Q とすると、ボーナス点として 1,000-Q 点が得られる。

問題全体の得点は以下のように計算される。

テストケースの数は、以下の入力例 1 を含む 50 ケースである。この 50 ケースの点数の和がプログラムの点数となる。
全テストケースのステータスに「AC」以外が存在する場合には、「example_01」を除く全てのテストケースの点数は0点となるので注意せよ。

制約

N=100
0 ≦ A_{i,j} ≦ 100,000
マス目 A は初期マス目に対して 1000 回の山型足し算を行うことで生成されたマス目である。

入力

入力は以下の形式で与えられる。

A_{0,0} A_{0,1} ... A_{0,N-1}
A_{1,0} A_{1,1} ... A_{1,N-1}
:
A_{N-1,0} A_{N-1,1} ... A_{N-1,N-1}

出力

マス目 A にできる限り近いマス目 B を生成する山型足し算の手順を以下の形式で出力せよ。

Q
X_1 Y_1 H_1
X_2 Y_2 H_2
:
X_Q Y_Q H_Q

1 行目には山型足し算の回数 Q\ (0≦Q≦1000) を出力せよ。
1+i \ (1 ≦ i ≦ Q) 行目には、i 回目の山型足し算で用いるパラメータ (X_i,Y_i,H_i) を表す整数をスペース区切りで出力せよ。

テストケースの生成方法

マス目 A は初期マス目に対して、1000 回の山型足し算を行うことで生成される。

各回の山型足し算で用いられるパラメータ `(X,Y,H)` についての制約

X は [0,N-1] の範囲で、一様乱数によってランダムに選ばれる。
Y は [0,N-1] の範囲で、一様乱数によってランダムに選ばれる。
H は [1,N] の範囲で、一様乱数によってランダムに選ばれる。

入出力例1

入出力ファイルはこちらから(zip)

テストケース「example_01」が入出力例1に対応します。テストケース「example_01」も採点対象となります。

ビジュアライザ

入力ファイルと出力ファイルから、点数の計算および結果を可視化するビジュアライザを用意しました。

このビジュアライザはchromeでの使用を推奨します。他の環境で正常に動作することを保証していません。特にInternet Explorerでは動作しないことを確認しています。
このビジュアライザから解答の提出はできません。 AtCoder 上で解答を提出して下さい。
このビジュアライザ上で計算された点数は、当コンテスト上での点数を保証するものではありません。このビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。

操作方法と見方

左クリックで回転、右クリックで移動、マウスホイールで拡大縮小が出来ます。
入力ファイルのマス目 A と出力ファイルの山型足し算手順から生成されるマス目 B を比較して、赤・白・青の3つの領域に色分けされます。
それぞれについて、赤：一致、白：不足 ( A_{i,j} > B_{i,j} の場合のみ出現) 、青：過剰　( A_{i,j} < B_{i,j} の場合のみ出現) を表します。
高さ方向はデフォルトの縮尺を1/100にしています。縮尺は変更可能となっているため、見易い縮尺に調整してください。

入力ファイル：
出力ファイル：
高さの縮尺：/100

統計情報（高さいくつのピラミッドをそれぞれいくら使ったか）

（データを入力すると統計情報が表示されます）

A51 - Stack

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

以下の 3 種類のクエリを高速に処理するプログラムを実装してください。

クエリ 1： x という題名の本を机の一番上に積む。
クエリ 2：一番上に積まれている本の題名を答える。
クエリ 3：一番上に積まれている本を机から取り出す。

ただし、最初は机の上に本が積まれておらず、与えられるクエリの数は Q 個であるとします。

入力

Query_i は i 回目のクエリの情報を表します。クエリ 1 の場合は 1 x、クエリ 2 の場合は 2、クエリ 3 の場合は 3 という形式で与えられます。

詳しくは入力例をご覧ください。

Q
Query_1
:
Query_Q

出力

クエリ 2 の答えを、順番に出力してください。

制約

1 \leq Q \leq 100,000
与えられる本の題名は 20 文字以下であり、英小文字からなる
クエリ 2 およびクエリ 3 の時点では、一冊以上の本が積まれている

入力例 1

5
1 futuremap
1 howtospeak
2
3
2

出力例 1

howtospeak
futuremap

A52 - Queue

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

以下の 3 種類のクエリを高速に処理する、行列管理システムを実装してください。

クエリ 1：行列の最後尾に x さんが並ぶ。
クエリ 2：行列の先頭にいる人の名前を答える。
クエリ 3：行列の先頭にいる人を列から抜けさせる。

ただし、最初は行列に人がおらず、与えられるクエリの数は Q 個であるとします。

入力

詳しくは入力例をご覧ください。

Q
Query_1
:
Query_Q

出力

クエリ 2 の答えを、順番に出力してください。

制約

1 \leq Q \leq 100,000
与えられる人の名前は 20 文字以下であり、英小文字からなる
クエリ 2 およびクエリ 3 の時点では、一人以上が列に存在する

入力例 1

5
1 taro
1 hanako
2
3
2

出力例 1

taro
hanako

A53 - Priority Queue

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

以下の 3 種類のクエリを高速に処理する、販売システムを実装してください。

クエリ 1：価格が x 円の商品が追加される。
クエリ 2：今ある商品の中の最小価格を答える。
クエリ 3：最も安い商品が 1 つ売れる。

ただし、最初は商品が 1 つもなく、与えられるクエリの数は Q 個であるとします。

入力

詳しくは入力例をご覧ください。

Q
Query_1
:
Query_Q

出力

クエリ 2 の答えを、順番に出力してください。

制約

1 \leq Q \leq 100,000
商品の値段は 1 以上 1,000,000 以下の整数である
クエリ 2 およびクエリ 3 の時点では、一つ以上の商品が存在する

入力例 1

出力例 1

A54 - Map

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

以下の 2 種類のクエリを高速に処理する、成績管理システムを実装してください。

クエリ 1：生徒 x の成績が y 点になったと登録される。
クエリ 2：生徒 x の成績を答える。

ただし、最初は誰の成績も登録されておらず、与えられるクエリの数は Q 個であるとします。

入力

Query_i は i 回目のクエリの情報を表します。クエリ 1 の場合は 1 x y、クエリ 2 の場合は 2 x という形式で与えられます。

詳しくは入力例をご覧ください。

Q
Query_1
:
Query_Q

出力

クエリ 2 の答えを、順番に出力してください。

制約

1 \leq Q \leq 100,000
成績は 0 以上 100 以下の整数である
名前は 20 文字以下であり、英小文字からなる
クエリ 1 では、同じ名前の人が二度登録されることはない
クエリ 2 では、その時点で未登録の人の点数を聞くことはない

入力例 1

3
1 tanaka 49
1 suzuki 50
2 tanaka

出力例 1

A55 - Set

Time Limit: 3 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

以下の 3 種類のクエリを高速に処理するプログラムを実装してください。

クエリ 1：x と書かれたカードが机に置かれる。
クエリ 2：x と書かれたカードが机から除去される。
クエリ 3：机にある x 以上のカードのうち最小のものを答える。

ただし、最初の時点では机の上に 1 個もカードが置かれていないものとします。

入力

Query_i は i 回目のクエリの情報を表します。クエリ 1 の場合は 1 x、クエリ 2 の場合は 2 x、クエリ 3 の場合は 3 x という形式で与えられます。

詳しくは入力例をご覧ください。

Q
Query_1
:
Query_Q

出力

クエリ 3 の答えを、順番に出力してください。ただし、x 以上のカードが机の上に存在しないクエリについては、-1 と出力してください。

制約

1 \leq Q \leq 100,000
1 \leq x \leq 10^9
クエリ 1 では、既に置かれているカードが追加されることはない
クエリ 2 では、置かれていないカードが除去されることはない

入力例 1

出力例 1

77
-1

A56 - String Hash

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

長さ N の文字列 S が与えられます。以下の Q 個のクエリを処理してください。

i 個目のクエリ：S[a_i, b_i] と S[c_i, d_i] は一致するか？

ただし、S[l, r] は S の l 文字目から r 文字目までの連続部分文字列のことを指します。

制約

N, Q, a_i, b_i, c_i, d_i は整数である
S は英小文字からなる文字列である
1 \leq N \leq 200000
1 \leq Q \leq 200000
|S| = N
1 \leq a_i \leq b_i \leq N
1 \leq c_i \leq d_i \leq N
b_i - a_i = d_i - c_i

入力

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

N Q
S
a_1 b_1 c_1 d_1
a_2 b_2 c_2 d_2
\vdots
a_Q b_Q c_Q d_Q

出力

Q 行にわたって出力してください。i 行目には、i 個目のクエリで文字列が一致する場合 Yes、そうでない場合 No と出力してください。

入力例 1

出力例 1

Yes
No
No

1 個目のクエリでは、S[1, 3] と S[5, 7] が一致するかどうか聞かれています。いずれも abc であり一致するので、Yes と出力します。

2 個目のクエリでは、S[1, 5] と S[2, 6] が一致するかどうか聞かれています。S[1, 5] = abcba、S[2, 6] = bcbab であり一致しないので、No と出力します。

A57 - Doubling

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

N 個の穴がある砂場に、一匹のアリが住んでいます。このアリは規則的な動きをすることが知られており、穴 i（1 \leq i \leq N）に入った翌日には穴 A_i に移動します。

それについて、以下の Q 個のクエリを処理してください。

j 個目のクエリ：いま穴 X_j にいるとき、Y_j 日後にはどの穴にいるか？

制約

入力はすべて整数である
1 \leq N \leq 100000
1 \leq Q \leq 100000
1 \leq A_i \leq N
1 \leq X_j \leq N
1 \leq Y_j \leq 10^9

入力

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

N Q
A_1 A_2 \ldots A_N
X_1 Y_1
X_2 Y_2
\vdots
X_Q Y_Q

出力

Q 行にわたって出力してください。j 行目には、j 個目のクエリの答えを出力してください。

入力例 1

7 4
2 4 1 7 6 5 3
1 1
1 5
2 13
5 999999999

出力例 1

いま穴 1 にいるとき、

1 日後には穴 A_1 = 2
2 日後には穴 A_2 = 4
3 日後には穴 A_4 = 7
4 日後には穴 A_7 = 3
5 日後には穴 A_3 = 1

にいます。よって、1, 2 個目のクエリの答えはそれぞれ 2, 1 です。

A58 - RMQ (Range Maximum Queries)

Time Limit: 3 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

長さ N の数列 A = (A_1, A_2, \ldots, A_N) があり、最初はすべての要素が 0 になっています。以下の 2 種類のクエリを処理してください。

クエリ 1：A_{\mathrm{pos}} の値を x に更新する。
クエリ 2：A_l, A_{l+1}, \ldots, A_{r-1} の最大値を答える。

ただし、与えられるクエリの数は全部で Q 個であるとします。

制約

入力はすべて整数である
1 \leq N \leq 100000
1 \leq Q \leq 100000
1 \leq \mathrm{pos} \leq N
0 \leq x \leq 10^9
1 \leq l < r \leq N + 1

入力

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

N Q
\mathrm{Query}_1
\mathrm{Query}_2
\vdots
\mathrm{Query}_Q

i 番目のクエリ \mathrm{Query}_i では、まずクエリの種類 c_i（1 または 2）が与えられます。c_i = 1 の場合は \mathrm{pos}, x が、c_i = 2 の場合は l, r が追加で与えられます。

すなわち、各クエリは以下に示す 2 つの形式のいずれかです。

1 \mathrm{pos} x

2 l r

出力

クエリ 2 の答えを、順番に出力してください。

入力例 1

出力例 1

0
13

はじめ、A = (0, 0, 0, 0, 0, 0, 0, 0) です。
1 個目のクエリでは、A_3 の値を 16 に更新します。A = (0, 0, 16, 0, 0, 0, 0, 0) となります。
2 個目のクエリでは、(A_4, A_5, A_6) = (0, 0, 0) の最大値 0 を出力します。
3 個目のクエリでは、A_5 の値を 13 に更新します。A = (0, 0, 16, 0, 13, 0, 0, 0) となります。
4 個目のクエリでは、(A_4, A_5, A_6) = (0, 13, 0) の最大値 13 を出力します。

A59 - RSQ (Range Sum Queries)

Time Limit: 3 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

長さ N の数列 A = (A_1, A_2, \ldots, A_N) があり、最初はすべての要素が 0 になっています。以下の 2 種類のクエリを処理してください。

クエリ 1：A_{\mathrm{pos}} の値を x に更新する。
クエリ 2：A_l, A_{l+1}, \ldots, A_{r-1} の合計値を答える。

ただし、与えられるクエリの数は全部で Q 個であるとします。

制約

入力はすべて整数である
1 \leq N \leq 100000
1 \leq Q \leq 100000
1 \leq \mathrm{pos} \leq N
0 \leq x \leq 1000
1 \leq l < r \leq N + 1

入力

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

N Q
\mathrm{Query}_1
\mathrm{Query}_2
\vdots
\mathrm{Query}_Q

すなわち、各クエリは以下に示す 2 つの形式のいずれかです。

1 \mathrm{pos} x

2 l r

出力

クエリ 2 の答えを、順番に出力してください。

入力例 1

出力例 1

24
40

はじめ、A = (0, 0, 0, 0, 0, 0, 0, 0) です。
1 個目のクエリでは、A_3 の値を 16 に更新します。A = (0, 0, 16, 0, 0, 0, 0, 0) となります。
2 個目のクエリでは、A_6 の値を 24 に更新します。A = (0, 0, 16, 0, 0, 24, 0, 0) となります。
3 個目のクエリでは、(A_4, A_5, A_6, A_7) = (0, 0, 24, 0) の合計値 24 を出力します。
4 個目のクエリでは、(A_1, A_2, A_3, A_4, A_5, A_6) = (0, 0, 16, 0, 24, 0) の合計値 40 を出力します。

A60 - Stock Price

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

株式会社 KYOPRO-MASTER は上場から N 日が経過しており、i 日目の株価は A_i 円でした。太郎君は、それぞれの日について「株価が何日ぶりの高値を更新したか」を求めようと思いました。ここで d 日目に対する 起算日 を次のように定義します。

i < d かつ A_i > A_d を満たす最大の i
ただし、そのような i が存在しない場合、起算日はない

d = 1, 2, \ldots, N について、起算日を計算してください。

制約

入力はすべて整数である
1 \leq N \leq 200000
1 \leq A_i \leq 10^9
A_1, A_2, \ldots, A_N はすべて異なる

入力

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

N
A_1 A_2 \ldots A_N

出力

d = 1, 2, \ldots, N のときの起算日を、空白区切りで出力してください。ただし、起算日が存在しない日については -1 と出力してください。

入力例 1

6
6 2 5 3 1 4

出力例 1

-1 1 1 3 4 3

たとえば 6 日目の起算日は 3 日目です。なぜなら、5 日目・4 日目は株価が A_6（= 4）円以下であり、3 日目は株価が A_6（= 4）円を超えているからです。

A61 - Adjacent Vertices

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

頂点数 N、辺数 M のグラフが与えられます。頂点には 1 から N までの番号が付けられており、i 番目の辺は頂点 A_i と B_i を双方向に結んでいます。それぞれの k について、「頂点 k と隣接している頂点の番号」をすべて出力するプログラムを作成してください。

制約

2 \leq N \leq 100000
1 \leq M \leq 100000
1 \leq A_i \lt B_i \leq N\ (1\leq i\leq M)
i \neq j \implies (A_i,B_i) \neq (A_j,B_j)
入力は全て整数

入力

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

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

N 行にわたって出力してください。k 行目には、頂点 k と隣接している頂点の番号を、出力例の形式にならって出力してください(出力の順序は問いません)。

入力例 1

出力例 1

1: {2}
2: {1, 3}
3: {2, 4, 5}
4: {3}
5: {3}

与えられたグラフは次のようになります。

たとえば 2 行目については、2: {1, 3} ではなく 2: {3, 1} と出力しても正解となります。

入力例 2

出力例 2

1: {3, 4, 6, 9, 13}
2: {4, 6, 8, 9, 14}
3: {1, 5, 9}
4: {1, 2, 6, 9, 13, 14}
5: {3, 9, 15}
6: {1, 2, 4, 9, 13}
7: {9}
8: {2, 9, 10}
9: {1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15}
10: {8, 9}
11: {9, 15}
12: {9}
13: {1, 4, 6, 9}
14: {2, 4, 9}
15: {5, 9, 11}

A62 - Depth First Search

Time Limit: 1 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

各頂点に 1,2,\dots,N の番号がついた、 N 頂点 M 辺の無向グラフが与えられます。
i 番目の辺は頂点 A_i と頂点 B_i とを結んでいます。
このグラフ全体が連結であるかどうか判定して以下のように出力してください。

もしグラフ全体が連結であれば、 The graph is connected. と出力する
そうでなければ、 The graph is not connected. と出力する

制約

入力はすべて整数
1 \le N \le 10^5
0 \le M \le \min(10^5,\frac{N(N-1)}{2})
1 \le A_i < B_i \le N
グラフに多重辺や自己ループは存在しない

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

問題文中の指示通り出力せよ。

入力例 1

3 2
1 3
2 3

出力例 1

The graph is connected.

与えられたグラフは連結です。

入力例 2

出力例 2

The graph is not connected.

与えられたグラフは連結ではありません。

A63 - Shortest Path 1

Time Limit: 1 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

N 頂点 M 辺の無向グラフが与えられます。各頂点には 1 から N までの番号が付けられており、i 番目の辺は頂点 A_i と頂点 B_i を結んでいます。

1 以上 N 以下の全ての整数 k について、以下の問いに答えてください。

頂点 1 から頂点 k まで、辺を何本かたどって移動することを考えるとき、たどるべき辺の本数の最小値を出力せよ。ただし、移動不可能な場合は -1 を出力せよ。

制約

入力はすべて整数
1 \le N \le 10^5
0 \le M \le \min(10^5,\frac{N(N-1)}{2})
1 \le A_i < B_i \le N
グラフに多重辺や自己ループは存在しない

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

全体で N 行出力してください。

i 行目には、 k=i の場合の答えを出力してください。

入力例 1

3 2
1 3
2 3

出力例 1

0
2
1

頂点 1 から頂点 1 には、 0 本の辺を辿って移動可能であるとします。
頂点 1 から頂点 2 に移動する際、 1 \rightarrow 3 \rightarrow 2 と移動すると辿る辺の数が最小になります。
頂点 1 から頂点 3 に移動する際、 1 \rightarrow 3 と移動すると辿る辺の数が最小になります。

入力例 2

出力例 2

与えられるグラフが連結であるとは限りません。

A64 - Shortest Path 2

Time Limit: 3 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

重み付き無向グラフに対する最短経路問題を解いてください。具体的には、以下のようなグラフが与えられるとき、頂点 1 から各頂点までの最短経路長を求めてください。

頂点数は N 、辺数は M である
i 番目の辺は頂点 A_i と頂点 B_i を結び、長さは C_i である

なお、以降の説明では、頂点 1 から頂点 k までの最短経路長を \operatorname{dist}[k] とします。

制約

2 \leq N \leq 100000
1 \leq M \leq \min(100000,N(N-1)/2)
1 \leq A_i \lt B_i \leq N\ (1\leq i\leq M)
1 \leq C_i \leq 10000\ (1\leq i\leq M)
i \neq j \implies (A_i,B_i) \neq (A_j,B_j)
入力は全て整数

入力

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

N M
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_M B_M C_M

出力

k 行目には \operatorname{dist}[k] の値を出力してください。ただし、頂点 k まで移動できない場合は代わりに -1 と出力してください。

入力例 1

出力例 1

与えられるグラフは次のようになります。

入力例 2

出力例 2

A65 - Road to Promotion

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

株式会社 KYOPRO-MASTER には N 人の社員がおり、地位順に 1 から N までの番号が付けられています。社長(社員 1)以外には直属の上司が 1 人おり、社員 i の直属の上司は社員 A_i です。各社員について、部下が何人いるかを出力してください。ただし、社員 y が社員 x の部下であるとは、x\neq y であり、なおかつ社員 y の直属の上司をたどって社員 x に到達できることを指します。

制約

2 \leq N \leq 100000
1 \leq A_i \leq i-1\ (2\leq i\leq N)
入力は全て整数

入力

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

N
A_2 A_3 \cdots A_N

出力

社員 1,2,\ldots,N の部下の数を、空白区切りで出力してください。

入力例 1

7
1 1 3 2 4 4

出力例 1

6 1 3 2 0 0 0

入力例 2

15
1 2 1 1 1 6 2 6 9 10 6 12 13 12

出力例 2

14 2 0 0 0 8 0 0 2 1 0 3 1 0 0

与えられるグラフは次のようになります。

A66 - Connect Query

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

頂点数 N のグラフに対して、以下の 2 種類のクエリを高速に処理してください。

クエリ 1：頂点 u と頂点 v を双方向に結ぶ辺を追加する。
クエリ 2：頂点 u と頂点 v は同じ連結成分に属するかを答える。

ただし、最初はグラフに辺が一本もなく、与えられるクエリの数は Q 個であるとします。

制約

2 \leq N \leq 100000
1 \leq Q \leq 100000
\operatorname{Query}_i\ (1\leq i\leq Q) はすべて t_i u_i v_i の形式
t_i \in \{1,2\}\ (1\leq i\leq Q)
1 \leq u_i \lt v_i \leq N\ (1\leq i\leq Q)
入力は全て整数

入力

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

N Q
\operatorname{Query}_1
\operatorname{Query}_2
\vdots
\operatorname{Query}_Q

\operatorname{Query}_i は i 回目のクエリの情報を表します。クエリ 1 の場合は 1 u v、クエリ 2 の場合は 2 u v という形式で与えられます。詳しくは入力例をご覧ください。

出力

クエリ 2 の答えを、順番に出力してください。

入力例 1

出力例 1

No
Yes

クエリ 1 の結果、グラフは次のように変化します。

入力例 2

出力例 2

No
No
Yes
Yes
No

A67 - MST (Minimum Spanning Tree)

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

頂点数 N、辺数 M のグラフが与えられます。頂点には 1 から N までの番号が付けられており、辺 i は頂点 A_i と B_i を双方向に結ぶ長さ C_i の辺です。このグラフの最小全域木における辺の長さの総和を求めてください。

制約

2 \leq N \leq 100000
1 \leq M \leq 100000
1 \leq A_i \lt B_i \leq N
i\neq j ならば (A_i,B_i) \neq (A_j,B_j)
1 \leq C_i \leq 10000
与えられるグラフは連結
入力はすべて整数

入力

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

N M
A_1 B_1 C_1
\vdots
A_M B_M C_M

出力

最小全域木における辺の長さの総和を出力してください。

入力例 1

出力例 1

A68 - Maximum Flow

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

N 個のタンクと M 本のパイプがあります、j 本目のパイプはタンク A_j からタンク B_j の方向に毎秒 C_j リットルまで水を流すことができます。
タンク 1 からタンク N まで毎秒最大何リットルの水を流すことができますか。ただし、タンクに水を貯めることはできないと考えてかまいません。

制約

2 \leq N \leq 400
1 \leq M \leq 400
1 \leq A_j , B_j \leq N
A_j \neq B_j
j\neq k ならば (A_j,B_j) \neq (A_k,B_k)
0 \leq C_j \leq 5000
答えは 5000 以下の整数
入力はすべて整数

入力

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

N M
A_1 B_1 C_1
\vdots
A_M B_M C_M

出力

毎秒最大何リットルを流すことができるか、整数で出力してください。

入力例 1

出力例 1

A69 - Bipartite Matching

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

注意

書籍の版によっては、書籍内の入力例が正しくない場合があります。正誤表を参照してください。

問題文

情報高校の 1 年 A 組には N 人の生徒がおり、1 から N までの番号が付けられています。また、教室の席も N 個あり、1 から N までの番号が付けられています。
さて、今日はクラスで席替えを行うことになりました。「生徒〇〇は視力が悪いので前の方が良い」といった希望が与えられるので、最大何人の希望をかなえられるかを求めてください。

制約

1 \leq N \leq 150
N は整数である
C_{i,j} は # または . である

入力

入力は以下の形式で標準入力から与えられます。
生徒 i が席 j に座っても良い場合は C_{i,j}= # 、そうでない場合は C_{i,j}= . となります。

N
C_{1,1} C_{1,2} \ldots C_{1,N}
C_{2,1} C_{2,2} \ldots C_{2,N}
\vdots
C_{N,1} C_{N,2} \ldots C_{N,N}

出力

最大何人の希望をかなえられるかを出力してください。

入力例 1

5
#....
#.#..
....#
....#
...##

出力例 1

A70 - Lanterns

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

N 個のランプが机の上に置かれています。i 個目のランプの最初の状態は整数 A_i で表され、A_i = 0 のとき OFF、A_i = 1 のとき ON です。
太郎君は、電灯に対して M 種類の操作を行うことができます。i 種類目の操作は、ランプ X_i,Y_i,Z_i の状態を同時に反転させるものです。ここで反転とは、OFF であるランプを ON にし、ON であるランプを OFF にすることを指します。
最小何回の操作で、すべてのランプの状態を ON にすることができるかを求めてください。ただし、同じ種類の操作を複数回行っても良いものとします。

制約

3 \leq N \leq 10
0 \leq M \leq 100
A_i \in \{ 0,1 \}
1 \leq X_i \lt Y_i \lt Z_i \leq N
i \neq j ならば (X_i,Y_i,Z_i) \neq (X_j,Y_j,Z_j)
入力はすべて整数

入力

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

N M
A_1 A_2 \ldots A_N
X_1 Y_1 Z_1
\vdots
X_M Y_M Z_M

出力

答えを出力してください。ただし、何回操作を行っても、すべてのランプの状態を ON にすることが不可能である場合、代わりに -1 と出力してください。

入力例 1

出力例 1

A71 - Homework

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

あなたは夏休みの宿題 N 個を、毎日 1 つずつ終わらせなければなりません。宿題には 1 から N までの番号が付けられており、宿題 i の 難易度 は整数 A_i で表されます。

また、夏休み i 日目 (1 \leq i \leq N) の気温は B_i 度になることが予想されています。「難易度 × 気温」の総和だけ労力がかかるとき、すべての宿題を終わらせるために必要な労力の最小値はいくつですか。

制約

2 \leq N \leq 60
1 \leq A_i \leq 100
1 \leq B_i \leq 45

入力

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

N
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N

出力

必要な労力として考えられる最小値を求めてください。

入力例 1

3
10 20 30
35 40 33

出力例 1

1 日目に宿題 2、2 日目に宿題 1、3 日目に宿題 3 を終わらせた場合、必要な労力は (20 \times 35) + (10 \times 40) + (30 \times 33) = 2090 となり、これが最小です。

A72 - Tile Painting

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

縦 H 行、横 W 列のマス目があります。上から i 行目・左から j 列目のマス (i, j) の色は c_{i,j} であり、c_{i,j} = . のとき白色、 c_{i,j} = # のとき黒色で塗られています。

あなたは「ある行またはある列を選び、すべて黒で塗り替える」という操作を K 回まで行うことができます。最大で何個のマスを黒くすることができますか。

制約

1 \leq H \leq 10
1 \leq W \leq 100
1 \leq K \leq \min(H, W)
c_{i, j} は . または # である

入力

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

H W K
c_{1, 1} c_{1, 2} \cdots c_{1, W}
\vdots
c_{H, 1} c_{H, 2} \cdots c_{H, W}

出力

最大で何個のマスを黒くすることができるか、出力してください。

入力例 1

4 10 3
##...#.##.
.#....#...
##.####..#
#..######.

出力例 1

A73 - Marathon Route

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

注意

書籍の版によっては、書籍内のコードが正しくない場合があります。正誤表を参照してください。

問題文

ALGO 市には N 個の交差点と M 本の道路があります。i 本目の道路は、交差点 A_i と交差点 B_i を双方向に結んでおり、長さは C_i メートルです。交差点どうしは、いくつかの道路を通って必ず行き来できることが保証されます。また、 D_i = 1 であるような道路には、木が一本植えられています。

ALGO 市の市長である次郎君は、交差点 1 と交差点 N を結ぶマラソンコースを作ろうと思いました。彼は参加者を疲れさせたくないので、合計距離をできるだけ短くしたいです。また参加者に自然を楽しんでいただきたいので、合計距離が同じ場合、コース上に植えられている木の数をより多くしたいです。どのようなマラソンコースが考えられますか。

制約

2 \leq N \leq 8{,}000
1 \leq M \leq 100{,}000
1 \leq C_i \leq 100
交差点どうしは、いくつかの道路を通って必ず行き来できることが保証される
1 \leq A_i < B_i \leq N
i \neq j ならば (A_i, B_i) \neq (A_j, B_j)
D_i は 0 または 1 である

入力

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

N M
A_1 B_1 C_1 D_1
\vdots
A_M B_M C_M D_M

出力

マラソンコースの合計距離と、コース上にある木の数を空白区切りで出力してください。

入力例 1

出力例 1

90 2

A74 - Board Game

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

1 から N までの整数が一個ずつ書かれた N \times N のマス目 P が与えられます。太郎君は、

隣接する 2 つの行を交換する
隣接する 2 つの列を交換する

という 2 種類の操作を繰り返すことで、すべての k に対して「整数 k が上から k 行目・左から k 列目のマスに存在する」ようにしたいです。最小何回の操作が必要ですか。

制約

2 \leq N \leq 100

入力

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

P_{i, j} は上から i 行目・左から j 列目に書かれた整数を表します。ただし、 P_{i, j} = 0 のマスには整数が書かれていません。ここで、各行・各列には「整数が書かれたマス」がちょうど 1 つ存在することが保証されています。

N
P_{1, 1} P_{1, 2} \cdots P_{1, N}
P_{2, 1} P_{2, 2} \cdots P_{2, N}
\vdots
P_{N, 1} P_{N, 2} \cdots P_{N, N}

出力

最小の操作回数を出力してください。

入力例 1

出力例 1

A75 - Examination

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

次郎君は N 問からなる期末試験を受けることになりました。各設問には 1 から N までの番号が付けられており、設問 i は連続する T_i 分間を使って考えると正解にたどり着けます。

しかし、各設問には締切が定められており、設問 i は試験開始時刻から D_i 分後を過ぎると回答できなくなります。次郎君が最適な行動をしたとき、最大で何問正解することができるかを求めてください。

制約

1 \leq N \leq 100
1 \leq T_i \leq 1{,}440
1 \leq D_i \leq 1{,}440

入力

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

N
T_1 D_1
\vdots
T_N D_N

出力

最大で何問正解することができるか、整数で出力してください。

入力例 1

出力例 1

設問 2 → 設問 4 → 設問 1 → 設問 3 の順に解けば、すべての設問に正解することができます。

A76 - River Crossing

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

注意

書籍の版によっては、書籍内のコードが正しくない場合があります。正誤表を参照してください。

問題文

川幅が W メートルである KYOPRO 川には、 N 個の足場が一直線上に並べられており、西から順に 1 から N までの番号が付けられています。足場 i (1 \leq i \leq N) は西岸から X_i メートルの位置にあります。

太郎君は東方向のジャンプを繰り返すことで、西岸から東岸まで移動しようと思いました。しかし、一回のジャンプで飛ぶ距離は長すぎても短すぎてもダメであり、 L メートル以上 R メートル以下でなければなりません。移動方法は全部で何通りありますか。

制約

1 \leq N \leq 150{,}000
0 < X_1 < X_2 < \cdots < X_N < W \leq 10^{9}
1 \leq L \leq R \leq W

入力

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

N W L R
X_1 X_2 \ldots X_N

出力

答えを 1{,}000{,}000{,}007 で割った余りを出力してください。

入力例 1

5 65 7 37
5 15 30 50 55

出力例 1

A77 - Yokan Party（★4）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 4 点

問題文

左右の長さが L [cm] のようかんがあります。 N 個の切れ目が付けられており、左から i 番目の切れ目は左から A_i [cm] の位置にあります。

あなたは N 個の切れ目のうち K 個を選び、ようかんを K+1 個のピースに分割したいです。そこで、以下の値を スコア とします。

K+1 個のピースのうち、最も短いものの長さ（cm 単位）

スコアが最大となるように分割する場合に得られるスコアを求めてください。

制約

1 \leq K \leq N \leq 100000
0 \lt A_1 \lt A_2 \lt \cdots \lt A_N \lt L \leq 10^9
入力はすべて整数

入力

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

N L
K
A_1 A_2 \cdots A_N

出力

求めるスコアを出力してください。

入力例 1

3 34
1
8 13 26

出力例 1

左から 2 番目の切れ目で分割すると、長さ 13 [cm] のピースと長さ 21 [cm] のピースに分かれ、スコア 13 を達成できます。

入力例 2

7 45
2
7 11 16 20 28 34 38

出力例 2

左から 3 番目と 5 番目の切れ目で分割すると、スコア 12 を達成できます。

入力例 3

3 100
1
28 54 81

出力例 3

左から 2 番目の切れ目で分割すると、スコア 46 を達成できます。

入力例 4

3 100
2
28 54 81

出力例 4

入力例 5

20 1000
4
51 69 102 127 233 295 350 388 417 466 469 523 553 587 720 739 801 855 926 954

出力例 5

Source Name

「競プロ典型90問」1日目

B01 - A+B Problem

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

整数 A と B が与えられます。
A+B の値を出力してください。

制約

A は 1 以上 100 以下の整数
B は 1 以上 100 以下の整数

入力

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

A B

出力

答えを整数で出力してください。

入力例 1

1 2

出力例 1

1+2=3 です。

入力例 2

77 23

出力例 2

77+23=100 です。

入力例 3

100 100

出力例 3

100+100=200 です。

B02 - Divisor Check

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

A 以上 B 以下の整数のうち、100 の約数であるものは存在しますか。

制約

1 \leq A \leq B \leq 100
入力はすべて整数

入力

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

A B

出力

100 の約数が存在する場合 Yes、そうでない場合 No を出力してください。

入力例 1

5 20

出力例 1

Yes

たとえば、10 は 100 の約数です。

入力例 2

6 9

出力例 2

No

6 以上 9 以下の整数のうち、100 の約数であるものは存在しません。

B03 - Supermarket 1

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

N 個の商品があり、商品 i (i = 1, 2, \cdots, N) の価格は A_i 円です。
異なる 3 つの商品を選び、合計価格をピッタリ 1000 円にする方法は存在しますか。

制約

3 \leq N \leq 100
1 \leq A_i \leq 1000
入力はすべて整数

入力

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

N
A_1 A_2 \cdots A_N

出力

合計を 1000 円にする方法が存在する場合 Yes、そうでない場合 No と出力してください。

入力例 1

5
100 250 350 400 600

出力例 1

Yes

商品 2, 3, 4 を選んだ場合、合計価格は 250+350+400=1000 円になります。

入力例 2

10
50 150 250 350 450 550 650 750 850 950

出力例 2

No

合計価格を 1000 円にするような選び方は存在しません。

B04 - Binary Representation 2

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

2 進法表記で表された整数 N が与えられます。
N を 10 進法に変換した値を出力するプログラムを作成してください。

制約

N の長さは 1 文字以上 8 文字以下
N は 0 と 1 からなる
N の先頭の桁は 1 である

入力

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

出力

答えを整数で出力してください。

入力例 1

出力例 1

2 進法の 1101 を 10 進法に変換した値は 13 です。

入力例 2

出力例 2

2 進法の 1 を 10 進法に変換した値は 1 です。

入力例 3

出力例 3

2 進法の 100101 を 10 進法に変換した値は 37 です。

入力例 4

10000000

出力例 4

B06 - Lottery

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

太郎君はくじを N 回引き，i 回目の結果は A_i でした．A_i=1 のときアタリ，A_i=0 のときハズレを意味します．「L 回目から R 回目までの中では，アタリとハズレどちらが多いか？」という形式の質問が Q 個与えられるので，それぞれの質問に答えるプログラムを作成してください．

制約

1\leq N,Q\leq 10^5
0\leq A_i\leq 1
1\leq L_i\leq R_i\leq N
入力はすべて整数

入力

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

N
A_1 A_2 \cdots A_N
Q
L_1 R_1
\vdots
L_Q R_Q

出力

i=1,2,3,\ldots,Q それぞれについて，アタリの方が多い場合 win を，ハズレの方が多い場合 lose を，アタリとハズレが同じ場合 draw を，一行ずつ，総計 Q 行に出力してください．

入力例 1

7
0 1 1 0 1 0 0
3
2 5
2 7
5 7

出力例 1

win
draw
lose

B07 - Convenience Store 2

Time Limit: 6 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

あるコンビニは時刻 0 に開店し、時刻 T に閉店します。このコンビニには N 人の従業員が働いており、i 番目 (1 \leq i \leq N) の従業員は時刻 L_i に出勤し、時刻 R_i に退勤します。

t = 0, 1, 2, \dots, T-1 それぞれについて、時刻 t+0.5 にコンビニにいる従業員の数を出力するプログラムを作成してください。

制約

1 \leq T \leq 500\,000
1 \leq N \leq 500\,000
0 \leq L_i < R_i \leq T (1 \leq i \leq N)
入力はすべて整数

入力

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

T
N
L_1 R_1
\vdots
L_N R_N

出力

全体で T 行出力してください。

t + 1 行目 (0 \leq t \leq T-1) には、時刻 t+0.5 にコンビニにいる従業員の数を出力してください。

入力例 1

出力例 1

このコンビニは時刻 0 に開店し、時刻 10 に閉店します。従業員の出退勤の様子を図に表すと以下のようになります。

B08 - Counting Points

Time Limit: 5 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

二次元平面上に N 個の点があります．i 個目の点の座標は (X_i, Y_i) です．「x 座標が a 以上 c 以下であり，y 座標が b 以上 d 以下であるような点は何個あるか？」という形式の質問が Q 個与えられるので，それぞれの質問に答えるプログラムを実装してください．なお，入力される値はすべて整数です．

制約

1\leq N,Q\leq 100000
1\leq X_i, Y_i\leq 1500
1\leq a_i \leq c_i\leq 1500
1\leq b_i \leq d_i\leq 1500
入力はすべて整数

入力

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

N
X_1 Y_1
\vdots
X_N Y_N
Q
a_1 b_1 c_1 d_1
\vdots
a_Q b_Q c_Q d_Q

出力

Q 行にわたって出力してください．i 行目には，i 個目の質問の答えを出力してください．

入力例 1

出力例 1

5
2
4

B09 - Papers

Time Limit: 5 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

二次元平面上に N 枚の紙があります．それぞれの紙は，各辺が x 軸または y 軸に平行であるような長方形となっています．また，i 枚目の紙の左下座標は (A_i, B_i) であり，右上座標は (C_i, D_i) です．1 枚以上の紙が置かれている部分の面積を求めてください．なお，入力される値はすべて整数です．

制約

1\leq N\leq 100000
0\leq A_i < C_i\leq 1500
0\leq B_i < D_i\leq 1500
入力はすべて整数

入力

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

N
A_1 B_1 C_1 D_1
\vdots
A_N B_N C_N D_N

出力

答えを 1 行に出力してください．

入力例 1

2
1 1 3 3
2 2 4 4

出力例 1

B11 - Binary Search 2

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

小さい順に並んでいるとは限らない、要素数 N の配列 A = [A_1, A_2, \cdots, A_N] が与えられます。それについて、以下の Q 個の質問に答えるプログラムを作成してください。

i (1 \leq i \leq Q) 個目の質問：配列 A には X_i より小さい要素が何個あるか？

制約

1 \leq N, Q \leq 100000
1 \leq A_i \leq 10^9 (1 \leq i \leq N)
1 \leq X_i \leq 10^9 (1 \leq i \leq Q)
入力はすべて整数

入力

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

N
A_1 A_2 \cdots A_N
Q
X_1
X_2
\vdots
X_Q

出力

それぞれの質問に対する答えを、順番に Q 行出力してください。

入力例 1

15
83 31 11 17 32 19 23 37 43 47 53 61 67 5 55
5
10
20
30
40
50

出力例 1

入力例 2

出力例 2

5
2

B12 - Equation

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

正の整数 N が与えられます。x^3 + x = N を満たす正の実数 x を出力してください。ただし、相対誤差または絶対誤差が 0.001 以下であれば正解とします。

制約

1 \leq N \leq 100000
N は整数

入力

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

出力

答えを出力してください。絶対誤差または相対誤差が 0.001 未満であれば許容されます。

入力例 1

出力例 1

1.000000

B13 - Supermarket 2

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

KYOPRO 商店には N 個の品物が売られており、i 番目の品物は A_i 円です。連続する番号の品物を買う方法は全部で N(N+1)/2 通りありますが、この中で合計価格が K 円以内となるような買い方は何通りでしょうか。

制約

1 \leq N \leq 100\,000
1 \leq K \leq 10^9
1 \leq A_i \leq 10^9
入力はすべて整数

入力

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

N K
A_1 A_2 \cdots A_N

出力

合計価格が K 円以内となるような買い方が何通りかを求め、一行に出力してください。

入力例 1

7 50
11 12 16 22 27 28 31

出力例 1

B14 - Another Subset Sum

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

N 枚のカードがあり、i 枚目 (1 \leq i \leq N) のカードには整数 A_i が書かれています。カードの選び方は全部で 2^N 通りありますが、選んだカードの合計がちょうど K となるようにする方法は存在しますか。

制約

1 \leq N \leq 30
1 \leq K \leq 10^8
1 \leq A_i \leq 10^8
入力はすべて整数

入力

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

N　K
A_1　A_2　\cdots　A_N

出力

合計が K となる可能性がある場合 Yes、そうでない場合 No を出力してください。

入力例 1

6 30
5 1 18 7 2 9

出力例 1

Yes

5 + 18 + 7 = 30 なので、Yes を出力してください。

B16 - Frog 1

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

N 個の足場があります。足場には 1, 2, \ldots, N と番号が振られています。各 i (1 \leq i \leq N) について、足場 i の高さは h_i です。

最初、足場 1 にカエルがいます。カエルは次の行動を何回か繰り返し、足場 N まで辿り着こうとしています。

足場 i にいるとき、足場 i + 1 または i + 2 へジャンプする。このとき、ジャンプ先の足場を j とすると、コスト |h_i - h_j| を支払う。

カエルが足場 N に辿り着くまでに支払うコストの総和の最小値を求めてください。

制約

入力はすべて整数である。
2 \leq N \leq 10^5
1 \leq h_i \leq 10^4

入力

入力は以下の形式で標準入力から与えられる。

N
h_1 h_2 \ldots h_N

出力

カエルが支払うコストの総和の最小値を出力せよ。

入力例 1

4
10 30 40 20

出力例 1

足場 1 → 2 → 4 と移動すると、コストの総和は |10 - 30| + |30 - 20| = 30 となります。

入力例 2

2
10 10

出力例 2

足場 1 → 2 と移動すると、コストの総和は |10 - 10| = 0 となります。

入力例 3

6
30 10 60 10 60 50

出力例 3

足場 1 → 3 → 5 → 6 と移動すると、コストの総和は |30 - 60| + |60 - 60| + |60 - 50| = 40 となります。

Score : 100 points

Problem Statement

There are N stones, numbered 1, 2, \ldots, N. For each i (1 \leq i \leq N), the height of Stone i is h_i.

There is a frog who is initially on Stone 1. He will repeat the following action some number of times to reach Stone N:

If the frog is currently on Stone i, jump to Stone i + 1 or Stone i + 2. Here, a cost of |h_i - h_j| is incurred, where j is the stone to land on.

Find the minimum possible total cost incurred before the frog reaches Stone N.

Constraints

All values in input are integers.
2 \leq N \leq 10^5
1 \leq h_i \leq 10^4

Input

Input is given from Standard Input in the following format:

N
h_1 h_2 \ldots h_N

Output

Print the minimum possible total cost incurred.

Sample Input 1

4
10 30 40 20

Sample Output 1

If we follow the path 1 → 2 → 4, the total cost incurred would be |10 - 30| + |30 - 20| = 30.

Sample Input 2

2
10 10

Sample Output 2

If we follow the path 1 → 2, the total cost incurred would be |10 - 10| = 0.

Sample Input 3

6
30 10 60 10 60 50

Sample Output 3

If we follow the path 1 → 3 → 5 → 6, the total cost incurred would be |30 - 60| + |60 - 60| + |60 - 50| = 40.

B17 - Frog 1 with Restoration

Time Limit: 1 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

N 個の足場があります。足場には 1, 2, …, N と番号が振られています。各 i (1≤i≤N) について、足場 i の高さは h_i です。

最初、足場 1 にカエルがいます。カエルは次の行動を何回か繰り返し、足場 N まで辿り着こうとしています。

足場 i にいるとき、足場 i+1 または i+2 へジャンプする。このとき、ジャンプ先の足場を j とすると、コスト |h_i - h_j| を支払う。

カエルが足場 N に辿り着くまでに支払うコストの総和が最小になる移動方法を 1 つ出力するプログラムを作成してください。

制約

2 ≤ N ≤ 100\,000
1 ≤ h_i ≤ 10\,000 (1 ≤ i ≤ N)
入力される値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

N
h_1 h_2 \cdots h_N

出力

足場 P_1 → 足場 P_2 → ･･･ → 足場 P_K という経路で移動する場合、以下の形式で出力してください。特に、P_1=1、P_K=N でなければならないことに注意してください。

K
P_1 P_2 \cdots P_K

入力例 1

4
10 30 40 20

出力例 1

3
1 2 4

入力例 2

2
10 10

出力例 2

2
1 2

入力例 3

6
30 10 60 10 60 50

出力例 3

4
1 3 5 6

B18 - Subset Sum with Restoration

Time Limit: 1 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

N 枚のカードが一列に並べられており、左から i 番目のカード（以下、カード i とする）には整数 A_i が書かれています。カードの中からいくつかを選んで、書かれた整数の合計が S となるようにする方法が存在するか判定し、存在する場合はその方法を 1 つ求めてください。

制約

1 \leq N \leq 60
1 \leq S \leq 10\,000
1 \leq A_i \leq 10\,000
入力される値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

N S
A_1 A_2 \cdots A_N

出力

カードの中からいくつかを選んで、書かれた整数の合計が S となるようにする方法が存在する場合、選ぶカードの番号を P_1, P_2, …, P_K として以下の形式で出力してください。

K
P_1 P_2 \cdots P_K

そのような方法が存在しない場合、-1 を出力してください。

入力例 1

3 7
2 2 3

出力例 1

3
1 2 3

カード 1・カード 2・カード 3 を選んだ場合、書かれた整数の合計は 2+2+3=7 となります。

入力例 2

3 10
1 2 4

出力例 2

-1

入力例 3

10 100
14 23 18 7 11 23 23 5 8 2

出力例 3

6
2 3 6 7 8 9

B19 - Knapsack 2

Time Limit: 10 sec / Memory Limit: 1024 MB

配点: 1000 点

この問題は、Educational DP Contest E - Knapsack 2 と同じ問題です。

問題文

宝箱には N 個の品物が入っており、それぞれ 1 から N までの番号が付けられています。
品物 i の重さは w_i であり、価値は v_i です。

制約

1 \leq N \leq 100
1 \leq W \leq 10^9
1 \leq w_i \leq W
1 \leq v_i \leq 1000
入力はすべて整数

入力

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

N W
w_1 v_1
w_2 v_2
 :
w_N v_N

出力

答えを整数で出力してください。

入力例 1

出力例 1

たとえば品物 1・品物 2・品物 4 を選んだ場合、価値の合計は 13+17+10=40 となります。
価値の合計を 41 以上にする方法は存在しません。

入力例 2

出力例 2

品物 1・品物 3 を選ぶのが最適です。

入力例 3

10 1000000000
80000000 99
11000000 119
12000000 150
15000000 174
16000000 168
18000000 190
19000000 187
25000000 273
28000000 307
30000000 319

出力例 3

B20 - Edit Distance

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

文字列 S と T が与えられます。
あなたは、文字列 S に対して以下の 3 種類の操作を行うことができます。

操作1：S 中の文字を 1 つ選び、削除する。
操作2：S 中の文字を 1 つ選び、別の文字に変更する。
操作3：S 中の適当な位置に、文字を 1 つ挿入する。

最小何回の操作で、文字列 S を T に一致させることができますか。

制約

S の文字数は 1 以上 2000 以下
T の文字数は 1 以上 2000 以下
S, T は英小文字からなる

入力

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

S
T

出力

答えを整数で出力してください。

入力例 1

tokyo
kyoto

出力例 1

以下のような 4 回の操作を行うことで、tokyo を kyoto にすることができます。

1 文字目を削除する：okyo になる。
1 文字目を削除する：kyo になる。
3 文字目の後に t を追加：kyot になる。
4 文字目の後に o を追加：kyoto になる。

入力例 2

competitive
programming

出力例 2

入力例 3

abcdef
bdf

出力例 3

B21 - Longest Subpalindrome

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

太郎君は、長さ N の文字列 S に対して以下の操作を行うことで、回文を作りたいです。

S の中から（連続するとは限らない）文字を取り除く。
残った文字を順番通りに連結する。

最長何文字の回文を作ることができるか、出力するプログラムを作成してください。

制約

1 \leq N \leq 1000
文字列 S は英小文字からなる

入力

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

N
S

出力

最長何文字の回文を作ることができるか、整数で出力してください。

入力例 1

11
programming

出力例 1

4, 7, 8, 11 文字目のみを残すと、gmmg という回文を作ることができます。

入力例 2

7
abcdcba

出力例 2

何も取り除かなくても回文になります。

B23 - Traveling Salesman Problem

Time Limit: 10 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

二次元平面上に N 個の都市があり、それぞれ 1 から N までの番号が付けられています。
都市 i の座標は (X_i, Y_i) であり、2 つの都市間を移動するには、直線距離と同じだけ時間がかかります。
すなわち、都市 i から j まで移動するのに、\sqrt{(X_i - X_j)^2 + (Y_i - Y_j)^2} 分かかります。

ある都市から出発し、すべての都市を一度ずつ通った後、出発地点に戻るためには最短何分必要でしょうか。

制約

2 \leq N \leq 15
0 \leq X_i \leq 1000
0 \leq Y_i \leq 1000
入力はすべて整数

入力

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

N
X_1 Y_1
X_2 Y_2
 :
X_N Y_N

出力

答えを出力してください。
絶対誤差または相対誤差が 10^{-3} 未満であれば、正解として扱われます。

入力例 1

出力例 1

4.000000000000

都市 1 \to 2 \to 4 \to 3 \to 1 というルートを通ると、合計距離が約 4 となります。

入力例 2

出力例 2

18.870481592668

都市 1 \to 2 \to 4 \to 3 \to 5 \to 6 \to 7 \to 1 というルートを通ると、合計距離が約 18.87 となります。

B24 - Many Boxes

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

N 個の箱があります。i 個目の箱の縦の長さは X_i であり、横の長さは Y_i です。
以下の 2 つの条件両方を満たすとき、箱 A を箱 B の中に入れることができます。

(箱 A の縦の長さ) < (箱 B の縦の長さ)
(箱 A の横の長さ) < (箱 B の横の長さ)

箱は最大で何重にすることができますか。
ただし、箱を回転させて縦の長さと横の長さを逆にする操作はできないものとします。

制約

1 \leq N \leq 100000
1 \leq X_i \leq 500000
1 \leq Y_i \leq 500000
入力はすべて整数

入力

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

N
X_1 Y_1
X_2 Y_2
 :
X_N Y_N

出力

答えを整数で出力してください。

入力例 1

出力例 1

外側から順に「箱 5, 1, 2」と置くことで、箱を 3 重にすることができます。

入力例 2

出力例 2

B26 - Output Prime Numbers

Time Limit: 1 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

N 以下の素数を値の小さい方から全て出力してください。

制約

N は 2 以上 1000000=(10^6) 以下の整数

入力

入力は以下の形式で標準入力から与えられる。

出力

N 以下の素数を 1 行に 1 つ、値の小さい方から順に出力してください。

入力例 1

出力例 1

B27 - Calculate LCM

Time Limit: 1 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

整数 A と B の最小公倍数（ A,B 両方の倍数であるような正の整数 x のうち最小のもの）を出力してください。

制約

A,B は整数
1 \le A,B \le 10^9

入力

入力は以下の形式で標準入力から与えられる。

A B

出力

答えを整数として出力せよ。

入力例 1

25 30

出力例 1

入力例 2

998244353 998244853

出力例 2

996492287418565109

答えは 32bit 符号付き整数に収まらない可能性があります。

B28 - Fibonacci Easy (mod 1000000007)

Time Limit: 10 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

以下の漸化式で定められるフィボナッチ数列の第 N 項 a_N を 1000000007 (=10^9+7) で割った余りを求めてください。

a_1 = 1, a_2 = 1
a_n = a_{n-1} + a_{n-2} (n \geq 3)

制約

3 \le N \le 10^7
N は整数

入力

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

出力

答えを整数で出力してください。

入力例 1

出力例 1

a=(1,1,2,3,5,8,\dots) です。
N=6 なので、第 6 項である 8 を出力してください。

入力例 2

出力例 2

922041576

1000000007 で割った余りを求めることに注意してください。

B29 - Power Hard

Time Limit: 1 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

a^b を 1000000007 で割った余りを出力せよ。

制約

a,b は整数
1 \le a \le 10^9
1 \le b \le 10^{18}

入力

入力は以下の形式で標準入力から与えられる。

a b

出力

答えを整数として出力せよ。

入力例 1

6 3

出力例 1

入力例 2

123456789 123456789012345678

出力例 2

1000000007 で割った余りを出力してください。

B30 - Combination 2

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

縦 H 行・横 W 列のマス目があります。上から i 行目・左から j 列目のマスを (i, j) とするとき、マス (1, 1) から出発し、右方向か下方向の移動を繰り返して、マス (H, W) まで行く方法は何通りありますか。

制約

1 \leq H \leq 100000
1 \leq W \leq 100000
入力はすべて整数

入力

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

H W

出力

答えを 1000000007 で割った余りを出力してください。

入力例 1

1 2

出力例 1

入力例 2

5 10

出力例 2

入力例 3

869 120

出力例 3

223713395

答えを 1000000007 で割った余りを出力してください。

B31 - Divisors Hard

Time Limit: 1 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

1 以上 N 以下の整数のうち、 3,5,7 のいずれかで割り切れるものは何個ありますか。

制約

N は 1 以上 10^{12} 以下の整数

入力

入力は以下の形式で標準入力から与えられる。

出力

答えを整数として出力してください。

入力例 1

出力例 1

10 以下の整数のうち 3,5,7 のいずれかで割り切れるものは、 3,5,6,7,9,10 の 6 個です。

入力例 2

出力例 2

入力例 3

100000000000

出力例 3

54285714286

B32 - Game 5

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

N 個の石が積まれた山があり、プレイヤー 2 人が交互に石を取り合います。
各プレイヤーが 1 回のターンで取る石の数は、 a_1,a_2,\dots,a_K 個のいずれかでなければなりません。
先に石を取り除けなくなった方が負けとするとき、先手と後手どちらが勝ちますか。

制約

入力は全て整数
1 \le N \le 100000
1 \le K \le 100
1 \le a_i \le 100000
a_i は相異なる

入力

入力は以下の形式で標準入力から与えられる。

N K
a_1 a_2 \dots a_K

出力

先手が勝つ場合は First 、後手が勝つ場合は Second と出力してください。

入力例 1

8 2
2 3

出力例 1

First

入力例 2

6 2
2 3

出力例 2

Second

入力例 3

20 3
6 1 3

出力例 3

Second

B33 - Game 6

Time Limit: 1 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

H \times W のマス目に N 個のコマが置かれています。
i 個目のコマは上から A_i 行目、左から B_i 列目のマスに存在します。
太郎君と次郎君は交互に、「 1 つのコマを選んで左方向か上方向に 1 マス以上移動させる」という操作を行います。
同じ位置に複数のコマを置くことも許されます。
操作を行えなくなった方が負けであるとき、どちらが勝ちますか。

制約

入力は全て整数
1 \le N \le 100000
1 \le H,W \le 10^9
1 \le A_i \le H
1 \le B_i \le W

入力

入力は以下の形式で標準入力から与えられる。

N H W
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

先手が勝つ場合は First 、後手が勝つ場合は Second と出力してください。

入力例 1

1 3 5
2 4

出力例 1

First

入力例 2

2 8 4
6 4
7 1

出力例 2

Second

B34 - Game 7

Time Limit: 1 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

この問題は A34：Game 3 と制約のみが異なる問題です。制約欄をよくお読みください。
石の山が N 個あり、山 i(1 \le i \le N) には A_i 個の石が積まれています。
このゲームでは、 2 人のプレイヤーが交互に次の操作を行います。

好きな石の山を 1つ選び、選んだ山から X 個または Y 個の石を取る。

すべての山にある石の数が X 個未満になり、操作を行えなくなった方が負けです。
両者が最善を尽くしたとき、先手と後手どちらが勝ちますか。

制約

入力は全て整数
1 \le N \le 100000
\color{red}{X=2}
\color{red}{Y=3}
1 \le A_i \le \color{red}{10^{18}}

入力

入力は以下の形式で標準入力から与えられる。

N X Y
A_1 A_2 \dots A_N

出力

先手が勝つ場合は First 、後手が勝つ場合は Second と出力してください。

入力例 1

2 2 3
5 8

出力例 1

First

入力例 2

2 2 3
7 8

出力例 2

Second

B36 - Switching Lights

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

N 個の豆電球があり、i 個目の豆電球は S_i (S の i 文字目) が '1' のとき ON、'0' のとき OFF になっています。

あなたは、以下の操作を何回でも行えます。

2 個の異なる豆電球を選び、ON／OFF の状態を反転させる。

ちょうど K 個の豆電球が ON になっている状態にすることが可能であるかどうかを判定してください。

制約

2 \leq N \leq 3 \times 10^5
0 \leq K \leq N
S は '1' および '0' のみからなる N 文字の文字列

入力

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

N K
S

出力

問題文で指定された状態にすることが可能である場合は 'Yes'、不可能である場合は 'No' を出力してください。

入力例 1

7 3
1010111

出力例 1

Yes

7 個の豆電球のうち 5 個が ON になっています。
ON になっている豆電球を 2 個選んで反転させる（OFF に切り替える）ことで、3 個の豆電球が ON になっている状態にすることができます。

入力例 2

10 6
0001010001

出力例 2

No

入力例 3

2 2
11

出力例 3

Yes

はじめから 2 個の豆電球が ON になっています。
このような場合、一度も操作を行わなくてもかまいません。

B37 - Sum of Digits

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

この問題は、同じ節の例題（A37）と比べて難易度が高いです。ヒントも用意していますが、難しいと思ったら飛ばしても構いません。

整数 x の各桁の和を f(x) とします。たとえば、f(288)=2+8+8=18 です。

f(1)+f(2)+\dots+f(N) の値を求めてください。

ヒントについて

解説ページにヒントがあります。考察に詰まったらご活用ください。ヒント1 から順番に読んで、各ヒントまでの段階で考えてみることをおすすめします。

制約

1 \leq N < 10^{15}
N は整数

入力

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

出力

答えを整数で出力してください。

入力例 1

出力例 1

f(1) + f(2) + f(3) + f(4) = 1+2+3+4 = 10 です。

入力例 2

出力例 2

B38 - Heights of Grass

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

N 個の草が一列に並んでおり、1 から N までの番号が付けられています。各草の高さは 1 以上の整数値で表され、それについて次の情報 S_1,S_2,\cdots,S_{N-1} が分かっています。

S_i = 'A' のとき: 草 i より草 i + 1 の方が真に高い
S_i = 'B' のとき: 草 i より草 i + 1 の方が真に低い

N 個の草の高さの合計として考えられる最小値を出力してください。

制約

1 \leq N \leq 3000
N は整数
S は 'A' および 'B' のみからなる N-1 文字の文字列

入力

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

N
S

出力

答えを整数で出力してください。

入力例 1

7
AABBBA

出力例 1

草の高さがそれぞれ 1, 2, 4, 3, 2, 1, 2 となっている状態が、草の高さの合計が最小となります。

B39 - Taro's Job

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 1000 点

重要：この問題は、書籍『競技プログラミングの鉄則』の 6.4 節と 8.3 節で二度扱っています。 6.4 節の解法では、部分点しか取れない可能性があることに注意してください（8.3 節の解法では満点を取ることができます）

問題文

太郎君は今日から D 日間、仕事をしようと思いました。仕事の選択肢は N 個あり、i 個目の仕事は X_i 日目以降になれば選ぶことができ、完了すれば Y_i 円もらえます。 1 つの仕事をするのに 1 日かかるとき、太郎君は最大何円を稼ぐことが出来ますか。

制約

1 \leq N \leq 2 \times 10^5
1 \leq D \leq 2000
1 \leq X_i \leq D
1 \leq Y_i \leq 10^6
入力はすべて整数

(2022/10/05 2:00 追記) D の制約を 365 から 2000 に引き上げ、テストケースを再作成しています。

部分点

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

入力

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

N D
X_1 Y_1
\vdots
X_N Y_N

出力

答えを整数で出力してください。

入力例 1

出力例 1

1 個目、2 個目、4 個目、3 個目の順に仕事をすると 1+4+4+3=12 円得ることができ、これが最大です。

B40 - Divide by 100

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

長さ N の配列 A = [A_1, \dots ,A_N] が与えられます。 1 \leq x < y \leq N かつ A_x + A_y の値が 100 の倍数であるような組 (x,y) の個数はいくつありますか。

制約

1 \leq N \leq 2 \times 10^5
1 \leq A_i \leq 10^9 (1 \leq i \leq N)
入力はすべて整数

入力

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

N
A_1 A_2 \cdots A_N

出力

答えを整数で出力してください。

入力例 1

9
10 20 30 40 50 60 70 80 90

出力例 1

(1, 9), (2, 8), (3, 7), (4, 6) が条件を満たします。

B41 - Reverse of Euclid

Time Limit: 10 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

変数 x, y があり、最初は両方の値が 1 です。以下の 2 種類の操作を何回か行うことで、変数 x の値を X, 変数 y の値を Y にする方法を求めてください。

x の値を x + y に変更する
y の値を x + y に変更する

ただし X と Y の最大公約数は 1 であるとします。

制約

1 \leq X, Y \leq 10^6
X と Y の最大公約数は 1 である

入力

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

X Y

出力

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

K
x_1 y_1
x_2 y_2
\vdots
x_K y_K

ここで、K は操作回数、x_i, y_i は i 回目の操作後の x, y の値を表します。

入力例 1

5 2

出力例 1

1 回目の操作では y の値を x + y に変更します。x, y は 1, 2 になります
2 回目の操作では x の値を x + y に変更します。x, y は 3, 2 になります
3 回目の操作では x の値を x + y に変更します。x, y は 5, 2 になります

入力例 2

1 1

出力例 2

B42 - Two Faced Cards

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

N 枚のカードがあり、i 枚目のカードの表には整数 A_i 、裏には整数 B_i が書かれています。太郎君はカードを何枚か選び、以下で定義されるスコアを最大にしたいです。

[スコア]=[選んだカードにおける表の総和の絶対値]
       +[選んだカードにおける裏の総和の絶対値]

スコアとして考えられる最大値はいくつでしょうか。

制約

1 \leq N \leq 100000
-10^9 \leq A_i, B_i \leq 10^9 \ (1 \leq i \leq N)

入力

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

N
A_1 B_1
\vdots
A_N B_N

出力

答えを整数で出力してください。

入力例 1

出力例 1

2 枚目のカード、3 枚目のカード、5 枚目のカードを選ぶことで、スコアが |4 + 5 - 2| + |-5 - 3 - 3| = 18 となり、これがスコアの最大値です。

B43 - Quiz Contest

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

N 人の生徒がクイズ大会に参加しました。この大会では M 問が出題され、i 問目では A_i 番目の生徒を除く全員が正解しました。

各生徒の最終的な正解数を求めるプログラムを作成してください。

制約

1 \leq N, M \leq 200000
1 \leq A_i \leq N \ (1 \leq i \leq M)

入力

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

N M
A_1 A_2 \cdots A_M

出力

N 行にわたって出力してください。k 行目には、k 番目の生徒の最終的な正解数を出力してください。

入力例 1

4 6
1 4 1 4 2 1

出力例 1

B44 - Grid Operations

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

N \times N のマス目があり、上から i 行目・左から j 列目のマス (i, j) には整数 A_{i, j} が書かれています。以下の 2 種類の操作を処理するプログラムを作成してください。

交換操作：整数 x, y が与えられるので、x 行目と y 行目を交換する
取得操作：整数 x, y が与えられるので、マス (x, y) に書かれた整数を答える

制約

1 \leq N \leq 500
1 \leq Q \leq 200000
1 \leq A_{i, j} \leq 100

入力

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

Query_i は i 回目の操作を表し、交換操作の場合は 1 x y、取得操作の場合は 2 x y という形式で与えられます。

N
A_{1, 1} A_{1, 2} \cdots A_{1, N}
\vdots
A_{N, 1} A_{N, 2} \cdots A_{N, N}
Q
Query_1
\vdots
Query_Q

出力

取得操作に対する答えを順番に出力してください。

入力例 1

出力例 1

マス目は次のように変化します。

最初の状態:

1 2 3
4 5 6
7 8 9

2 回目の操作 1 1 2 により 1 行目と 2 行目が交換された後の状態:

4 5 6
1 2 3
7 8 9

5 回目の操作 1 2 3 により 2 行目と 3 行目が交換された後の状態:

4 5 6
7 8 9
1 2 3

入力例 2

出力例 2

32
8

B45 - Blackboard 2

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

黒板に 3 つの整数 a, b, c が書かれています。「3 つ中 2 つの整数を選び、片方に +1、もう片方に -1 する」という操作を何回か行い、書かれた整数を全部 0 にすることはできますか。

制約

-10^{18} \leq a, b, c \leq 10^{18}

入力

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

a b c

出力

黒板に書かれた整数を全部 0 にすることができるとき Yes、そうでないとき No を出力してください。

入力例 1

3 -4 1

出力例 1

Yes

(a, b, c) を次のように変化させることができるため Yes を出力します。

(3, -4, 1) \rightarrow (2, -3, 1) \rightarrow (1, -2, 1) \rightarrow (0, -1, 1) \rightarrow (0, 0, 0)

B51 - Bracket

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

対応の取れているカッコ列 S があります。 S の何文字目と何文字目が対応しているかを、全て出力してください。たとえば、(())() の場合、「1 文字目と 4 文字目」、「2 文字目と 3 文字目」、「5 文字目と 6 文字目」が対応しています。

ここで、対応の取れているカッコ列は以下のいずれかの条件を満たしている空でない文字列です。

()
対応の取れているカッコ列 A が存在し、 (, A, )をこの順に結合した文字列
対応の取れているカッコ列 A,B が存在し、A,B をこの順に結合した文字列

入力

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

出力

|S| を S の長さと表したとき、カッコの対応を以下の形式にしたがって |S|/2 行で出力せよ。

l_1 r_1
:
l_{|S|/2} r_{|S|/2}

これは、「l_1 文字目と r_1 文字目」, ... ,「l_{|S|/2} 文字目と r_{|S|/2} 文字目」が対応していることを表します。

出力は以下の条件を満たす必要があります。

1 \leq l_i < r_i \leq |S| \ (1 \leq i \leq |S|/2)
\text{max}(l_i, r_i) < \text{max}(l_{i + 1}, r_{i + 1}) \ (1 \leq i \leq |S|/2 - 1)

制約

1 \leq |S| \leq 200,000
S は()の文字から構成される対応の取れたカッコ列

入力例 1

(())()

出力例 1

2 3
1 4
5 6

B52 - Ball Simulation

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

N 個のボールが一列に並べられています。これらのボールの最初の色は文字列 A で与えられます。

ボール i の色は A の i 文字目で表されており、黒の時 A_i は #、白の時 A_i は .　となっています。

以下のシミュレーションを行うとき、最終的なボールの色はどうなりますか。

まず、キューに整数 X を追加し、ボール X を青で塗る。
その後、キューが空になるまで以下の操作を繰り返す。
- キューの先頭要素 (\text{pos}) を削除する
- ボール \text{pos}-1 が白のとき、これを青で塗り、キューに \text{pos}-1 を追加する
- ボール \text{pos}+1 が白のとき、これを青で塗り、キューに \text{pos}+1 を追加する

入力

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

N X
A

出力

シミュレーションを行った後のボールの色を長さN の文字列として出力してください。

出力する文字列の i 文字目は、ボール i の色が黒の時は #、白の時は .、青の時は @ としてください。

制約

1 \leq N \leq 100,000
1 \leq X \leq N
A は #. からなる文字列
ボール X は白

入力例 1

5 3
#...#

出力例 1

#@@@#

B54 - Counting Same Values

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

整数 A_1, A_2, \cdots, A_N が与えられます。

1 \leq j < i \leq N かつ A_j = A_i を満たすような組 (i, j) は全部でいくつありますか。

入力

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

N
A_1
:
A_N

出力

問題文の条件を満たす (i, j) の組が何通りあるか出力してください。

制約

1 \leq N \leq 100,000
1 \leq A_i \leq 10^9 (1 \leq i \leq N)

入力例 1

出力例 1

B55 - Difference

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

以下の 2 種類のクエリを高速に処理するプログラムを実装してください。

クエリ 1：x と書かれたカードが机に置かれる。
クエリ 2：整数 x と「机にあるカード」の差の絶対値の最小値を答える。

ただし、最初の時点では机の上に 1 個もカードが置かれていないものとします。

入力

Query_i は i 回目のクエリの情報を表します。クエリ 1 の場合は 1 x、クエリ 2 の場合は 2 x という形式で与えられます。

詳しくは入力例をご覧ください。

Q
Query_1
:
Query_Q

出力

クエリ 2 の答えを、順番に出力してください。ただし、机の上にカードが存在しないクエリについては、-1 と出力してください。

制約

1 \leq Q \leq 100,000
1 \leq x \leq 10^9
クエリ 1 では、既に置かれているカードが追加されることはない

入力例 1

出力例 1

-1
20
10

B56 - Palindrome Queries

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

回文とは、前から読んでも後ろから読んでも変わらない文字列のことを指します。たとえば abba や level は回文です。

長さ N の文字列 S が与えられます。以下の Q 個のクエリに答えてください。

i 個目のクエリ：S[L_i, R_i] は回文か？

ただし、S[l, r] は S の l 文字目から r 文字目までの連続部分文字列のことを指します。

制約

N, Q, L_i, R_i は整数である
S は英小文字からなる文字列である
1 \leq N \leq 100000
1 \leq Q \leq 100000
|S| = N
1 \leq L_i \leq R_i \leq N

入力

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

N Q
S
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q

出力

Q 行にわたって出力してください。i 行目には、i 個目のクエリで回文である場合 Yes、そうでない場合 No と出力してください。

入力例 1

11 3
mississippi
5 8
6 10
2 8

出力例 1

Yes
No
Yes

1 個目のクエリでは、S[5, 8] = issi が回文かどうか聞かれています。これは回文なので、Yes と出力します。

2 個目のクエリでは、S[6, 10] = ssipp が回文かどうか聞かれています。これは回文ではないので、No と出力します。

B57 - Calculator

Time Limit: 4 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

1, 2, \ldots, N それぞれに対して、次の操作を K 回行った後の整数を求めてください。

十進法で表したときの各位の数字の和を、自身から引く。

たとえば 108 に対して 3 回の操作を行うと、108 \rightarrow 99 \rightarrow 81 \rightarrow 72 と変化します。

制約

入力はすべて整数である
1 \leq N \leq 300000
1 \leq K \leq 10^9

入力

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

N K

出力

N 行出力してください。i 行目には、整数 i に操作を K 回行った後の整数を出力してください。

入力例 1

10 1

出力例 1

B58 - Jumping

Time Limit: 2.5 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

N 個の足場が横一列に並んでおり、左から順に 1 から N までの番号が付けられています。足場 1 がスタート地点、足場 N がゴール地点であり、足場 i はスタート地点から X_i メートルの位置にあります。

あなたは 1 回で L メートル以上 R メートル以下の距離を右方向にのみジャンプできるとき、スタートからゴールまで最小何回のジャンプで行けますか。ただし、与えられる入力において、スタートからゴールまで到達できることが保証されます。

制約

入力はすべて整数である
2 \leq N \leq 100000
1 \leq L \leq R \leq 10^9
0 = X_1 < X_2 < \cdots < X_N \leq 10^9
与えられる入力において、スタートからゴールまで到達可能である

入力

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

N L R
X_1 X_2 \ldots X_N

出力

答えを出力してください。

入力例 1

5 20 40
0 20 30 60 70

出力例 1

まず 30 メートルの距離をジャンプして足場 3 に行き、次に 40 メートルの距離をジャンプして足場 5 に行くのが最適です。

B59 - Number of Inversions

Time Limit: 4 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

長さ N の数列 A = (A_1, A_2, \ldots, A_N) が与えられます。1 \leq i < j \leq N かつ A_i > A_j を満たす整数の組 (i, j) の個数を求めてください。

制約

入力はすべて整数である
1 \leq N \leq 150000
\bm{A} は \bm{(1, 2, \ldots, N)} を並べ替えた順列である

入力

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

N
A_1 A_2 \ldots A_N

出力

答えを出力してください。

入力例 1

4
2 4 1 3

出力例 1

(i, j) = (1, 3), (2, 3), (2, 4) の 3 つが条件を満たします。

入力例 2

7
3 6 4 5 7 1 2

出力例 2

B61 - Influencer

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

情報大学の 1 年 A 組には N 人の生徒が在籍しており、1 から N までの番号が付けられています。このクラスには M 個の友達関係があり、各 i\ (1 \leq i \leq M) について、生徒 A_i と生徒 B_i が互いに友達です。

最も友達の多い生徒の番号を出力するプログラムを作成してください。該当者が複数いる場合はどれを出力しても正解となります。

制約

2 \leq N \leq 100000
1 \leq M \leq 100000
1 \leq A_i \lt B_i \leq N\ (1\leq i\leq M)
i \neq j \implies (A_i,B_i) \neq (A_j,B_j)
入力は全て整数

入力

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

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

最も友達の多い生徒の番号を 1 行に出力してください。

入力例 1

出力例 1

入力例 2

出力例 2

B62 - Print a Path

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

頂点数 N、辺数 M の連結なグラフが与えられます。このグラフについて、頂点 1 から頂点 N までの単純パスを一つ出力してください。

制約

2 \leq N \leq 100000
1 \leq M \leq 100000
1 \leq A_i \lt B_i \leq N\ (1\leq i\leq M)
i \neq j \implies (A_i,B_i) \neq (A_j,B_j)
与えられるグラフは連結
入力は全て整数

入力

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

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

次の形式で答えを 1 行に出力してください。

v_1 v_2 \cdots v_k

(v_1,v_2,\ldots,v_k) は与えられたグラフにおける頂点 1 から頂点 N への単純パスになっていなければなりません。形式的には、(v_1,v_2,\ldots,v_k) が満たすべき条件は以下のようになります。

v_1=1,v_k=N
i\neq j\implies v_i\neq v_j
与えられたグラフには辺 (v_i,v_{i+1}) が存在する (1\leq i\lt k)

入力例 1

出力例 1

1 2 3 5

与えられるグラフは次のようになります。

入力例 2

出力例 2

1 4 6 9 11 15

1 9 15 や 1 6 5 15 と出力しても正解となります。

B63 - 幅優先探索

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

たかはし君は迷路が好きです。今、上下左右に移動できる二次元盤面上の迷路を解こうとしています。盤面は以下のような形式で与えられます。

まず、盤面のサイズと、迷路のスタート地点とゴール地点の座標が与えられる。
次に、それぞれのマスが通行可能な空きマス(.)か通行不可能な壁マス(#)かという情報を持った盤面が与えられる。盤面は壁マスで囲まれている。スタート地点とゴール地点は必ず空きマスであり、スタート地点からゴール地点へは、空きマスを辿って必ずたどり着ける。具体的には、入出力例を参考にすると良い。

今、彼は上記の迷路を解くのに必要な最小移動手数を求めたいと思っています。どうやって求めるかを調べていたところ、「幅優先探索」という手法が効率的であることを知りました。幅優先探索というのは以下の手法です。

スタート地点から近い(たどり着くための最短手数が少ない)マスから順番に、たどり着く手数を以下のように確定していく。説明の例として図1の迷路を利用する。

図1. 説明に用いる盤面

最初に、スタート地点は、スタート地点から手数0でたどり着ける(当然)ので、最短手数0で確定させる(図2)。

図2. 最短手数0でたどり着けるマスが確定(初期)

次に、スタート地点の四近傍(上下左右)の空きマスについて、手数1で確定させる(図3)。

図3. 最短手数1でたどり着けるマスが確定

次に、手数1で確定したそれぞれのマスの4近傍を見て、まだ確定していない空きマスがあればそのマスを手数2で確定させる(図4)。

図4. 最短手数2でたどり着けるマスが確定

次に、手数2で確定したそれぞれのマスの4近傍を見て、まだ確定していない空きマスがあればそのマスを手数3で確定させる(図5)。

図5. 最短手数3でたどり着けるマスが確定

次に、手数3で確定したそれぞれのマスの4近傍を見て、まだ確定していない空きマスがあればそのマスを手数4で確定させる(図6)。

図6. 最短手数4でたどり着けるマスが確定

上記の手順を確定の更新が無くなるまで繰り返すと、スタート地点からたどり着ける全ての空きマスについて最短手数が確定する(図7)。スタートとゴールは必ず空きマスを辿ってたどり着けるという制約があるので、ゴール地点への最短手数も分かる。

図7. すべてのたどり着けるマスへの最短手数が確定

さて、この処理をスマートに実装するためには、先入れ先出し(FIFO)のキュー(Queue)というデータ構造を用いると良いことが知られています。もちろん、使わなくても解くことは可能です。今回、よく分からなければ思いついた方法で解くことをおすすめします。先入れ先出しのキューとは以下のような機能を持つデータ構造です。

追加(Push): キューの末尾にデータを追加する。
取り出し(Pop): キューの先頭のデータを取り出す。

このデータ構造を使うと、先ほどの幅優先探索の説明における「マスの最短手数の確定」のタイミングでその確定マスをキューに追加し、追加操作が終わればPopを行い、取り出したマスの4近傍を調べるということを繰り返せば(つまり先に追加されたものから順番に処理していけば)、簡潔に処理ができることが分かります。

入力

入力は以下の形式で標準入力から与えられる。

R\ C
sy\ sx
gy\ gx
c_{(1,1)}c_{(1,2)}\ …\ c_{(1,C)}
c_{(2,1)}c_{(2,2)}\ …\ c_{(2,C)}
:
c_{(R,1)}c_{(R,2)}\ …\ c_{(R,C)}

1 行目には、行数 R(1≦R≦50)と列数 C(1≦C≦50)がそれぞれ空白区切りで与えられる。
2 行目には、スタート地点の座標 (sy,sx) が空白区切りで与えられる。スタート地点が sy 行 sx 列にあることを意味する。 1≦sy≦R　かつ 1≦sx≦C である。
3 行目には、ゴール地点の座標 (gy,gx) が空白区切りで与えられる。ゴール地点が gy 行 gx 列にあることを意味する。 1≦gy≦R　かつ 1≦gx≦C であり、(gy,gx)≠(sy,sx)であることが保障されている。
4 行目から R 行、長さ C の文字列が 1 行ずつ与えられる。各文字は . もしくは # のいずれかであり、i 回目 (1≦i≦R) に与えられられる文字列のうち j 文字目 (1≦j≦C) について、その文字が . なら、マス (i,j) が空きマスであり、# なら、マス (i,j) が壁マスであることをあらわす。
盤面は壁マスで囲まれている。つまり、i=1,i=R,j=1,j=C のうちいずれか1つでも条件を満たすマス (i,j) について、c_{(i,j)} は #である。また、スタート地点とゴール地点は必ず空きマスであり、スタート地点からゴール地点へは、空きマスを辿って必ずたどり着ける。

出力

スタート地点からゴール地点に移動する最小手数を 1 行に出力せよ。最後に改行を忘れないこと。

入力例1

7 8
2 2
4 5
########
#......#
#.######
#..#...#
#..##..#
##.....#
########

出力例1

問題文中の例です。

入力例2

5 8
2 2
2 4
########
#.#....#
#.###..#
#......#
########

出力例2

図8のように進めば 10 手でたどり着くことが進むことができます(※Sはスタート、Gはゴールをあらわす)。

図8. 入出力例2において最小手数10を達成する進み方

入力例3

50 50
2 2
49 49
##################################################
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
##################################################

出力例3

もはやただの広い空間であり、迷路と呼んで良いのかは分からないがこの問題でこのような盤面も迷路として扱う。兎にも角にも、スタートからゴールへの最短手数は 94 である。

B64 - Shortest Path with Restoration

Time Limit: 3 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

頂点数 N、辺数 M の重み付き無向グラフが与えられます。頂点 1 から頂点 N までの具体的な最短経路を 1 つ出力してください。計算量は O(M \log N) であることが望ましいです。

制約

2 \leq N \leq 100000
1 \leq M \leq \min(100000,N(N-1)/2)
1 \leq A_i \lt B_i \leq N\ (1\leq i\leq M)
1 \leq C_i \leq 10000\ (1\leq i\leq M)
i \neq j \implies (A_i,B_i) \neq (A_j,B_j)
与えられるグラフにおいて、頂点 1 と頂点 N は連結
入力は全て整数

入力

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

N M
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_M B_M C_M

出力

次の形式で答えを 1 行に出力してください。

v_1 v_2 \cdots v_k

(v_1,v_2,\ldots,v_k) は与えられたグラフにおける頂点 1 から頂点 N への最短経路になっていなければなりません。形式的には、(v_1,v_2,\ldots,v_k) が満たすべき条件は以下のようになります。

v_1=1,v_k=N
与えられたグラフには辺 (v_i,v_{i+1}) が存在する (1\leq i\lt k)
上の 2 条件を満たすどのような (u_1,u_2,\ldots,u_l) に対しても、辺 (v_i,v_{i+1}) の長さの合計は辺 (u_i,u_{i+1}) の長さの合計以下

入力例 1

出力例 1

1 2 5 6

与えられたグラフでの頂点 1 から頂点 N への最短経路は次のようになります。

入力例 2

出力例 2

1 10 15

B65 - Road to Promotion Hard

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

株式会社 KYOPRO-MASTER には N\ (\leq 100000) 人の社員がおり、1 から N までの番号が付けられています。ライバル会社に勤務している太郎君は、以下の N-1 個の情報を入手しました。

i 個目の情報: 社員 A_i と社員 B_i は直属の上司と部下の関係にある。ここで、社員 A_i と B_i のどちらが上司かは分かっていない。

社員 T が社長であり、それ以外の N-1 人全員が誰か 1 人の直属の部下であるとき、各社員の「階級」を求めるプログラムを作成してください。ただし、部下がいない社員の階級は 0 であり、部下がいる社員の階級は、直属の部下における階級の最大値に 1 を足した値であるとします。

制約

2 \leq N \leq 100000
1 \leq T \leq N
1 \leq A_i \lt B_i \leq N\ (1\leq i\leq N-1)
i \neq j \implies (A_i,B_i) \neq (A_j,B_j)
与えられる条件をすべて満たすような直属の上司と部下の関係が存在する。
入力は全て整数

入力

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

N T
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}

出力

社員 1,2,\ldots,N の「階級」の値を、空白区切りで出力してください。

入力例 1

出力例 1

3 1 2 1 0 0 0

入力例 2

出力例 2

4 1 0 0 0 3 0 0 2 1 0 2 1 0 0

与えられるグラフは次のようになります。

B66 - Typhoon

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

ALGO 国には N 個の駅と M 本の鉄道路線があります。駅には 1 から N までの番号が付けられており、i 本目の路線は駅 A_i と駅 B_i を双方向に結んでいます。さて、今日は ALGO 国に台風が上陸するため、いくつかの路線は運休になる場合があります。それについて、以下の 2 種類のクエリを処理してください。

クエリ1：x 本目の路線が運休になる。
クエリ2：現時点で駅 s から駅 t へ移動できるかを答える。

与えられるクエリの数を Q 個とするとき、計算量は O((N+M+Q)\log N) であることが望ましいです。

制約

2 \leq N \leq 100000
1 \leq M \leq 100000
1 \leq Q \leq 100000
1 \leq A_i \lt B_i \leq N\ (1\leq i\leq M)
i \neq j \implies (A_i,B_i) \neq (A_j,B_j)
\operatorname{Query}_i\ (1\leq i\leq Q) はすべて次の形式のどちらか
- 1 x (1\leq x\leq M) ただし、このクエリが与えられる前に x 本目の路線が運休になっていることはない。
- 2 u v (1\leq u\lt v\leq N)
入力は全て整数

入力

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

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M
Q
\operatorname{Query}_1
\operatorname{Query}_2
\vdots
\operatorname{Query}_Q

出力

クエリ 2 の答えを、順番に出力してください。

入力例 1

出力例 1

Yes
No

クエリ 1 の結果、グラフは次のように変化します。

入力例 2

出力例 2

No
Yes
Yes
No
No

入力例 3

出力例 3

Yes
Yes
Yes
Yes
No
No

B67 - Max MST

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

頂点数 N、辺数 M のグラフが与えられます。頂点には 1 から N までの番号が付けられており、辺 i は頂点 A_i と B_i を双方向に結ぶ長さ C_i の辺です。このグラフの最大全域木における辺の長さの総和を求めてください。

制約

2 \leq N \leq 100000
1 \leq M \leq 100000
1 \leq A_i \lt B_i \leq N
i\neq j ならば (A_i,B_i) \neq (A_j,B_j)
1 \leq C_i \leq 10000
与えられるグラフは連結
入力はすべて整数

入力

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

N M
A_1 B_1 C_1
\vdots
A_M B_M C_M

出力

最大全域木における辺の長さの総和を出力してください。

入力例 1

出力例 1

B68 - ALGO Express

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

ALGO 鉄道には N 個の駅があり、1 から N までの番号が付けられています。現在、ALGO 鉄道では特急列車を作るという計画があり、N 個の駅のうち 0 個以上を特急駅に指定しなければなりません。ここで、駅 i を特急駅に指定した場合は P_i 円の利益が見込めます（P_i は負であることもあり得ます）。
一方、特急列車を作るにあたって、利用者から M 個の提案が出されました。j 個目の提案は「駅 A_j を特急駅に指定するならば、駅 B_j も特急駅に指定するべきだ」というものです。すべての提案を守った場合、最大何円の利益を出すことができますか。

制約

2 \leq N \leq 150
1 \leq M \leq 150
|P_i| \leq 150
1 \leq A_j , B_j \leq N
A_j \neq B_j
j\neq k ならば (A_j,B_j) \neq (A_k,B_k)
入力はすべて整数

入力

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

N M
P_1 \ldots P_N
A_1 B_1
\vdots
A_M B_M

出力

最大何円の利益を出すことができるか、整数で出力してください。

入力例 1

5 2
3 4 -1 -5 5
1 3
2 4

出力例 1

駅 1、駅 3、駅 5 を特急駅に指定すると利益が 7 円となり、これが最大です。

B69 - Black Company 2

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

KYOPRO 工場には N 人の社員が在籍しています。しかし、社員が全時間帯に勤務できるとは限りません。社員 i が働ける時間の情報は C_i で表され、j 時台 (0 ≤ j ≤ 23) に働けるとき C_{i,j} = 1、働けないとき C_{i,j} = 0 となります。
また、社員をあまりに働かせると、ブラック企業という評価を受けてしまうため、どの社員も一日 10 時間までしか勤務させてはいけません。このような条件下で、どの時間帯にも M 人以上が勤務しているようにシフトを組むことは可能かどうかを判定してください。

制約

1 \leq N \leq 50
1 \leq M \leq N
N,M は整数である
C_{i,j} は 0 または 1 である

入力

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

N M
C_{1,0} C_{1,1} \ldots C_{1,23}
C_{2,0} C_{2,1} \ldots C_{2,23}
\vdots
C_{N,0} C_{N,1} \ldots C_{N,23}

出力

シフトを組むことが可能な場合は Yes と、そうでない場合は No と出力してください。

入力例 1

2 1
111111111111000000000000
000000000000111111111111

出力例 1

No

社員 1 を 0 時から 11 時に、社員 2 を 12 時から 23 時に勤務させればどの時間帯にも 1 人以上が勤務している状態になりますが、社員をそれぞれ 12 時間勤務させることになるので不適です。

入力例 2

10 2
101001000011000100010111
000010011110110010100111
101110001110000011110111
011011110100011110100011
000011001111111010110001
001010011010101010110100
001010010111101101111010
110011111100010110111011
100010011100011101110001
010110100101101111111011

出力例 2

Yes

C01 - Tax Rate

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

ある商品の税抜価格は N 円です。消費税率が 10 \% であるとき、この商品の税込価格が何円であるかを出力するプログラムを作成してください。ただし、N は 100 の倍数であるとします。

制約

1 \leqq N \leqq 10^6
N は 100 の倍数

入力

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

出力

商品の税込価格を標準出力に 1 行で出力してください。

入力例 1

出力例 1

C02 - Two Balls

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

N 個のボールが机の上に置かれています。i 個目のボールの重さは A_i グラムです。

2 つの異なるボールを選ぶとき、重さの合計として考えられる最大値は何グラムでしょうか。

制約

2 \leq N \leq 100
1 \leq A_i \leq 1000
入力はすべて整数

入力

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

N
A_1 A_2 \cdots A_N

出力

答えを整数で出力してください。

入力例 1

5
120 150 100 200 100

出力例 1

2 番目のボールと 4 番目のボールを選べば、合計 150+200=350 グラムになります。

入力例 2

10
1 2 3 4 5 6 7 8 9 10

出力例 2

9 番目のボールと 10 番目のボールを選べば、合計 9+10=19 グラムになります。

C03 - Stock Queries

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

株式会社 KYOPRO-MARKET は上場から D 日が経過しました。1 日目の株価は X 円であり、i = 2,3, ... ,D について、i 日目の株価は前日よりも A_i 円だけ高かったです（A_i が負の数である場合、安くなったことを意味します）。

「S_j 日目の株価と T_j 日目の株価はどちらの方が高いか？」という形式の質問が Q 個与えられるので、それぞれの質問に答えるプログラムを作成してください。

計算量は O(D + Q) であることが望ましいです。

制約

入力はすべて整数
2 \leqq D \leqq 2 \times 10^5
1 \leqq X \leqq 10^9
-5\,000 \leqq A_i \leqq 5\,000 (2 \leqq i \leqq D)
1 \leqq Q \leqq 2 \times 10^5
1 \leqq S_j < T_j \leqq D (1 \leqq j \leqq Q)
上場以降どの日の株価も 1 以上である

入力

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

D
X
A_2
\vdots
A_D
Q
S_1 T_1
\vdots
S_Q T_Q

出力

標準出力に Q 行出力してください。j 行目には、j 番目の質問に関する答えを次のように表して出力してください。

S_j 日目の株価が T_j 日目の株価よりも高い場合、S_j の値。
T_j 日目の株価が S_j 日目の株価よりも高い場合、T_j の値。
S_j 日目の株価と T_j 日目の株価が等しい場合、Same。

入力例 1

出力例 1

1
5
Same

5 日ぞれぞれの株価は以下の通りになります。

1 日目の株価は X = 30。
2 日目の株価は 30 - 10 = 20。
3 日目の株価は 20 + 20 = 40。
4 日目の株価は 40 - 10 = 30。
5 日目の株価は 30 + 20 = 50。

3 つそれぞれの質問の答えは次のようになります。

1 日目の株価は 2 日目の株価よりも高い。したがって、1 行目には 1 を出力する。
5 日目の株価は 3 日目の株価よりも高い。したがって、2 行目には 5 を出力する。
1 日目の株価と 4 日目の株価は等しい。したがって、3 行目には Same を出力する。

C04 - Divisor Enumeration

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

整数 N が与えられます。 N の約数を列挙してください。

制約

1 \leq N \leq 10^{13}
N は整数

入力

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

出力

Nの約数を小さい順に、改行区切りで出力してください。

入力例 1

出力例 1

12の約数は1、2、3、4、6、12の 6 個あります。

入力例 2

827847039317

出力例 2

1
909859
909863
827847039317

C05 - Lucky Numbers

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

4, 7 のみからなる 10 桁の整数をラッキー数と呼ぶことにします。小さい方から数えて N 番目のラッキー数はいくつですか。

制約

N は 1 以上 1024 以下の整数

入力

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

出力

小さいほうから数えて N 番目のラッキー数を標準出力に 1 行で出力してください。

入力例 1

出力例 1

4444444744

C06 - Regular Graph

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

N 頂点の連結な無向グラフであって、すべての頂点の次数が 2 であるものを一つ出力するプログラムを作成してください。

制約

N は 3 以上 100 以下の整数

入力

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

出力

条件を満たすグラフを，次の形式で標準出力に出力してください。

1 行目に、答えるグラフの辺の本数 m を出力する。
続く m 行のうち j 行目 (1 \leqq j \leqq m)に，j 本目の辺がむすぶ端点の番号を空白区切りで出力する。

入力例 1

出力例 1

この出力は以下のグラフを表しています。

出力例1のグラフ

答えとなるグラフが複数あり得る場合、どれを出力してもかまいません。

C07 - ALGO-MARKET

Time Limit: 3 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

ALGO-MARKET には N 個の品物が売られています。i 個目の品物は C_i 円です。

以下の Q 個の質問が与えられるので、それぞれの質問に答えてください。

j 個目の質問：X_j 円を持っているとき、最大何個の品物を買えるか？

制約

1 \leq N \leq 100000
1 \leq C_i \leq 10000
1 \leq Q \leq 100000
1 \leq X_j \leq 10^9
入力はすべて整数

入力

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

N
C_1 C_2 \cdots C_N
Q
X_1
X_2
 :
X_Q

出力

Q 行にわたって出力してください。
j 行目には、j 個目の質問の答えを出力してください。

入力例 1

5
300 100 400 100 500
3
500
250
40

出力例 1

3
2
0

各質問に対する説明は以下の通りです。

1 つ目の質問：品物 1, 2, 4 を選ぶと、合計価格 500 円で 3 つの品物を買うことができます。
2 つ目の質問：品物 2, 4 を選ぶと、合計価格 200 円で 3 つの品物を買うことができます。
3 つ目の質問：40 円しか持っていない場合、一つも品物を買うことができません。

入力例 2

10
100 100 100 100 100 100 100 100 100 100
11
90
190
290
390
490
590
690
790
890
990
100000000

出力例 2

C08 - ALGO4

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

宝くじ「ALGO4」の抽選券には、0000 から 9999 までの 4 桁の番号が書かれています。

この宝くじには 1 等から 3 等までがあります。1 等は、4 桁の番号のうちどれか 1 つです。2 等は、1 等の当選番号と異なる桁が 1 つだけある番号です。3 等（ハズレ）は、1 等・2 等以外のすべての番号です。たとえば 1 等の当選番号が「1234」である場合、「1534」や「1230」などは 2 等ですが、「4321」や「1253」などは 3 等です。

太郎君は、宝くじの抽選券を N 枚持っており、それぞれについて当たったかどうかを調べました。i 枚目の抽選券の番号は S_i であり、等級は T_i 等でした。

1 等の当選番号はどれであるかを出力してください。ただし、答えが一つに定まらない場合、代わりにCan't Solve と出力してください。

制約

入力はすべて整数
1 \leqq N \leqq 100
S_i は 4 桁の番号 (1 \leqq i \leqq N)
T_i は 1, 2, 3 のいずれか (1 \leqq i \leqq N)
入力と矛盾しない当選番号が少なくとも 1 つ存在する

入力

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

N
S_1 T_1
\vdots
S_N T_N

出力

当選番号としてあり得る番号が一つに定まる場合はその番号を、複数あり得る場合は Can't Solve を、標準出力に 1 行で出力してください。

入力例 1

出力例 1

入力例 2

2
1234 3
8894 2

出力例 2

Can't Solve

入力例 3

2
1234 3
8894 1

出力例 3

C09 - Taro's Vacation

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

太郎君の夏休みは N 日間あり、i 日目に勉強すると A_i だけ実力が上がることが知られています。

しかし、彼は 2 日連続で勉強したくありません。太郎君が夏休みの間に実力をどれだけ上げられるか、その最大値を求めるプログラムを作成してください。

制約

2 \leq N \leq 500000
0 \leq A_i \leq 10^9
入力はすべて整数

入力

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

N
A_1 A_2 \cdots A_N

出力

答えを出力してください。

入力例 1

5
2 5 3 3 1

出力例 1

2 日目、4 日目に勉強すると、実力が 5+3=8 上がります。

C10 - A Long Grid

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

縦 2 行、横 W 列のマス目があります。
どの隣接する 2 マスも同じ色にならないように、マス目を赤・黄・緑・青の 4 色で塗る方法は何通りありますか。

制約

W は 1 以上 10^{18} 以下の整数

入力

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

出力

答えを 1000000007 で割った余りを求めてください。

入力例 1

出力例 1

入力例 2

出力例 2

入力例 3

出力例 3

908287499

C11 - Election

Time Limit: 3 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

今日、KYOPRO 国では総選挙が行われました。N 個の党が立候補し、i 番目の党は A_i 票を獲得しました。比例代表制にしたがって K 議席を配分するとき、各党は何議席を獲得しますか。

ただし比例代表制では、以下の表のように「票数÷議席数」の大きい方から議席を割り当てていきます（ドント方式といいます）。

制約

2 \leq N \leq 100000
1 \leq K \leq 10^9
1 \leq A_i
A_1 + A_2 + \cdots + A_N \leq 10^9
ボーダーとなる「票数÷議席数」の値は 1 を超え 10^9 未満である
ボーダーとなる「票数÷議席数」と、次点の「票数÷議席数」の相対誤差は 10^{-6} を超える
入力はすべて整数

入力

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

N K
A_1 A_2 \cdots A_N

出力

答えを整数で出力してください。

入力例 1

4 10
1000000 700000 300000 180000

出力例 1

5 3 1 1

問題文の図に書かれている通りです。

入力例 2

2 3
6000 3000

出力例 2

2 1

この入力は制約を満たしますが、もし A = [6000, 3000] かつ K=2 である場合はボーダーが同点となるため、制約を満たさないことに注意してください（このような入力は絶対に与えられません）。

入力例 3

15 50
18256245 7845995 6771945 6181431 3618432 3159625 2319156 1768385 1258501 1253872 193724 148020 109045 77861 65107

出力例 3

18 8 7 6 3 3 2 1 1 1 0 0 0 0 0

第 26 回参議院通常選挙のデータです。

入力例 4

2 1
900000000 100000000

出力例 4

1 0

C12 - Taro the Novel Writer

Time Limit: 3 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

作家の太郎君は、N ページの小説を執筆しました。この小説には M 個の繋がりがあり、i 個目の繋がりは A_i ページ目と B_i ページ目です。

いま、彼は小説を K 個の章に分割しようとしています。同じ章に存在する繋がりの個数を「小説の良さ」とするとき、小説の良さの最大値はいくつですか。

制約

入力はすべて整数
2 \leqq N \leqq 288
1 \leqq M \leqq 50
1 \leqq K \leqq 10
K \leqq N
1 \leqq A_i < B_i \leqq N (1 \leqq i \leqq M)

入力

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

N M K
A_1 B_1
\vdots
A_M B_M

出力

小説の良さの最大値を、標準出力に 1 行で出力してください。

入力例 1

出力例 1

入力例 2

出力例 2

入力例 3

出力例 3

C13 - Select 2

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

N 枚のカードがあり、それぞれ整数 A_1, A_2, \cdots, A_N が書かれています。

相異なるカードを 2 枚選ぶ方法のうち、次の条件を満たすものはいくつありますか。

条件：2 枚のカードの積を 1000000007 で割った余りが P になる。

制約

2 \leq N \leq 100000
0 \leq P \leq 1000000006
0 \leq A_i \leq 10^{18}
入力はすべて整数

入力

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

N P
A_1 A_2 \cdots A_N

出力

答えを整数で出力してください。

入力例 1

4 6
1 2 3 6

出力例 1

以下のカードの組を選んだときに、条件を満たします。

1 番目のカードと 4 番目のカードを選ぶ。
2 番目のカードと 3 番目のカードを選ぶ。

入力例 2

4 1
1000000008 1000000008 1000000008 1000000008

出力例 2

書かれている整数が同じであっても、選んだカードの組が異なる場合は区別して数えることに注意してください。

入力例 3

2 609777330
31415926535897932 384626433832795028

出力例 3

入力例 4

10 0
0 0 0 0 0 1 2 3 4 5

出力例 4

C14 - Commute Route

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

諸注意

初版第 1 刷の問題文にミスがありました。本来は「交差点」と書くべきところの一部が「都市」と書かれてしまっているミスです。大変申し訳ございません。詳しくは正誤表をご覧ください。

問題文

KYOPRO 市には N 個の交差点と M 本の道路があります。i 本目の道路は交差点 A_i と交差点 B_i を双方向に結ぶ、長さ C_i の道路です。

太郎君は交差点 1 から交差点 N まで最短経路で移動したいです。彼が通る可能性のある交差点の数は、交差点 1 と交差点 N を含めていくつですか。

制約

2 \leq N \leq 100000
1 \leq M \leq \min(100000, N(N-1)/2)
1 \leq A_i < B_i \leq N
1 \leq C_i \leq 10000
(A_1, B_1), (A_2, B_2), \cdots, (A_M, B_M) はすべて異なる
どの 2 つの交差点間も、いくつかの道路を通って到達可能である
入力はすべて整数

入力

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

N M
A_1 B_1 C_1
A_2 B_2 C_2
 :
A_M B_M C_M

出力

答えを整数で出力してください。

入力例 1

出力例 1

通る可能性のある交差点は 1, 2, 5, 6 です。

入力例 2

出力例 2

通る可能性のある交差点は 1, 2, 3, 4, 5 です。

C15 - Many Meetings

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

株式会社 KYOPRO-MARKET では、今日は N 個の会議が予定されています。i 番目の会議は時刻 L_i [秒] に始まり、時刻 R_i [秒] に終了します。

i=1, 2, 3, \cdots, N について、以下の問いの答えを出力してください。

問い：
i 番目の会議には絶対出席しなければならないとき、最大何個の会議に出席できるか？
ただし、会議は延長される可能性もあるので、2 つの出席する会議の間には K 秒以上空ける必要がある。

制約

1 \leq N \leq 100000
0 \leq K \leq 86400
0 \leq L_i < R_i \leq 86400

入力

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

N
K
L_1 R_1
L_2 R_2
 :
L_N R_N

出力

答えを整数で出力してください。

入力例 1

出力例 1

それぞれの i について、最適な会議の出席方法の一例は以下の通りになります。

i=1 のとき：会議 1, 4 に出席する。
i=2 のとき：会議 2, 3, 5 に出席する。
i=3 のとき：会議 2, 3, 5 に出席する。
i=4 のとき：会議 1, 4 に出席する。
i=5 のとき：会議 2, 3, 5 に出席する。

入力例 2

出力例 2

会議と会議の間には K=1000 秒以上空ける必要があることに注意してください。

C16 - Flights

Time Limit: 5 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

KYOPRO 王国には N 個の空港があり、それぞれ 1 から N までの番号が付けられています。

今日は M 個のフライトが予定されています。i 番目のフライトは空港 A_i を時刻 S_i に出発し、空港 B_i へと時刻 T_i に到着するものです。

太郎君は今日、できるだけ多くの飛行機に乗ろうと思いました。フライトとフライトの間の乗り継ぎ 1 回に K 分かかるとき、最大で何本の飛行機に乗ることができるかを出力してください。

制約

入力はすべて整数
2 \leqq N \leqq 100\,000
1 \leqq M \leqq 100\,000
1 \leqq K \leqq 10^9
1 \leqq A_i, B_i \leqq N (1 \leqq i \leqq N)
0 \leqq S_i < T_i \leqq 10^9 (1 \leqq i \leqq M)

入力

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

N M K
A_1 S_1 B_1 T_1
\vdots
A_M S_M B_M T_M

出力

乗れる飛行機の最大値を、標準出力に 1 行で出力してください。

入力例 1

4 5 30
1 100 2 180
2 200 3 300
1 80 3 360
3 400 3 410
3 450 4 600

出力例 1

C17 - Strange Data Structure?

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

あなたはアトラクションの行列を管理しています。最初、行列には誰も並んでいません。これから Q 個のクエリを処理する必要があります。各クエリは以下の 4 種類のいずれかです。

タイプ A: 文字列 X_i が与えられ、行列の最後尾に名前が X_i である人が入る。
タイプ B: 文字列 X_i が与えられ、行列の中央に名前が X_i である人が入る。
タイプ C: 行列の先頭にいる人が列から抜ける。
タイプ D: 行列の先頭にいる人の名前を答える。

ただし、タイプ B のクエリでは、行列に並んでいる人が n 人であるとき、n が奇数のときは先頭から (n+1)/2 人目の後ろに、n が偶数のときは先頭から n/2 人目の後ろに入るものとします（特に n = 0 の場合は、行列の最後尾に入ることになります）。

すべてのクエリを順番に処理し、与えられるタイプ D のクエリに正しく答えるプログラムを作成してください。

注意

この問題では実行時間制限に間に合えば正解 (AC) とはなりますが、計算量 O(Q) で解いてみましょう。

制約

2 \leq Q \leq 300000
i 個目のクエリがタイプ A, B のとき、X_i は英小文字からなる 10 文字以下の文字列
行列に誰も並んでいない状態でタイプ C, D のクエリが行われることはない
タイプ D のクエリは 1 回以上行われる

入力

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

Q
Query_1
Query_2
 \vdots
Query_Q

ただし、Query_i は i 番目のクエリの情報を指します。各タイプについて以下の形式で与えられます。

タイプ A のとき

A X_i

タイプ B のとき

B X_i

タイプ C のとき

タイプ D のとき

出力

タイプ D のクエリが来るたびに、行列の先頭ににいる人の名前を 1 行ずつ出力してください。

入力例 1

6
A kyopuro
A tessoku
B book
D
C
D

出力例 1

kyopuro
book

各クエリとその結果は以下のようになります。

何番目	クエリ	説明	行列
1	`A kyopuro`	行列の末尾に `kyopuro` さんが入る	`[ "kyopuro" ]`
2	`A tessoku`	行列の末尾に `tessoku` さんが入る	`[ "kyopuro", "tessoku" ]`
3	`B book`	行列の中央に `book` さんが入る	`[ "kyopuro", "book", "tessoku" ]`
4	`D`	行列の先頭の人の名前を答える	（`kyopuro` と出力する）
5	`C`	行列の先頭の人が列から抜ける	`[ "book", "tessoku" ]`
6	`D`	行列の先頭の人の名前を答える	（`book` と出力する）

したがって、1 行目に kyopuro、2 行目に book と出力します。

入力例 2

15
B prefixsum
B binsearch
A dp
B math
C
D
C
D
B heuristics
B ds
B graph
C
D
C
D

出力例 2

binsearch
math
heuristics
graph

C18 - Pick Two（★6）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 6 点

問題文

長さ 2N の正整数列 A=(A_1,A_2,\ldots,A_{2N}) が与えられます。次の操作で列 A から数を取り除くことを考えます。

残っている列を (A^{\prime}_1,A^{\prime}_2,\ldots,A^{\prime}_M) とする。 1\leq i<M を満たす整数 i を一つ選び、A^{\prime}_i と A^{\prime}_{i+1} を列から取り除く。この操作のあと、残る列は (A^{\prime}_1,\ldots,A^{\prime}_{i-1},A^{\prime}_{i+2},\ldots,A^{\prime}_M) である。

この操作には コスト がかかります。 1 回の操作にかかるコストは、取り除く数を A^{\prime}_i,A^{\prime}_{i+1} として |A^{\prime}_i-A^{\prime}_{i+1}| です。

この操作を N 回繰り返して列 A から全ての数を取り除くとき、N 回の操作にかかるコストの総和として考えられる最小の値を求めてください。

制約

1 \leq N \leq 200
1 \leq A_i \leq 10^6\ (1\leq i\leq 2N)
入力は全て整数

入力

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

N
A_1 A_2 \ldots A_{2N}

出力

N 回の操作にかかるコストの総和として考えられる最小の値を出力してください。

入力例 1

3
6 2 3 9 8 6

出力例 1

コストの総和が最小になる操作の例を以下に示します。

i=2 とし、|2 - 3| = 1 のコストをかけて操作を行う。列は (6,9,8,6) となる。
i=2 とし、|9 - 8| = 1 のコストをかけて操作を行う。列は (6,6) となる。
i=1 とし、|6 - 6| = 0 のコストをかけて操作を行う。列は () となる。

3 回の操作にかかるコストの総和は 2 となります。

入力例 2

3
1 3 5 5 3 1

出力例 2

入力例 3

4
1 2 4 8 16 32 64 128

出力例 3

入力例 4

15
73 8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32

出力例 4

Source Name

「競プロ典型90問」19日目

C19 - Gasoline Optimization Problem

Time Limit: 10 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

ALGO 街道は、全長 L キロメートルの直線状の道路です。街道の一方の端をスタート地点とし、もう一方の端をゴール地点とします。

この街道には N 個のガソリンスタンドがあります。i 個目 (1 \leq i \leq N) のガソリンスタンドはスタートから A_i キロメートルの地点にあり、価格は 1 リットル当たり C_i 円です。

燃費が 1 km/L であり、最大 K リットルのガソリンを貯めることができる車を利用したとき、スタートからゴールまで行くことが可能か判定し、もし可能ならば最小何円のガソリン代が必要かを求めるプログラムを求めてください。

ただし、最初の時点でガソリンは満タンであるとします。また、ガソリンの残量がちょうど 0 リットルになったときにガソリンスタンドで給油したり、ゴールに到達したりすることはできるものとします。

制約

0 \leq N \leq 700000
1 \leq K \leq L \leq 700000
1 \leq A_1 \leq A_2 \leq \dots \leq A_N \leq L - 1
1 \leq C_i \leq 10^{12}
入力はすべて整数

入力

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

N L K
A_1 C_1
A_2 C_2
 \vdots
A_N C_N

出力

スタートからゴールまで行くために必要なガソリン代の最小値を 1 行で出力してください。ただし、スタートからゴールまで行くことが不可能な場合は、代わりに -1 と出力してください。

部分点

この問題では、N \leq 100, L \leq 100 を満たすケースすべてに正解すれば、部分点として 500 点を獲得します。

入力例 1

出力例 1

下図のように給油するのが最適です。ガソリンスタンド 1, 2, 3 でそれぞれ 2, 4, 1 リットルを給油するので、ガソリン代は 70 \times 2 + 50 \times 4 + 100 \times 1 = 440 円となります。

入力例 2

1 100 60
39 1

出力例 2

-1

たとえガソリンスタンド 1 で車のガソリンを満タンにしたとしても、スタートから 99 キロメートルの地点でガソリンが尽き、ゴールに到達することはできません。

入力例 3

6 100 30
19 1700000000
44 1400000000
44 1900000000
57 1600000000
78 1300000000
91 1500000000

出力例 3

100800000000

C20 - Mayor's Challenge

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 100000000 点

問題文

KYOPRO 市は N \times N のマス目で表されます。上から i 番目、左から j 番目のマスを (i, j) とします。この市には K 個の地区があり、それぞれに 1 から K までの番号が付けられています。地区 k の人口は A_k 人、役所職員数は B_k 人です。また、マス (i, j) は地区 C_{i, j} に属しています（C_{i, j} = 0 のときは市の領域外です）。ここで、KYOPRO 市の各地区および市全体は連結になっています。ただし連結であるとは、どのマスからどのマスへも、上下左右に隣接するマスへの移動を繰り返して到達できることを指します。

KYOPRO 市の市長である三郎氏は、いくつかの地区を合併することで、市全体を L 個の「特別区」に分けようと考えています（下図は K = 24, L = 4 の例）。ここで、各特別区は連結である方が好ましいです。

三郎氏は特別区どうしの格差を減らしたいので、人口の差と役所職員数の差をできるだけ小さくする（評価基準については得点の項を参照）ような特別区の分け方を求めるプログラムを作成してください。

なお、この問題はヒューリスティック型課題であるため、必ずしも最適な答えを出力する必要はありません。また、採点方法やテストケースの生成方法などの情報は、以降の文章をご覧ください。

制約

N = 50
K = 400
L = 20
50000 \leq A_k \leq 100000
1000 \leq B_k \leq 2000
0 \leq C_{i, j} \leq K
KYOPRO 市全体（C_{i, j} \neq 0 の部分）は連結
地区 1, 2, \dots, K はすべて連結

入力

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

N K L
A_1 B_1
A_2 B_2
 \vdots
A_K B_K
C_{1, 1} C_{1, 2} \cdots C_{1, N}
C_{2, 1} C_{2, 2} \cdots C_{2, N}
 \vdots
C_{N, 1} C_{N, 2} \cdots C_{N, N}

出力

K 行にわたって出力してください。i 行目には、地区 i を何番目の特別区に割り当てるか（1 以上 L 以下の整数）を出力してください。

得点

この問題では、特別区どうしの格差が小さいほど高得点が得られるようになっています。

まず、以下の条件をひとつでも満たした場合は不正解 (WA) となり、0 点となります。

出力形式が指定されたフォーマットに沿っていない
どの地区にも割り当てられていない特別区が存在する

それ以外の場合は正解 (AC) と判定されます。特別区の人口の最大値と最小値をそれぞれ p_{max}, p_{min}、特別区の役所職員数の最大値と最小値をそれぞれ q_{max}, q_{min} とするとき、テストケースの得点は以下の値を四捨五入して整数にした値となります。

すべての特別区が連結な場合：10^6 \times \min\left(\frac{p_{min}}{p_{max}}, \frac{q_{min}}{q_{max}}\right) 点
一部の特別区が連結でない場合：10^3 \times \min\left(\frac{p_{min}}{p_{max}}, \frac{q_{min}}{q_{max}}\right) 点

採点に使われるテストケースは全部で 100 個あり、最終的な得点はそれらの合計となります。

マイルストーン

以下の図は、得点を 10 段階のレベルで表したものです。
より高いレベルに挑戦してみましょう！

入力データ生成方法

すべての採点用入力データは、以下の手順で生成されています。ただし、実数 x に対して、\lfloor x \rfloor を x を超えない最大の整数とします。

ステップ 1. 地区に分割

まず、J = \lfloor 1.2 \times K \rfloor として、N \times N のマス目を以下のようにして J 個の地区に分割します。

最初、各マスが異なる地区に属するとして、合計 N^2 個の地区があるとする。
以下の処理を N^2 - J 回繰り返す。
- 隣り合っている 2 つの地区のペアのなかで、合計マス数が最小になるものを選ぶ。このようなペアが複数ある場合は、その中から無作為に 1 つ選ぶ。
- 選んだ 2 つの地区を合併し、1 つの地区にする。

ステップ 2. KYOPRO 市の地区の割り当て

ステップ 1 で生成した J 個の地区のうち J - K 個を除去した後、残った K 個の地区に番号を割り振ります。具体的な手順は以下のようになります。

以下の処理を J - K 回繰り返す。
- 市の境界に面する地区をランダムに 1 つ選ぶ。
- 選んだ地区を除去しても市が連結になるなら、その地区を除去する。そうでないなら、前述の処理をもう一度行う。
残った K 個の地区に、1 から K までの番号を無作為に割り振る。

ステップ 3. 人口・役所職員数の設定

地区 k の人口 A_k および B_k は、以下のように生成します。

A_k は 50000 以上 100000 以下の整数の中から無作為に選ばれる
B_k は 1000 以上 2000 以下の整数の中から無作為に選ばれる

入力データのサンプル

入力データのサンプルは、ここをクリックするとダウンロードすることができます。ダウンロードで得られる ZIP ファイルの中には 100 個の入力ケースが入っており、手元でのテストなどに利用できます。そのうち in000.txt が入力例に対応しています。なお、これらの入力データのサンプルは、実際の採点に使われる入力データとは異なります。

ビジュアライザ（2022/10/9 追記）

ikd さんのご協力によりビジュアライザが作られました（リンク）。入出力を画像上に表示できるツールとなっています。デバッグ等にご活用ください。

入力例 1

50 400 20
88693 1799
76752 1355
97712 1846
70684 1141
55236 1861
85874 1843
73687 1551
50878 1033
92129 1207
75284 1795
92687 1323
84374 1306
73047 1460
85013 1272
64574 1753
81364 1084
71249 1908
88895 1551
59297 1708
87655 1553
71481 1149
67716 1979
80160 1921
78145 1609
98542 1801
56480 1674
74497 1425
52281 1209
96057 1606
82457 1590
71796 1634
86369 1694
62952 1868
67210 1946
83266 1149
86268 1140
50062 1259
96867 1641
73101 1065
52990 2000
94882 1658
63770 1027
87958 1834
54498 1384
53732 1434
63482 1894
56957 1074
98805 1584
53201 1657
96175 1707
90532 1889
57349 1943
72347 1257
73535 1927
92986 1940
85034 1284
64922 1330
75695 1423
79448 1460
57880 1050
96912 1747
98826 1198
74857 1720
54893 1134
94592 1752
59118 1390
81705 1359
61909 1499
54752 1251
86563 1280
94992 1401
76451 1126
87839 1177
98731 1832
64034 1565
88459 1148
99114 1549
58688 1771
57191 1611
61927 1862
85569 1010
70164 1726
57552 1125
71398 1057
88017 1367
85453 1396
71142 1434
71239 1262
89953 1203
86776 1559
95700 1344
94389 1450
52155 1733
50231 1288
56618 1211
96704 1352
87133 1702
65956 1383
84315 1804
99492 1243
85839 1054
63447 1506
65983 1844
76328 1540
59450 1289
84784 1457
99142 1651
55733 1097
57534 1387
95537 1197
95624 1140
84856 1172
61110 1513
75875 1273
65174 1261
87225 1293
94030 1356
77742 1939
81080 1529
85622 1458
91790 1347
84224 1910
61377 1476
95385 1869
69625 1066
50191 1439
70446 1453
82596 1631
60200 1404
57047 1961
65764 1912
81602 1898
77479 1283
61187 1395
77822 1611
53982 1848
55120 1953
81149 1387
81073 1476
53001 1307
77733 1161
66742 1479
55933 1683
64860 1072
90679 1043
99060 1682
96415 1960
80195 1499
71820 1554
64974 1476
83457 1034
85491 1311
72217 1045
58730 1574
60131 1170
80550 1874
77866 1564
64268 1952
96515 1546
79013 1149
79259 1932
85523 1789
64544 1373
61542 1398
52506 1301
91418 1486
74370 1254
91232 1272
63460 1656
57576 1867
79700 1636
54883 1710
76853 1204
63723 1439
88128 1458
84666 1222
61797 1455
55950 1368
76391 1790
56052 1835
61568 1907
85798 1831
83613 1311
87976 1674
68735 1665
90801 1360
64586 1526
75766 1508
71242 1000
94316 1104
55170 1746
70634 1143
73859 1153
67631 1446
62574 1281
61644 1337
94606 1894
50411 1200
54253 1677
93582 1457
66649 1199
63614 1767
59093 1661
94390 1127
61784 1028
89213 1871
66341 1250
50519 1088
55770 1302
80281 1258
65393 1010
97540 1652
94575 1879
77963 1256
74517 1362
73235 1333
64773 1461
94207 1924
70784 1833
95335 1191
94330 1141
98765 1676
56009 1168
77836 1430
93280 1215
86754 1669
80692 1550
57644 1505
82106 1636
94724 1113
54673 1732
60098 1295
61673 1180
66186 1024
51943 1233
70738 1267
82712 1428
88292 1989
84997 1403
83935 1350
99904 1794
92433 1094
58355 1810
83851 1619
66380 1163
66746 1279
95196 1658
72767 1131
94814 1250
72101 1173
65642 1244
94782 1468
71879 1157
56107 1700
67791 1698
85564 1284
58588 1596
75147 1053
89163 1339
87299 1490
55271 1943
85867 1103
59029 1660
69875 1920
65427 1451
80333 1007
71524 1993
67978 1291
63645 1998
96580 1004
93632 1630
83360 1359
87493 1731
94513 1586
87353 1587
70916 1045
91837 1034
65444 1819
69503 1625
55506 1011
99854 1643
65694 1033
59667 1844
79840 1197
96907 1273
65119 1445
55313 1624
70066 1256
71472 1207
99497 1658
85129 1433
86751 1665
69314 1518
84512 1648
87989 1332
63478 1837
57027 1721
92446 1019
51310 1371
73462 1244
98214 1223
96654 1494
75329 1362
87021 1568
64515 1250
73807 1374
73575 1982
99401 1980
51542 1896
60046 1814
58927 1488
71230 1112
73741 1372
57187 1883
61097 1108
75247 1289
78624 1588
87709 1151
50280 1397
64016 1923
71644 1928
91198 1430
81278 1260
77443 1235
56476 1873
93020 1985
81397 1922
74870 1287
61788 1006
63081 1458
96159 1588
74904 1302
95627 1002
80587 1480
79684 1526
89412 1412
72415 1511
94620 1448
77865 1932
69070 1108
67986 1183
74304 1276
96437 1630
97770 1496
93097 1363
73233 1761
71266 1304
71942 1712
52077 1566
83784 1361
84341 1762
99764 1366
54525 1061
67943 1625
85433 1852
69265 1113
87501 1853
71730 1404
50460 1722
91218 1910
64912 1896
78734 1682
92271 1124
52575 1207
81435 1305
67040 1494
62378 1480
89866 1385
82297 1429
83433 1141
81755 1745
85057 1598
86884 1043
60307 1326
65230 1562
93307 1663
74117 1515
80081 1867
85321 1835
86707 1321
81159 1705
54801 1391
88115 1354
63325 1307
55802 1247
89458 1011
72180 1493
71436 1789
64185 1857
70933 1964
96435 1350
97773 1863
51584 1157
93204 1747
50258 1242
93614 1395
96850 1858
54754 1591
91059 1339
72536 1956
379 379 379 0 226 226 226 382 382 355 355 355 0 0 0 0 0 0 0 63 63 63 63 0 0 0 0 0 0 327 0 0 0 0 194 194 0 0 0 0 72 358 358 358 358 0 0 0 0 0
379 379 379 0 0 226 226 382 382 0 0 355 0 0 0 337 337 0 0 0 0 163 356 356 0 0 0 0 0 327 300 300 0 0 194 194 0 0 0 0 72 72 358 358 0 0 0 0 0 0
379 379 0 0 275 226 226 382 382 0 0 0 0 0 0 337 69 69 69 0 163 163 356 356 0 0 378 378 327 327 300 300 0 0 194 194 174 174 297 297 297 72 358 0 0 0 0 0 0 0
347 347 128 128 275 275 275 382 382 87 354 354 354 0 0 337 69 69 0 0 163 163 151 151 151 151 378 327 327 327 327 338 338 0 0 320 320 174 174 297 297 297 358 0 0 0 0 0 0 0
347 347 128 128 275 244 182 87 87 87 354 354 354 354 0 0 238 238 0 0 0 342 151 151 188 188 378 284 284 95 95 338 338 307 307 320 320 174 210 210 210 210 210 0 0 0 348 348 0 0
128 128 128 244 244 244 182 159 149 149 149 149 205 205 205 90 238 238 0 0 0 342 342 342 188 188 284 284 284 95 95 397 338 307 14 14 67 224 224 224 210 210 210 0 0 0 348 375 375 0
0 0 244 244 244 244 182 159 149 149 149 202 202 202 205 90 90 90 173 0 0 0 342 342 188 188 97 34 34 95 95 397 397 307 14 14 67 224 184 184 184 184 0 0 0 348 348 375 375 227
0 0 0 41 41 41 182 159 88 88 267 202 309 12 119 119 90 90 173 0 0 0 344 188 188 133 97 34 34 95 137 137 397 36 14 14 67 67 67 76 76 76 269 269 227 227 227 227 227 227
0 0 0 41 41 41 159 159 88 88 267 309 309 12 119 119 90 90 173 0 0 0 344 133 133 133 97 272 272 137 137 137 137 36 36 260 260 80 80 76 76 76 269 269 178 178 178 178 156 156
0 0 0 380 380 380 88 88 88 88 267 309 309 12 12 334 334 216 173 0 0 344 344 133 74 74 97 272 272 371 371 137 137 36 36 260 260 80 80 80 269 269 269 269 3 3 3 178 156 156
0 0 0 380 333 333 333 98 98 98 267 374 374 374 109 334 334 216 216 216 0 207 207 74 74 74 97 299 299 371 371 371 308 308 36 260 351 103 103 324 324 324 324 209 3 323 323 225 225 265
0 0 0 0 0 333 136 136 98 98 374 374 374 374 109 109 334 334 58 58 58 58 207 74 40 40 299 299 299 371 371 39 39 308 155 336 351 103 103 324 324 324 47 209 209 323 323 225 265 265
0 0 0 0 0 333 136 206 287 287 127 127 374 369 369 109 334 394 394 58 58 58 207 74 40 40 25 25 299 299 39 39 39 308 155 336 351 351 118 118 47 47 47 240 209 209 142 225 265 0
177 306 306 0 38 333 136 206 287 287 127 127 127 369 369 161 161 394 394 55 92 92 92 150 150 150 25 25 264 264 212 148 148 132 155 336 135 135 118 118 296 296 131 240 142 142 142 225 153 0
177 306 306 306 38 38 38 206 206 104 104 104 383 383 266 266 161 55 55 55 322 322 92 150 150 357 357 357 357 264 212 148 148 132 155 336 135 321 321 321 296 296 131 240 142 142 142 153 153 0
177 177 262 262 302 302 302 206 206 104 230 104 383 383 266 266 161 346 253 322 322 322 73 73 73 220 220 220 220 264 212 148 132 132 155 336 135 321 232 232 232 232 131 240 349 349 295 153 0 0
262 262 262 302 302 82 82 206 206 230 230 104 383 383 266 266 346 346 253 253 322 31 31 180 73 285 220 220 220 264 212 193 193 193 252 252 252 321 304 368 368 368 131 349 349 349 295 23 0 0
42 42 42 11 11 82 82 203 203 230 230 222 222 279 279 266 346 24 24 253 331 31 31 180 285 285 44 44 220 145 145 193 193 193 252 252 252 33 304 304 304 368 171 59 59 295 295 23 23 0
158 158 42 11 305 305 203 203 203 316 316 222 222 222 279 279 18 18 24 253 331 331 180 180 285 285 44 44 317 145 145 187 193 319 319 195 195 33 33 304 171 171 171 171 59 59 59 23 0 0
158 158 292 11 305 305 203 203 289 316 316 222 71 71 71 279 18 18 24 24 24 331 331 331 285 117 117 317 317 145 145 187 187 319 319 319 195 33 33 33 170 170 45 45 59 59 59 23 0 114
0 0 292 305 305 144 144 144 289 289 222 222 71 71 231 231 231 204 126 126 261 261 9 331 117 117 317 317 179 179 179 187 187 21 319 319 195 49 49 33 147 170 45 377 377 377 377 0 0 114
0 0 292 305 305 75 274 144 289 289 17 17 71 71 231 276 276 204 126 126 261 261 9 9 9 6 6 6 179 179 21 21 21 21 360 360 195 195 49 147 147 170 45 26 26 26 110 140 114 114
0 292 292 75 75 75 274 200 122 122 17 17 350 234 276 276 276 204 204 37 218 301 9 9 290 290 290 6 112 112 21 21 21 278 360 107 195 195 49 147 28 28 45 26 110 110 110 140 123 123
0 0 0 115 115 115 274 200 122 122 17 17 350 234 234 214 214 204 37 37 218 301 86 86 290 242 242 6 112 112 268 278 278 278 360 107 107 107 107 28 28 28 28 28 110 0 140 140 123 123
0 0 0 115 274 274 274 200 286 286 256 256 350 234 214 214 204 204 37 218 218 301 301 86 86 86 242 242 242 246 268 268 278 278 387 387 387 387 107 52 52 52 152 168 168 0 0 0 0 123
291 291 291 239 239 120 120 200 286 286 256 256 350 234 366 366 318 318 78 218 218 389 389 270 270 398 398 242 242 246 329 268 278 278 35 387 399 399 373 373 52 52 152 168 168 0 0 0 0 123
291 291 239 239 258 258 120 120 120 22 22 93 93 366 366 366 318 318 78 78 389 389 389 270 270 270 398 398 384 246 329 329 329 329 35 399 399 373 373 373 52 152 152 113 0 0 0 0 0 0
0 0 0 258 258 16 29 29 29 22 22 93 93 93 93 50 50 50 78 48 48 48 389 172 172 43 43 43 384 246 329 329 35 35 35 35 56 56 364 364 364 152 113 113 0 0 0 0 0 0
0 0 0 258 16 16 29 65 65 65 22 22 93 217 217 50 50 100 78 78 78 48 339 172 172 43 43 384 384 246 246 248 248 248 365 365 56 83 233 233 364 364 113 395 395 186 186 186 0 0
0 0 0 16 16 199 199 199 65 65 361 22 22 217 217 157 157 100 100 359 339 339 339 339 339 43 213 213 213 259 259 259 259 248 365 365 56 83 233 233 364 364 113 395 395 236 236 186 0 0
0 0 0 0 0 0 199 199 361 361 361 343 217 217 217 157 157 100 100 359 359 353 353 353 353 43 213 213 213 213 213 345 345 345 365 365 56 83 233 60 60 255 255 395 395 236 236 0 0 0
0 0 0 392 392 0 10 199 199 241 46 343 217 393 393 393 393 393 100 100 359 141 141 353 353 257 257 66 27 27 27 325 345 345 15 365 81 83 60 60 255 255 255 0 0 0 0 0 0 0
0 0 0 392 392 392 10 10 241 241 46 343 343 343 280 280 57 57 57 183 183 183 141 141 257 257 102 66 27 325 325 325 15 15 15 15 81 81 60 60 255 255 255 341 0 0 0 0 0 0
0 0 0 0 392 10 10 10 241 46 46 166 166 343 280 280 162 57 183 183 183 381 257 257 257 257 102 66 372 325 340 5 5 169 169 81 81 81 249 249 249 165 165 341 0 0 0 0 0 0
0 0 0 0 0 0 0 0 241 64 64 166 166 400 400 400 162 57 330 330 381 381 381 381 125 125 102 66 372 340 340 367 5 5 169 169 169 81 249 229 165 165 165 341 341 215 201 0 0 0
0 0 0 0 0 0 0 0 64 64 13 13 13 400 400 400 162 162 330 330 381 381 381 125 125 102 102 372 372 340 367 367 367 96 96 169 169 196 196 229 229 165 84 84 84 215 201 201 201 0
0 328 328 68 68 0 0 0 160 13 13 89 89 400 400 2 2 2 386 330 111 111 111 176 176 102 102 243 243 243 243 208 367 96 245 196 196 196 229 229 229 165 84 84 215 215 263 263 0 0
0 328 328 68 68 68 0 0 160 160 13 89 89 198 2 2 2 386 386 330 4 4 111 176 176 298 298 101 101 101 243 208 208 96 245 30 30 62 62 62 190 190 190 108 108 143 263 263 0 0
0 0 0 99 99 370 121 160 160 160 13 235 235 198 198 198 386 386 386 386 4 4 111 124 124 298 298 314 314 101 303 208 208 245 245 30 30 62 62 385 385 385 190 108 108 143 143 0 0 0
0 0 99 99 99 370 121 121 121 294 294 294 235 235 235 271 271 271 271 106 106 106 111 124 124 154 154 314 314 303 303 61 208 146 146 30 62 62 62 385 385 385 192 192 192 143 143 0 0 0
0 0 0 0 370 370 121 282 293 294 294 390 390 181 181 181 181 271 271 271 271 106 53 53 124 154 154 352 352 303 303 61 61 61 146 146 146 146 385 385 288 288 192 192 192 192 192 134 0 0
0 0 211 211 211 121 121 282 293 293 390 390 390 197 221 221 0 0 19 19 53 53 53 53 54 54 154 352 352 352 352 312 1 1 388 146 139 164 164 288 288 273 273 85 85 85 85 134 134 134
0 0 211 211 211 211 282 282 293 293 390 197 197 197 221 221 221 0 0 19 19 70 70 70 54 396 105 105 105 7 352 312 1 1 388 139 139 139 164 288 362 273 273 85 85 0 0 0 134 134
0 0 0 0 0 51 247 247 293 293 310 310 94 94 94 94 221 221 0 391 391 391 391 70 54 396 105 7 7 7 312 312 228 228 388 388 388 139 164 362 362 251 251 191 191 0 0 0 0 0
0 32 0 0 0 51 129 247 247 247 247 310 310 189 189 189 20 20 0 391 138 391 391 281 396 396 105 250 250 250 363 363 228 283 283 223 223 139 219 362 362 251 251 191 191 0 0 0 0 0
0 32 0 237 237 51 129 247 0 0 332 332 91 91 91 189 20 20 0 0 138 391 281 281 396 396 105 0 0 250 363 363 228 283 283 223 223 167 219 219 219 335 335 335 335 130 130 79 0 0
0 32 32 237 237 51 129 129 0 8 8 332 332 91 91 0 0 0 0 138 138 281 281 281 376 376 105 0 250 250 363 313 313 283 77 77 77 167 219 219 219 219 335 335 0 130 130 79 0 0
0 0 32 237 237 237 129 315 0 0 8 8 8 0 0 0 0 277 277 311 311 311 311 326 326 376 0 0 254 250 250 313 313 313 0 0 77 167 167 0 0 0 0 0 0 130 130 79 0 0
0 0 0 0 0 0 0 315 0 0 0 0 0 0 0 0 0 277 277 0 0 311 311 326 326 376 0 0 254 116 116 0 313 313 0 0 0 175 175 0 0 0 0 0 185 185 130 79 0 0
0 0 0 0 0 0 315 315 0 0 0 0 0 0 0 0 0 0 0 0 0 0 326 326 326 0 0 254 254 116 116 0 0 0 0 0 0 175 175 175 0 0 0 0 185 185 130 0 0 0

出力例 1

この出力例では p_{min} = 883111, p_{max} = 2041166, q_{min} = 18267, q_{max} = 39399 となっているため、このテストケースに対して 432650 点が得られます。