AtCoder Daily Training MEDIUM 2024/03/21 18:30start

C - At Most 3 (Judge ver.)

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

配点 : 200 点

問題文

おもり 1, おもり 2, \dots, おもり N の N 個のおもりがあります。おもり i の重さは A_i です。
以下の条件を満たす正整数 n を 良い整数 と呼びます。

\bf{3} 個以下 の異なるおもりを自由に選んで、選んだおもりの重さの和を n にすることができる。

W 以下の正整数のうち、良い整数は何個ありますか？

制約

1 \leq N \leq 300
1 \leq W \leq 10^6
1 \leq A_i \leq 10^6
入力される値はすべて整数

入力

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

N W
A_1 A_2 \dots A_N

出力

答えを出力せよ。

入力例 1

2 10
1 3

出力例 1

おもり 1 のみを選ぶと重さの和は 1 になります。よって 1 は良い整数です。
おもり 2 のみを選ぶと重さの和は 3 になります。よって 3 は良い整数です。
おもり 1 とおもり 2 を選ぶと重さの和は 4 になります。よって 4 は良い整数です。
これら以外に良い整数は存在しません。また、1,3,4 のいずれも W 以下の整数です。よって答えは 3 個になります。

入力例 2

2 1
2 3

出力例 2

W 以下の良い整数は存在しません。

入力例 3

4 12
3 3 3 3

出力例 3

良い整数は 3,6,9 の 3 個です。
たとえばおもり 1, おもり 2, おもり 3 を選ぶと重さの和は 9 になるので、9 は良い整数です。
12 は良い整数 ではない ことに注意してください。

入力例 4

7 251
202 20 5 1 4 2 100

出力例 4

Score : 200 points

Problem Statement

There are N weights called Weight 1, Weight 2, \dots, Weight N. Weight i has a mass of A_i.
Let us say a positive integer n is a good integer if the following condition is satisfied:

We can choose at most 3 different weights so that they have a total mass of n.

How many positive integers less than or equal to W are good integers?

Constraints

1 \leq N \leq 300
1 \leq W \leq 10^6
1 \leq A_i \leq 10^6
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N W
A_1 A_2 \dots A_N

Output

Print the answer.

Sample Input 1

2 10
1 3

Sample Output 1

If we choose only Weight 1, it has a total mass of 1, so 1 is a good integer.
If we choose only Weight 2, it has a total mass of 3, so 3 is a good integer.
If we choose Weights 1 and 2, they have a total mass of 4, so 4 is a good integer.
No other integer is a good integer. Also, all of 1, 3, and 4 are integers less than or equal to W. Therefore, the answer is 3.

Sample Input 2

2 1
2 3

Sample Output 2

There are no good integers less than or equal to W.

Sample Input 3

4 12
3 3 3 3

Sample Output 3

There are 3 good integers: 3, 6, and 9.
For example, if we choose Weights 1, 2, and 3, they have a total mass of 9, so 9 is a good integer.
Note that 12 is not a good integer.

Sample Input 4

7 251
202 20 5 1 4 2 100

Sample Output 4

D - Base 2

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

配点 : 200 点

問題文

0 と 1 からなる長さ 64 の数列 A=(A_0,A_1,\dots,A_{63}) が与えられます。

A_0 2^0 + A_1 2^1 + \dots + A_{63} 2^{63} を求めてください。

制約

A_i は 0 または 1

入力

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

A_0 A_1 \dots A_{63}

出力

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

入力例 1

1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

出力例 1

A_0 2^0 + A_1 2^1 + \dots + A_{63} 2^{63} = 2^0 + 2^2 + 2^3 = 13 です。

入力例 2

1 0 1 0 1 0 0 0 0 1 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0

出力例 2

766067858140017173

Score : 200 points

Problem Statement

You are given a sequence A=(A_0,A_1,\dots,A_{63}) of length 64 consisting of 0 and 1.

Find A_0 2^0 + A_1 2^1 + \dots + A_{63} 2^{63}.

Constraints

A_i is 0 or 1.

Input

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

A_0 A_1 \dots A_{63}

Output

Print the answer as an integer.

Sample Input 1

1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Sample Output 1

A_0 2^0 + A_1 2^1 + \dots + A_{63} 2^{63} = 2^0 + 2^2 + 2^3 = 13.

Sample Input 2

1 0 1 0 1 0 0 0 0 1 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0

Sample Output 2

766067858140017173

E - ABC conjecture

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

配点 : 300 点

問題文

正の整数 N が与えられます。

A\leq B\leq C かつ ABC\leq N であるような正の整数の組 (A,B,C) の個数を求めてください。

なお、制約の条件下で答えは 2^{63} 未満であることが保証されます。

制約

1 \leq N \leq 10^{11}
N は整数である

入力

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

出力

答えを出力せよ。

入力例 1

出力例 1

条件を満たす組は (1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,2,2) の 5 つです。

入力例 2

出力例 2

入力例 3

100000000000

出力例 3

5745290566750

Score : 300 points

Problem Statement

You are given a positive integer N.

Find the number of triples of positive integers (A, B, C) such that A\leq B\leq C and ABC\leq N.

The Constraints guarantee that the answer is less than 2^{63}.

Constraints

1 \leq N \leq 10^{11}
N is an integer.

Input

Input is given from Standard Input in the following format:

Output

Print the answer.

Sample Input 1

Sample Output 1

There are five such triples: (1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,2,2).

Sample Input 2

Sample Output 2

Sample Input 3

100000000000

Sample Output 3

5745290566750

F - String Delimiter

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

配点 : 300 点

問題文

英小文字、,、" からなる長さ N の文字列 S が与えられます。S に含まれる " の個数は偶数であることが保証されています。

S に含まれる " の個数を 2K 個とすると、各 i=1,2,\ldots,K について 2i-1 番目の " から 2i 番目の " までの文字のことを 括られた文字 と呼びます。

あなたの仕事は、 S に含まれる , のうち、括られた文字 でないもの を . で置き換えて得られる文字列を答えることです。

制約

N は 1 以上 2\times 10^5 以下の整数
S は英小文字、,、" からなる長さ N の文字列
S に含まれる " の個数は偶数

入力

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

N
S

出力

答えを出力せよ。

入力例 1

8
"a,b"c,d

出力例 1

"a,b"c.d

S のうち "a,b" が括られた文字であり、c,d は括られた文字ではありません。

S に含まれる , のうち、括られた文字でないのは S の左から 7 番目の文字なので、7 番目の文字を . で置き換えたものが答えとなります。

入力例 2

5
,,,,,

出力例 2

.....

入力例 3

20
a,"t,"c,"o,"d,"e,"r,

出力例 3

a."t,"c."o,"d."e,"r.

Score : 300 points

Problem Statement

You are given a string S of length N consisting of lowercase English letters, ,, and ". It is guaranteed that S contains an even number of ".

Let 2K be the number of " in S. For each i=1,2,\ldots,K, the characters from the (2i-1)-th " through the (2i)-th " are said to be enclosed.

Your task is to replace each , in S that is not an enclosed character with . and print the resulting string.

Constraints

N is an integer between 1 and 2\times 10^5, inclusive.
S is a string of length N consisting of lowercase English letters, ,, and ".
S contains an even number of ".

Input

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

N
S

Output

Print the answer.

Sample Input 1

8
"a,b"c,d

Sample Output 1

"a,b"c.d

In S, "a,b" are enclosed characters, and c,d are not.

The , in S that is not an enclosed character is the seventh character from the left in S, so replace that character with . to get the answer.

Sample Input 2

5
,,,,,

Sample Output 2

.....

Sample Input 3

20
a,"t,"c,"o,"d,"e,"r,

Sample Output 3

a."t,"c."o,"d."e,"r.

G - Snuke Panic (1D)

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

配点 : 400 点

問題文

高橋君はすぬけ君たちを捕まえようとしています。

数直線上の座標 0,1,2,3,4 の 5 箇所に穴があり、すぬけ君たちの巣につながっています。

これから N 匹のすぬけ君が穴から出てきます。i 番目のすぬけ君は時刻 T_i に座標 X_i の穴から出てきて、大きさは A_i であることがわかっています。

高橋君は時刻 0 に座標 0 におり、数直線上を単位時間あたり 1 以下の速さで移動することができます。
すぬけ君が穴から出てきたのと同じ時刻に同じ座標に高橋君がいるとき、かつ、そのときに限り、高橋君はすぬけ君を捕まえることができます。
すぬけ君を捕まえるのにかかる時間は無視できます。

高橋君が適切に行動したとき、捕まえることができるすぬけ君の大きさの合計の最大値を求めてください。

制約

1 \leq N \leq 10^5
0 < T_1 < T_2 < \ldots < T_N \leq 10^5
0 \leq X_i \leq 4
1 \leq A_i \leq 10^9
入力に含まれる値は全て整数である

入力

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

N
T_1 X_1 A_1
T_2 X_2 A_2
\vdots
T_N X_N A_N

出力

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

入力例 1

出力例 1

次のように行動するのが最適です。

座標 0 で待機し、時刻 1 に 1 番目のすぬけ君を捕まえる
座標 4 へ移動し、時刻 5 に 3 番目のすぬけ君を捕まえる

1 番目と 2 番目のすぬけ君を両方とも捕まえることはできないので、これが最大です。

入力例 2

出力例 2

高橋君はすぬけ君を 1 匹も捕まえることができません。

入力例 3

10
1 4 602436426
2 1 623690081
3 3 262703497
4 4 628894325
5 3 450968417
6 1 161735902
7 1 707723857
8 2 802329211
9 0 317063340
10 2 125660016

出力例 3

2978279323

Score : 400 points

Problem Statement

Takahashi is trying to catch many Snuke.

There are five pits at coordinates 0, 1, 2, 3, and 4 on a number line, connected to Snuke's nest.

Now, N Snuke will appear from the pits. It is known that the i-th Snuke will appear from the pit at coordinate X_i at time T_i, and its size is A_i.

Takahashi is at coordinate 0 at time 0 and can move on the line at a speed of at most 1.
He can catch a Snuke appearing from a pit if and only if he is at the coordinate of that pit exactly when it appears.
The time it takes to catch a Snuke is negligible.

Find the maximum sum of the sizes of Snuke that Takahashi can catch by moving optimally.

Constraints

1 \leq N \leq 10^5
0 < T_1 < T_2 < \ldots < T_N \leq 10^5
0 \leq X_i \leq 4
1 \leq A_i \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
T_1 X_1 A_1
T_2 X_2 A_2
\vdots
T_N X_N A_N

Output

Print the answer as an integer.

Sample Input 1

Sample Output 1

The optimal strategy is as follows.

Wait at coordinate 0 to catch the first Snuke at time 1.
Go to coordinate 4 to catch the third Snuke at time 5.

It is impossible to catch both the first and second Snuke, so this is the best he can.

Sample Input 2

Sample Output 2

Takahashi cannot catch any Snuke.

Sample Input 3

10
1 4 602436426
2 1 623690081
3 3 262703497
4 4 628894325
5 3 450968417
6 1 161735902
7 1 707723857
8 2 802329211
9 0 317063340
10 2 125660016

Sample Output 3

2978279323