AtCoder Beginner Contest 182

A - twiblr

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

あなたは twiblr という SNS をしています。
twiblr では、フォロー数が 2\,\times\,( フォロワー数 )\,+\,100 を超えない範囲でフォロー数を増やすことができます。
あなたの現在のフォロワー数は A で、フォロー数は B です。
フォロー数はあといくつ増やせますか?

制約

0 \le A, B \le 10000
B \le 2 \times A + 100
入力は全て整数

入力

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

A B

出力

フォロー数があといくつ増やせるかを出力せよ。

入力例 1

200 300

出力例 1

フォロー数は 2 \times 200 + 100 = 500 まで増やせるので、あと 200 増やせます。

入力例 2

10000 0

出力例 2

Score : 100 points

Problem Statement

You are on a social networking site called twiblr.
In twiblr, you can follow at most 2\,\times\,( the number of users following you )\,+\,100 users.
You are currently following B users, and A users are following you.
At most, how many extra users can you follow now?

Constraints

0 \le A, B \le 10000
B \le 2 \times A + 100
All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B

Output

Print the maximum number of extra users you can follow now.

Sample Input 1

200 300

Sample Output 1

You can follow at most 2 \times 200 + 100 = 500 users, that is, 200 more users than you are following now.

Sample Input 2

10000 0

Sample Output 2

B - Almost GCD

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

数列 A\ (A_1, A_2, A_3, \dots, A_N) が与えられます。
正の整数 k の GCD 度を、A_1, A_2, A_3, \dots, A_N のうち k で割り切れるものの数と定義します。
2 以上の整数のうち GCD 度が最大になるものを一つ求めてください。 GCD 度が最大のものが複数ある場合どれを出力しても構いません。

制約

1 \le N \le 100
2 \le A_i \le 1000
入力は全て整数

入力

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

N
A_1 \hspace{7pt} A_2 \hspace{7pt} A_3 \hspace{5pt} \dots \hspace{5pt} A_N

出力

2 以上の整数のうち GCD 度が最大になるものを一つ出力せよ。GCD 度が最大のものが複数ある場合どれを出力してもよい。

入力例 1

3
3 12 7

出力例 1

3, 12, 7 のうち、 3, 12 の 2 つが 3 で割り切れるので 3 の GCD 度は 2 です。
2 以上の整数でこれより大きい GCD 度を持つものは存在しないので 3 は正答です。

入力例 2

5
8 9 18 90 72

出力例 2

この場合、 9 の GCD 度は 4 です。
2 や 3 の GCD 度も同じく 4 なので 2 や 3 を出力しても構いません。

入力例 3

5
1000 1000 1000 1000 1000

出力例 3

Score : 200 points

Problem Statement

Given is an integer sequence A: A_1, A_2, A_3, \dots, A_N.
Let the GCD-ness of a positive integer k be the number of elements among A_1, A_2, A_3, \dots, A_N that are divisible by k.
Among the integers greater than or equal to 2, find the integer with the greatest GCD-ness. If there are multiple such integers, you may print any of them.

Constraints

1 \le N \le 100
2 \le A_i \le 1000
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 \hspace{7pt} A_2 \hspace{7pt} A_3 \hspace{5pt} \dots \hspace{5pt} A_N

Output

Print an integer with the greatest GCD-ness among the integers greater than or equal to 2. If there are multiple such integers, any of them will be accepted.

Sample Input 1

3
3 12 7

Sample Output 1

Among 3, 12, and 7, two of them - 3 and 12 - are divisible by 3, so the GCD-ness of 3 is 2.
No integer greater than or equal to 2 has greater GCD-ness, so 3 is a correct answer.

Sample Input 2

5
8 9 18 90 72

Sample Output 2

In this case, the GCD-ness of 9 is 4.
2 and 3 also have the GCD-ness of 4, so you may also print 2 or 3.

Sample Input 3

5
1000 1000 1000 1000 1000

Sample Output 3

C - To 3

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

各桁に 0 が出現しないような正の整数 N が与えられます。
N の桁数を k とします。N の桁を 0 個以上 k 個未満消して、残った桁をそのままの順序で結合することで 3 の倍数を作りたいです。
3 の倍数を作ることができるか判定し、作ることができるなら作るのに必要な最少の消す桁数を求めてください。

制約

1 \le N \lt 10^{18}
N は各桁に 0 が出現しない整数

入力

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

出力

3 の倍数を作ることができないなら -1 を、作ることができるなら作るのに必要な最少の消す桁数を出力せよ。

入力例 1

出力例 1

5 を消した 3 という数は 3 の倍数です。このとき消した桁数は 1 で最少です。

入力例 2

出力例 2

1 つも桁を消さなくてもいいことに注意してください。

入力例 3

出力例 3

例えば、 8 を消した 622734 は 3 の倍数です。

入力例 4

出力例 4

-1

消す桁数は N の桁数を k として 0 個以上 k 個未満でなければならないため、全部の桁を消すことはできないことに注意してください。
この場合問題文に従って 3 の倍数を作ることは不可能なため -1 を出力します。

Score : 300 points

Problem Statement

Given is a positive integer N, where none of the digits is 0.
Let k be the number of digits in N. We want to make a multiple of 3 by erasing at least 0 and at most k-1 digits from N and concatenating the remaining digits without changing the order.
Determine whether it is possible to make a multiple of 3 in this way. If it is possible, find the minimum number of digits that must be erased to make such a number.

Constraints

1 \le N \lt 10^{18}
None of the digits in N is 0.

Input

Input is given from Standard Input in the following format:

Output

If it is impossible to make a multiple of 3, print -1; otherwise, print the minimum number of digits that must be erased to make such a number.

Sample Input 1

Sample Output 1

By erasing the 5, we get the number 3, which is a multiple of 3. Here we erased the minimum possible number of digits - 1.

Sample Input 2

Sample Output 2

Note that we can choose to erase no digit.

Sample Input 3

Sample Output 3

For example, by erasing the 8, we get the number 622734, which is a multiple of 3.

Sample Input 4

Sample Output 4

-1

Note that we must erase at least 0 and at most k-1 digits, where k is the number of digits in N, so we cannot erase all the digits.
In this case, it is impossible to make a multiple of 3 in the way described in the problem statement, so we should print -1.

D - Wandering

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

数列 A_1, A_2, A_3, \dots, A_N が与えられます。この数列は負の要素を含むかもしれません。
数直線上の座標 0 に置かれているロボットが、以下の動作を順に行います。

正の向きに A_1 進む。
正の向きに A_1 進み、正の向きに A_2 進む。
正の向きに A_1 進み、正の向きに A_2 進み、正の向きに A_3 進む。

\hspace{140pt} \vdots

正の向きに A_1 進み、正の向きに A_2 進み、正の向きに A_3 進み、\dots 、正の向きに A_N 進む。

動作開始時から終了時までのロボットの座標の最大値を求めてください。

制約

1 \le N \le 200000
-10^8 \le A_i \le 10^8
入力はすべて整数

入力

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

N
A_1 \hspace{7pt} A_2 \hspace{7pt} A_3 \hspace{5pt} \dots \hspace{5pt} A_N

出力

動作開始時から終了時までのロボットの座標の最大値を出力せよ。

入力例 1

3
2 -1 -2

出力例 1

ロボットは以下のように動きます。

正の向きに 2 進み、座標が 2 になる。
正の向きに 2 進み、座標が 4 になる。続けて正の向きに -1 進み、座標が 3 になる。
正の向きに 2 進み、座標が 5 になる。続けて正の向きに -1 進み、座標が 4 になる。更に正の向きに -2 進み、座標が 2 になる。

動作中の座標の最大値は 5 なので、 5 を出力してください。

入力例 2

5
-2 1 3 -1 -1

出力例 2

入力例 3

5
-1000 -1000 -1000 -1000 -1000

出力例 3

この場合最初にいた座標 0 が最大値です。

Score : 400 points

Problem Statement

Given is a number sequence A_1, A_2, A_3, \dots, A_N, which may contain negative elements.
On a number line, there is a robot at coordinate 0. It will do the following actions in order:

Move A_1 in the positive direction.
Move A_1 in the positive direction, and then move A_2 in the positive direction.
Move A_1 in the positive direction, then move A_2 in the positive direction, and then move A_3 in the positive direction.

\hspace{140pt} \vdots

Move A_1 in the positive direction, then move A_2 in the positive direction, then move A_3 in the positive direction, \ldots, \dots, and then move A_N in the positive direction.

Find the greatest coordinate occupied by the robot from the beginning to the end of the process.

Constraints

1 \le N \le 200000
-10^8 \le A_i \le 10^8
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 \hspace{7pt} A_2 \hspace{7pt} A_3 \hspace{5pt} \dots \hspace{5pt} A_N

Output

Print the greatest coordinate occupied by the robot from the beginning to the end of the process.

Sample Input 1

3
2 -1 -2

Sample Output 1

The robot moves as follows:

Move 2 in the positive direction, to coordinate 2.
Move 2 in the positive direction, to coordinate 4. Then move -1 in the positive direction, to coordinate 3.
Move 2 in the positive direction, to coordinate 5. Then move -1 in the positive direction, to coordinate 4. Then move -2 in the positive direction, to coordinate 2.

The greatest coordinate occupied during the process is 5, so we should print 5.

Sample Input 2

5
-2 1 3 -1 -1

Sample Output 2

Sample Input 3

5
-1000 -1000 -1000 -1000 -1000

Sample Output 3

In this case, the initial coordinate 0 is the greatest coordinate occupied.

E - Akari

Time Limit: 2.5 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

H 行 W 列のマス目があります。このマス目の i 行目 j 列目のマスをマス (i, j) と呼ぶことにします。
このマス目の上には N 個の電球と M 個のブロックが置かれていて、i 個目の電球はマス (A_i, B_i) に、i 個目のブロックはマス (C_i, D_i) に置かれています。一つのマスにある電球とブロックは合計で高々一つです。
全ての電球は、ブロックが置かれているマスに到達するまで届く光を上下左右の 4 方向に放ちます。電球が置かれているマス自身にも光が届くものとします。
マス目上のブロックの置かれていないマスのうち電球の光が届くものの数を求めてください。

制約

1 \le H, W \le 1500
1 \le N \le 5 \times 10^5
1 \le M \le 10^5
1 \le A_i \le H
1 \le B_i \le W
1 \le C_i \le H
1 \le D_i \le W
(A_i, B_i) \neq (A_j, B_j)\ \ (i \neq j)
(C_i, D_i) \neq (C_j, D_j)\ \ (i \neq j)
(A_i, B_i) \neq (C_j, D_j)
入力はすべて整数

入力

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

H W N M
A_1 B_1
A_2 B_2
A_3 B_3
\hspace{15pt} \vdots
A_N B_N
C_1 D_1
C_2 D_2
C_3 D_3
\hspace{15pt} \vdots
C_M D_M

出力

マス目上のブロックの置かれていないマスのうち、電球の光が届くものの数を出力せよ。

入力例 1

出力例 1

ブロックの置かれていないマスのうち、マス (3, 2) を除いた全てのブロックに光が届きます。

入力例 2

出力例 2

ブロックの置かれていないマスのうち、電球の光が届くものは以下の 8 個です。

マス (1, 1)
マス (1, 2)
マス (1, 3)
マス (1, 4)
マス (2, 2)
マス (3, 3)
マス (3, 4)
マス (4, 4)

入力例 3

出力例 3

この場合、ブロックが置かれていないマスには全て光が届きます。

Score : 500 points

Problem Statement

We have a grid with H rows and W columns. Let square (i, j) be the square at the i-th row and j-th column in this grid.
There are N bulbs and M blocks on this grid. The i-th bulb is at square (A_i, B_i), and the i-th block is at square (C_i, D_i). There is at most one object - a bulb or a block - at each square.
Every bulb emits beams of light in four directions - up, down, left, and right - that extend until reaching a square with a block, illuminating the squares on the way. A square with a bulb is also considered to be illuminated. Among the squares without a block, find the number of squares illuminated by the bulbs.

Constraints

1 \le H, W \le 1500
1 \le N \le 5 \times 10^5
1 \le M \le 10^5
1 \le A_i \le H
1 \le B_i \le W
1 \le C_i \le H
1 \le D_i \le W
(A_i, B_i) \neq (A_j, B_j)\ \ (i \neq j)
(C_i, D_i) \neq (C_j, D_j)\ \ (i \neq j)
(A_i, B_i) \neq (C_j, D_j)
All values in input are integers.

Input

Input is given from Standard Input in the following format:

H W N M
A_1 B_1
A_2 B_2
A_3 B_3
\hspace{15pt} \vdots
A_N B_N
C_1 D_1
C_2 D_2
C_3 D_3
\hspace{15pt} \vdots
C_M D_M

Output

Print the number of squares illuminated by the bulbs among the squares without a block.

Sample Input 1

Sample Output 1

Among the squares without a block, all but square (3, 2) are illuminated.

Sample Input 2

Sample Output 2

Among the squares without a block, the following eight are illuminated:

Square (1, 1)
Square (1, 2)
Square (1, 3)
Square (1, 4)
Square (2, 2)
Square (3, 3)
Square (3, 4)
Square (4, 4)

Sample Input 3

Sample Output 3

In this case, all the squares without a block are illuminated.

F - Valid payments

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

AtCoder 国には A_1 円玉、A_2 円玉、A_3 円玉、\dots 、A_N 円玉の N 種類のコインがあります。
ここで A_1 = 1 であり、1 \le i \lt N を満たす全ての整数 i について、 A_i \lt A_{i + 1} かつ A_{i + 1} は A_i の倍数です。

この国のある店で、犬のルンルンは X 円の商品を購入するために店員に y\ (\ge X) 円を渡し、店員はお釣りとして y - X 円を返しました。(お釣りが 0 円の可能性もあります)
このとき、ルンルンも店員もその金額をちょうど渡すのに必要な最小の枚数のコインで受け渡しを行いました。
また、ルンルンが店員に渡したコインのいずれかと同じ種類のコインが店員から返されることはありませんでした。

X が与えられるので、y として考えられる値が何通りあるかを求めてください。

制約

1 \le N \le 50
1 = A_1 \lt A_2 \lt A_3 \lt \dots \lt A_N \le 10^{15}
A_{i + 1} は A_i の倍数 (1 \le i \lt N)
1 \le X \le 10^{15}
入力はすべて整数

入力

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

N X
A_1 \hspace{7pt} A_2 \hspace{7pt} A_3 \hspace{5pt} \dots\ \hspace{5pt} A_N

出力

y として考えられる値が何通りあるかを出力せよ。

入力例 1

3 9
1 5 10

出力例 1

y として考えられる値は 9, 10, 14 です。
例えば、 y = 14 のときルンルンは 10 円玉 1 枚と 1 円玉 4 枚を渡し、店員は 5 円玉 1 枚でお釣りを返します。
このとき、ルンルンが渡したどの種類のコインも店員は返していないので条件を満たします。

入力例 2

5 198
1 5 10 50 100

出力例 2

y として考えられる値は 198, 200, 203, 208, 248 です。

入力例 3

4 44
1 4 20 100

出力例 3

y として考えられる値は 44, 60, 100, 104 です。

入力例 4

9 11837029798
1 942454037 2827362111 19791534777 257289952101 771869856303 3859349281515 30874794252120 216123559764840

出力例 4

Score : 600 points

Problem Statement

In Republic of AtCoder, N kinds of coins are used: A_1-yen, A_2-yen, A_3-yen, \dots, A_N-yen coins.
Here, A_1 = 1 holds, and for each i such that 1 \le i \lt N, A_i \lt A_{i + 1} holds and A_{i + 1} is a multiple of A_i.

At some shop in this country, Lunlun the dog bought an X-yen product by giving y\ (\ge X) yen to the clerk and receiving the change of y - X yen from the clerk. (The change may have been 0 yen.)
Here, both Lunlun and the clerk used the minimum number of coins needed to represent those amounts of money.
Additionally, the clerk did not return any kind of coins that Lunlun gave him.

Given X, find the number of possible values for y.

Constraints

1 \le N \le 50
1 = A_1 \lt A_2 \lt A_3 \lt \dots \lt A_N \le 10^{15}
A_{i + 1} is a multiple of A_i. (1 \le i \lt N)
1 \le X \le 10^{15}
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X
A_1 \hspace{7pt} A_2 \hspace{7pt} A_3 \hspace{5pt} \dots\ \hspace{5pt} A_N

Output

Print the number of possible values for y.

Sample Input 1

3 9
1 5 10

Sample Output 1

y can be 9, 10, or 14.
For example, when y = 14, Lunlun gives one 10-yen coin and four 1-yen coins, and the clerk returns one 5-yen coin.
Here, the clerk is not returning any kind of coins that Lunlun gives him, satisfying the requirement.

Sample Input 2

5 198
1 5 10 50 100

Sample Output 2

y can be 198, 200, 203, 208, or 248.

Sample Input 3

4 44
1 4 20 100

Sample Output 3

y can be 44, 60, 100, or 104.

Sample Input 4

9 11837029798
1 942454037 2827362111 19791534777 257289952101 771869856303 3859349281515 30874794252120 216123559764840