C - Pizza

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

ここに円形のピザが 1 枚あります。
高橋くんは長さ N の数列 A を使ってこのピザを以下の手順で切り分けます。

  • 最初に、円の中心から 12 時の方向に切れ込みをひとつ入れます。
  • 次に、以下の操作を N 回繰り返します。 i 回目の操作では以下を行います。
    • まず、ピザを時計回りに A_i 度回転させる。
    • 次に、円の中心から 12 時の方向に切れ込みをひとつ入れる。

例えば、A=(90,180,45,195) として手順を行うと、下図のようになります。

このとき、最も大きなピザの中心角が何度であるか求めてください。

制約

  • 入力は全て整数
  • 1 \le N \le 359
  • 1 \le A_i \le 359
  • 同じ場所に複数回切れ込みが入ることはない。

入力

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

N
A_1 A_2 \dots A_N

出力

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


入力例 1

4
90 180 45 195

出力例 1

120

この入力は問題文中の例と一致します。
最も大きなピザの中心角は 120 度です。


入力例 2

1
1

出力例 2

359

入力例 3

10
215 137 320 339 341 41 44 18 241 149

出力例 3

170

Score : 200 points

Problem Statement

We have a circular pizza.
Takahashi will cut this pizza using a sequence A of length N, according to the following procedure.

  • First, make a cut from the center in the 12 o'clock direction.
  • Next, do N operations. The i-th operation is as follows.
    • Rotate the pizza A_i degrees clockwise.
    • Then, make a cut from the center in the 12 o'clock direction.

For example, if A=(90,180,45,195), the procedure cuts the pizza as follows.

Find the center angle of the largest pizza after the procedure.

Constraints

  • All values in input are integers.
  • 1 \le N \le 359
  • 1 \le A_i \le 359
  • There will be no multiple cuts at the same position.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

Output

Print the answer as an integer.


Sample Input 1

4
90 180 45 195

Sample Output 1

120

This input coincides with the example in the Problem Statement.
The center angle of the largest pizza is 120 degrees.


Sample Input 2

1
1

Sample Output 2

359

Sample Input 3

10
215 137 320 339 341 41 44 18 241 149

Sample Output 3

170
D - Locked Rooms

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

N + 1 個の部屋が一列に並んでおり、順に 0, 1, \ldots, N の番号が付けられています。

部屋の間には N 個のドアがあり、1, 2, \ldots, N の番号が付けられています。ドア i は部屋 i - 1 と部屋 i の間にあります。

各ドアについて鍵の状態を表す値 L_i が与えられ、L_i = 0 のときドア i の鍵は開いており、L_i = 1 のときドア i の鍵は閉まっています。

2 人の人がおり、1 人は部屋 0 に、もう 1 人は部屋 N にいます。それぞれの人は、ドア i の鍵が開いているときに限り、部屋 i - 1 と部屋 i の間を移動することができます。

このとき、2 人のいずれも到達できない部屋の個数を求めてください。

制約

  • 2 \leq N \leq 100
  • L_i \in \lbrace 0, 1 \rbrace
  • 入力される値はすべて整数

入力

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

N
L_1 L_2 \ldots L_N

出力

答えを出力せよ。


入力例 1

5
0 1 0 0 1

出力例 1

3

2 人のいずれも到達できない部屋は部屋 2, 3, 4 の 3 つです。


入力例 2

3
1 0 1

出力例 2

2

入力例 3

8
0 0 1 1 0 1 0 0

出力例 3

3

Score : 200 points

Problem Statement

There are N + 1 rooms arranged in a line, numbered 0, 1, \ldots, N in order.

Between the rooms, there are N doors numbered 1, 2, \ldots, N. Door i is between rooms i - 1 and i.

For each door, a value L_i representing the lock state is given. When L_i = 0, door i is unlocked, and when L_i = 1, door i is locked.

There are two people, one in room 0 and the other in room N. Each person can move between rooms i - 1 and i only when door i is unlocked.

Find the number of rooms that neither of the two people can reach.

Constraints

  • 2 \leq N \leq 100
  • L_i \in \lbrace 0, 1 \rbrace
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
L_1 L_2 \ldots L_N

Output

Output the answer.


Sample Input 1

5
0 1 0 0 1

Sample Output 1

3

The rooms that neither of the two people can reach are rooms 2, 3, 4, which is 3 rooms.


Sample Input 2

3
1 0 1

Sample Output 2

2

Sample Input 3

8
0 0 1 1 0 1 0 0

Sample Output 3

3
E - Error Correction

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君は英小文字からなる文字列 T を青木君に向けて送りました。その結果、青木君は英小文字からなる文字列 T' を受信しました。

T' は T から一部が変更されてしまっている可能性があり、具体的には、下記の 4 つのうちのちょうど 1 つが成り立つことがわかっています。

  • T' は、T と等しい。
  • T' は、T のいずれか 1 つの位置(先頭と末尾も含む)に英小文字を 1 つ挿入して得られる文字列である。
  • T' は、T からある 1 文字を削除して得られる文字列である。
  • T' は、T のある 1 文字を別の英小文字に変更して得られる文字列である。

青木君が受信した文字列 T' と、英小文字からなる N 個の文字列 S_1, S_2, \ldots, S_N が入力として与えられるので、 S_1, S_2, \ldots, S_N のうち、高橋君が送った文字列 T と等しい可能性があるものをすべて求めてください。

制約

  • N は整数
  • 1 \leq N \leq 5 \times 10^5
  • S_i と T' は英小文字からなる長さ 1 以上 5 \times 10^5 以下の文字列
  • S_1, S_2, \ldots, S_N の長さの総和は 5 \times 10^5 以下

入力

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

N T'
S_1
S_2
\vdots
S_N

出力

S_1, S_2, \ldots, S_N のうち T と等しい可能性があるものすべての添字を昇順に並べた列を (i_1, i_2, \ldots, i_K) とする。 この列の長さ K および列自体を、下記の形式にしたがって出力せよ。

K
i_1 i_2 \ldots i_K

入力例 1

5 ababc
ababc
babc
abacbc
abdbc
abbac

出力例 1

4
1 2 3 4

S_1, S_2, \ldots, S_5 のうち、T と等しい可能性があるものは S_1, S_2, S_3, S_4 の 4 つであることが下記の通りわかります。

  • S_1 は T と等しい可能性があります。なぜなら、T' = ababc は S_1 = ababc と等しいからです。
  • S_2 は T と等しい可能性があります。なぜなら、T' = ababc は S_2 = babc の先頭に文字 a を挿入して得られる文字列だからです。
  • S_3 は T と等しい可能性があります。なぜなら、T' = ababc は S_3 = abacbc から 4 文字目の c を削除して得られる文字列だからです。
  • S_4 は T と等しい可能性があります。なぜなら、T' = ababc は S_4 = abdbc の 3 文字目の d を b に変更して得られる文字列だからです。
  • S_5 は T と等しい可能性はありません。なぜなら、S_5 = abbac を T としたとき、T' = ababc は問題文中の 4 つの条件をいずれも満たさないからです。

入力例 2

1 aoki
takahashi

出力例 2

0


入力例 3

9 atcoder
atoder
atcode
athqcoder
atcoder
tacoder
jttcoder
atoder
atceoder
atcoer

出力例 3

6
1 2 4 7 8 9

Score : 300 points

Problem Statement

Takahashi sent a string T consisting of lowercase English letters to Aoki. As a result, Aoki received a string T' consisting of lowercase English letters.

T' may have been altered from T. Specifically, exactly one of the following four conditions is known to hold.

  • T' is equal to T.
  • T' is a string obtained by inserting one lowercase English letter at one position (possibly the beginning and end) in T.
  • T' is a string obtained by deleting one character from T.
  • T' is a string obtained by changing one character in T to another lowercase English letter.

You are given the string T' received by Aoki and N strings S_1, S_2, \ldots, S_N consisting of lowercase English letters. Find all the strings among S_1, S_2, \ldots, S_N that could equal the string T sent by Takahashi.

Constraints

  • N is an integer.
  • 1 \leq N \leq 5 \times 10^5
  • S_i and T' are strings of length between 1 and 5 \times 10^5, inclusive, consisting of lowercase English letters.
  • The total length of S_1, S_2, \ldots, S_N is at most 5 \times 10^5.

Input

The input is given from Standard Input in the following format:

N T'
S_1
S_2
\vdots
S_N

Output

Let (i_1, i_2, \ldots, i_K) be the sequence of indices of all the strings among S_1, S_2, \ldots, S_N that could be equal to T, in ascending order. Print the length K of this sequence, and the sequence itself, in the following format:

K
i_1 i_2 \ldots i_K

Sample Input 1

5 ababc
ababc
babc
abacbc
abdbc
abbac

Sample Output 1

4
1 2 3 4

Among S_1, S_2, \ldots, S_5, the strings that could be equal to T are S_1, S_2, S_3, S_4, as explained below.

  • S_1 could be equal to T, because T' = ababc is equal to S_1 = ababc.
  • S_2 could be equal to T, because T' = ababc is obtained by inserting the letter a at the beginning of S_2 = babc.
  • S_3 could be equal to T, because T' = ababc is obtained by deleting the fourth character c from S_3 = abacbc.
  • S_4 could be equal to T, because T' = ababc is obtained by changing the third character d in S_4 = abdbc to b.
  • S_5 could not be equal to T, because if we take S_5 = abbac as T, then T' = ababc does not satisfy any of the four conditions in the problem statement.

Sample Input 2

1 aoki
takahashi

Sample Output 2

0


Sample Input 3

9 atcoder
atoder
atcode
athqcoder
atcoder
tacoder
jttcoder
atoder
atceoder
atcoer

Sample Output 3

6
1 2 4 7 8 9
F - Triple Attack

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

あなたはゲームをプレイしています。

N 人の敵が一列に並んでおり、前から i 番目の敵の体力は H_i です。

あなたは 0 で初期化された変数 T を使い、全ての敵の体力が 0 以下になるまで次の行動を繰り返します。

  • T を 1 増やす。その後、体力が 1 以上である最も前の敵を攻撃する。このとき、T が 3 の倍数ならばその敵の体力は 3 減り、そうでないなら 1 減る。

全ての敵の体力が 0 以下になったときの T の値を求めてください。

制約

  • 1 \leq N \leq 2\times 10^5
  • 1 \leq H_i \leq 10^9
  • 入力は全て整数

入力

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

N
H_1 H_2 \ldots H_N

出力

答えを出力せよ。


入力例 1

3
6 2 2

出力例 1

8

行動は次のように行われます。

  • T=1 になる。1 番目の敵を攻撃し、その敵の体力は 6-1=5 となる。
  • T=2 になる。1 番目の敵を攻撃し、その敵の体力は 5-1=4 となる。
  • T=3 になる。1 番目の敵を攻撃し、その敵の体力は 4-3=1 となる。
  • T=4 になる。1 番目の敵を攻撃し、その敵の体力は 1-1=0 となる。
  • T=5 になる。2 番目の敵を攻撃し、その敵の体力は 2-1=1 となる。
  • T=6 になる。2 番目の敵を攻撃し、その敵の体力は 1-3=-2 となる。
  • T=7 になる。3 番目の敵を攻撃し、その敵の体力は 2-1=1 となる。
  • T=8 になる。3 番目の敵を攻撃し、その敵の体力は 1-1=0 となる。

入力例 2

9
1 12 123 1234 12345 123456 1234567 12345678 123456789

出力例 2

82304529

入力例 3

5
1000000000 1000000000 1000000000 1000000000 1000000000

出力例 3

3000000000

オーバーフローに注意してください。

Score : 300 points

Problem Statement

You are playing a game.

There are N enemies lined up in a row, and the i-th enemy from the front has a health of H_i.

You will repeat the following action until the healths of all enemies become 0 or less, using a variable T initialized to 0.

  • Increase T by 1. Then, attack the frontmost enemy with health 1 or more. If T is a multiple of 3, the enemy's health decreases by 3; otherwise, it decreases by 1.

Find the value of T when the healths of all enemies become 0 or less.

Constraints

  • 1 \leq N \leq 2\times 10^5
  • 1 \leq H_i \leq 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
H_1 H_2 \ldots H_N

Output

Print the answer.


Sample Input 1

3
6 2 2

Sample Output 1

8

The actions are performed as follows:

  • T becomes 1. Attack the 1st enemy, and its health becomes 6-1=5.
  • T becomes 2. Attack the 1st enemy, and its health becomes 5-1=4.
  • T becomes 3. Attack the 1st enemy, and its health becomes 4-3=1.
  • T becomes 4. Attack the 1st enemy, and its health becomes 1-1=0.
  • T becomes 5. Attack the 2nd enemy, and its health becomes 2-1=1.
  • T becomes 6. Attack the 2nd enemy, and its health becomes 1-3=-2.
  • T becomes 7. Attack the 3rd enemy, and its health becomes 2-1=1.
  • T becomes 8. Attack the 3rd enemy, and its health becomes 1-1=0.

Sample Input 2

9
1 12 123 1234 12345 123456 1234567 12345678 123456789

Sample Output 2

82304529

Sample Input 3

5
1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

3000000000

Beware of integer overflow.

G - Jumping Takahashi 2

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君が住んでいる二次元平面上の街には N 個のジャンプ台があります。i 番目のジャンプ台は点 (x_i, y_i) にあり、ジャンプ台のパワーは P_i です。また高橋君のジャンプ力は S で表され、はじめ S=0 です。高橋君が訓練を 1 回行う度に S は 1 増えます。

高橋君は以下の条件を満たす場合に限り、i 番目のジャンプ台から j 番目のジャンプ台にジャンプすることができます。

  • P_iS\geq |x_i - x_j| +|y_i - y_j|

高橋君の目的は、適切に始点とするジャンプ台を決めることで、そのジャンプ台からどのジャンプ台にも何回かのジャンプで移動できるようにすることです。

目的を達成するためには高橋君は最低で何回訓練を行う必要があるでしょうか?

制約

  • 2 \leq N \leq 200
  • -10^9 \leq x_i,y_i \leq 10^9
  • 1 \leq P_i \leq 10^9
  • (x_i, y_i) \neq (x_j,y_j)\ (i\neq j)
  • 入力は全て整数

入力

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

N
x_1 y_1 P_1
\vdots
x_N y_N P_N

出力

答えを出力せよ。


入力例 1

4
-10 0 1
0 0 5
10 0 1
11 0 1

出力例 1

2

高橋君が 2 回訓練したとすると、 S=2 です。 このとき、2 番目のジャンプ台から全てのジャンプ台に移動することができます。

例えば、4 番目のジャンプ台へは以下の方法で移動ができます。

  • 2 番目のジャンプ台から 3 番目のジャンプ台へジャンプする。( P_2 S = 10, |x_2-x_3| + |y_2-y_3| = 10 であり、 P_2 S \geq |x_2-x_3| + |y_2-y_3| を満たす。)

  • 3 番目のジャンプ台から 4 番目のジャンプ台へジャンプする。( P_3 S = 2, |x_3-x_4| + |y_3-y_4| = 1 であり、 P_3 S \geq |x_3-x_4| + |y_3-y_4| を満たす。)


入力例 2

7
20 31 1
13 4 3
-10 -15 2
34 26 5
-2 39 4
0 -50 1
5 -20 2

出力例 2

18

Score : 400 points

Problem Statement

There are N trampolines on a two-dimensional planar town where Takahashi lives. The i-th trampoline is located at the point (x_i, y_i) and has a power of P_i. Takahashi's jumping ability is denoted by S. Initially, S=0. Every time Takahashi trains, S increases by 1.

Takahashi can jump from the i-th to the j-th trampoline if and only if:

  • P_iS\geq |x_i - x_j| +|y_i - y_j|.

Takahashi's objective is to become able to choose a starting trampoline such that he can reach any trampoline from the chosen one with some jumps.

At least how many times does he need to train to achieve his objective?

Constraints

  • 2 \leq N \leq 200
  • -10^9 \leq x_i,y_i \leq 10^9
  • 1 \leq P_i \leq 10^9
  • (x_i, y_i) \neq (x_j,y_j)\ (i\neq j)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1 P_1
\vdots
x_N y_N P_N

Output

Print the answer.


Sample Input 1

4
-10 0 1
0 0 5
10 0 1
11 0 1

Sample Output 1

2

If he trains twice, S=2, in which case he can reach any trampoline from the 2-nd one.

For example, he can reach the 4-th trampoline as follows.

  • Jump from the 2-nd to the 3-rd trampoline. (Since P_2 S = 10 and |x_2-x_3| + |y_2-y_3| = 10, it holds that P_2 S \geq |x_2-x_3| + |y_2-y_3|.)

  • Jump from the 3-rd to the 4-th trampoline. (Since P_3 S = 2 and |x_3-x_4| + |y_3-y_4| = 1, it holds that P_3 S \geq |x_3-x_4| + |y_3-y_4|.)


Sample Input 2

7
20 31 1
13 4 3
-10 -15 2
34 26 5
-2 39 4
0 -50 1
5 -20 2

Sample Output 2

18