AtCoder Beginner Contest 180

A - box

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

N 個のボールが入っていた箱から A 個のボールを取り出し、新たに B 個のボールを入れました。今、箱にはボールが何個入っていますか?

制約

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

入力

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

N A B

出力

答えを整数で出力せよ。

入力例 1

100 1 2

出力例 1

箱にはもともと 100 個のボールが入っていましたが 1 個のボールを取り出し、新たに 2 個のボールを入れたことで、今は 101 個のボールが入っています。

入力例 2

100 2 1

出力例 2

入力例 3

100 1 1

出力例 3

Score : 100 points

Problem Statement

We have removed A balls from a box that contained N balls and then put B new balls into that box. How many balls does the box contain now?

Constraints

All values in input are integers.
100 \leq N \leq 200
1 \leq A,B \leq 100

Input

Input is given from Standard Input in the following format:

N A B

Output

Print the answer as an integer.

Sample Input 1

100 1 2

Sample Output 1

The box contained 100 balls. After removing 1 ball and putting 2 new balls, it now contains 101 balls.

Sample Input 2

100 2 1

Sample Output 2

Sample Input 3

100 1 1

Sample Output 3

B - Various distances

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

N 次元空間内の点 (x_1,\ldots,x_N) が与えられます。

原点からこの点までの、マンハッタン距離、ユークリッド距離、チェビシェフ距離をそれぞれ求めてください。ただし、それぞれの距離は次のように計算されます。

マンハッタン距離： |x_1|+\ldots+|x_N|
ユークリッド距離： \sqrt{|x_1|^2+\ldots+|x_N|^2}
チェビシェフ距離： \max(|x_1|,\ldots,|x_N|)

制約

1 \leq N \leq 10^5
-10^5 \leq x_i \leq 10^5
入力は全て整数

入力

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

N
x_1 \ldots x_N

出力

原点から与えられた点までの、マンハッタン距離、ユークリッド距離、チェビシェフ距離をそれぞれこの順に改行区切りで出力せよ。正しい値との絶対誤差または相対誤差が 10^{-9} 以下であれば正解とみなされる。

入力例 1

2
2 -1

出力例 1

3
2.236067977499790
2

それぞれ次のように計算されます。

マンハッタン距離： |2|+|-1|=3
ユークリッド距離： \sqrt{|2|^2+|-1|^2}=2.236067977499789696\ldots
チェビシェフ距離： \max(|2|,|-1|)=2

入力例 2

10
3 -1 -4 1 -5 9 2 -6 5 -3

出力例 2

39
14.387494569938159
9

Score : 200 points

Problem Statement

Given is a point (x_1,\ldots,x_N) in an N-dimensional space.

Find the Manhattan distance, Euclidian distance, and Chebyshev distance between this point and the origin. Here, each of them is defined as follows:

The Manhattan distance: |x_1|+\ldots+|x_N|
The Euclidian distance: \sqrt{|x_1|^2+\ldots+|x_N|^2}
The Chebyshev distance: \max(|x_1|,\ldots,|x_N|)

Constraints

1 \leq N \leq 10^5
-10^5 \leq x_i \leq 10^5
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 \ldots x_N

Output

Print the Manhattan distance, Euclidian distance, and Chebyshev distance between the given point and the origin, each in its own line. Each value in your print will be accepted when its absolute or relative error from the correct value is at most 10^{-9}.

Sample Input 1

2
2 -1

Sample Output 1

3
2.236067977499790
2

Each of the distances is computed as follows:

The Manhattan distance: |2|+|-1|=3
The Euclidian distance: \sqrt{|2|^2+|-1|^2}=2.236067977499789696\ldots
The Chebyshev distance: \max(|2|,|-1|)=2

Sample Input 2

10
3 -1 -4 1 -5 9 2 -6 5 -3

Sample Output 2

39
14.387494569938159
9

C - Cream puff

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

N 個のシュークリームがあります。

シュークリームを分割することなく平等に分けることができるような人数としてあり得るものを全て求めてください。

制約

1 \leq N \leq 10^{12}
N は整数

入力

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

出力

答えを改行区切りで昇順に出力せよ。

入力例 1

出力例 1

例えば、2 人で分けるには 1 人あたり 3 個とすればよいです。

入力例 2

出力例 2

入力例 3

1000000007

出力例 3

1
1000000007

Score : 300 points

Problem Statement

We have N cream puffs.

Find all possible number of people to which we can evenly distribute the cream puffs without cutting them.

Constraints

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

Input

Input is given from Standard Input in the following format:

Output

Print the numbers of people in ascending order, each in its own line.

Sample Input 1

Sample Output 1

For example, we can evenly distribute the cream puffs to two people by giving three to each person.

Sample Input 2

Sample Output 2

Sample Input 3

1000000007

Sample Output 3

1
1000000007

D - Takahashi Unevolved

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

いろはちゃんはペットを育てるゲームにはまっています。

いろはちゃんはペットとして高橋君を飼っており、はじめ高橋君の強さは X 、経験値 は 0 です。これらの値は次の 2 種類の特訓によって増加します。

カコモンジムに通う：強さが A 倍になり、経験値は 1 増える。
AtCoderジムに通う：強さが B 増え、経験値は 1 増える。

高橋君は強さが Y 以上になると進化しますが、進化しない方がかわいいといろはちゃんは思っています。

そこで、強さが Y 以上にならないように高橋君に特訓を課すとき、経験値の最大値を求めてください。

制約

1 \leq X < Y \leq 10^{18}
2 \leq A \leq 10^9
1 \leq B \leq 10^9
入力は全て整数

入力

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

X Y A B

出力

与えられた条件の下での経験値の最大値を出力せよ。

入力例 1

4 20 2 10

出力例 1

最初、高橋君の強さは 4 です。次のような特訓方法によって、経験値を 2 にすることができます。

まずカコモンジムに通うことで、高橋君の強さは 8、経験値は 1 になります。
次に、AtCoderジムに通うことで、高橋君の強さは 18、経験値は 2 になります。

どのような特訓方法によっても、経験値を 2 より大きくすることはできません。

入力例 2

1 1000000000000000000 10 1000000000

出力例 2

1000000007

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

Score : 400 points

Problem Statement

Iroha is into a game where you keep pets.

Iroha's pet is Takahashi. Initially, Takahashi's STR and EXP are X and 0, respectively. These parameters increase in the following two kinds of training:

Go to Kakomon Gym: the STR gets multiplied by A, and the EXP increases by 1.
Go to AtCoder Gym: the STR increases by B, and the EXP increases by 1.

Takahashi evolves when his STR becomes Y or greater, but Iroha thinks that makes him less cute.

Find the maximum possible EXP of Takahashi when he is trained without letting him evolve.

Constraints

1 \leq X < Y \leq 10^{18}
2 \leq A \leq 10^9
1 \leq B \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

X Y A B

Output

Print the maximum possible EXP of Takahashi under the given situation.

Sample Input 1

4 20 2 10

Sample Output 1

Initially, Takahashi's STR is 4. We can make his EXP 2 in the following course of training:

First, go to Kakomon Gym, which makes his STR 8 and his EXP 1.
Then, go to AtCoder Gym, which makes his STR 18 and his EXP 2.

On the other hand, there is no way to train him so that his EXP becomes greater than 2.

Sample Input 2

1 1000000000000000000 10 1000000000

Sample Output 2

1000000007

Watch out for overflows.

E - Traveling Salesman among Aerial Cities

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

3 次元空間内に N 個の都市、都市 1 から都市 N があります。都市 i は座標 (X_i,Y_i,Z_i) にあります。

座標 (a,b,c) の都市から (p,q,r) の都市に移動する際には |p-a|+|q-b|+\max(0,r-c) のコストがかかります。

都市 1 からスタートし、全ての都市を 1 度以上巡って都市 1 に戻るまでの最小コストを求めてください。

制約

2 \leq N \leq 17
-10^6 \leq X_i,Y_i,Z_i \leq 10^6
同じ座標に複数の都市があることはない
入力は全て整数

入力

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

N
X_1 Y_1 Z_1
\vdots
X_N Y_N Z_N

出力

都市 1 からスタートし、全ての都市を 1 度以上巡って都市 1 に戻るまでの最小コストを出力せよ。

入力例 1

2
0 0 0
1 2 3

出力例 1

都市 1 から都市 2 へ向かう時には |1-0|+|2-0|+\max(0,3-0)=6 のコストがかかります。

都市 2 から都市 1 へ向かう時には |0-1|+|0-2|+\max(0,0-3)=3 のコストがかかります。

よって合計で 9 のコストがかかります。

入力例 2

出力例 2

例えば都市 1, 2, 1, 3, 1 の順に移動するとコストが 10 になります。途中で都市 1 に戻ってきても構いません。

入力例 3

17
14142 13562 373095
-17320 508075 68877
223606 -79774 9979
-24494 -89742 783178
26457 513110 -64591
-282842 7124 -74619
31622 -77660 -168379
-33166 -24790 -3554
346410 16151 37755
-36055 51275 463989
37416 -573867 73941
-3872 -983346 207417
412310 56256 -17661
-42426 40687 -119285
43588 -989435 -40674
-447213 -59549 -99579
45825 7569 45584

出力例 3

Score : 500 points

Problem Statement

In a three-dimensional space, there are N cities: City 1 through City N. City i is at point (X_i,Y_i,Z_i).

The cost it takes to travel from a city at point (a,b,c) to a city at point (p,q,r) is |p-a|+|q-b|+\max(0,r-c).

Find the minimum total cost it takes to start at City 1, visit all other cities at least once, and return to City 1.

Constraints

2 \leq N \leq 17
-10^6 \leq X_i,Y_i,Z_i \leq 10^6
No two cities are at the same point.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
X_1 Y_1 Z_1
\vdots
X_N Y_N Z_N

Output

Print the minimum total cost it takes to start at City 1, visit all other cities at least once, and return to City 1.

Sample Input 1

2
0 0 0
1 2 3

Sample Output 1

The cost it takes to travel from City 1 to City 2 is |1-0|+|2-0|+\max(0,3-0)=6.

The cost it takes to travel from City 2 to City 1 is |0-1|+|0-2|+\max(0,0-3)=3.

Thus, the total cost will be 9.

Sample Input 2

Sample Output 2

For example, we can visit the cities in the order 1, 2, 1, 3, 1 to make the total cost 10. Note that we can come back to City 1 on the way.

Sample Input 3

17
14142 13562 373095
-17320 508075 68877
223606 -79774 9979
-24494 -89742 783178
26457 513110 -64591
-282842 7124 -74619
31622 -77660 -168379
-33166 -24790 -3554
346410 16151 37755
-36055 51275 463989
37416 -573867 73941
-3872 -983346 207417
412310 56256 -17661
-42426 40687 -119285
43588 -989435 -40674
-447213 -59549 -99579
45825 7569 45584

Sample Output 3

F - Unbranched

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

頂点にラベルが付き辺にはラベルが付いていない N 頂点 M 辺の単純とも連結とも限らないグラフであって、以下の条件を満たすものの個数を 10^9+7 で割ったあまりを求めてください。

自己ループを持たない
すべての頂点の次数が 2 以下である
各連結成分のサイズを並べたとき、その最大値がちょうど L である

制約

2 \leq N \leq 300
1\leq M \leq N
1 \leq L \leq N
入力はすべて整数

入力

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

N M L

出力

答えを出力せよ。

入力例 1

3 2 3

出力例 1

頂点に 1 から N の番号を付けたとき、以下の 3 通りのグラフが条件を満たします。

1-2 間と 2-3 間に辺がある。
1-2 間と 1-3 間に辺がある。
1-3 間と 2-3 間に辺がある。

入力例 2

4 3 2

出力例 2

入力例 3

300 290 140

出力例 3

211917445

Score : 600 points

Problem Statement

Find the number of graphs with N labeled vertices and M unlabeled edges, not necessarily simple or connected, that satisfy the following conditions, modulo (10^9+7):

There is no self-loop;
The degree of every vertex is at most 2;
The maximum of the sizes of the connected components is exactly L.

Constraints

2 \leq N \leq 300
1\leq M \leq N
1 \leq L \leq N
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M L

Output

Print the answer.

Sample Input 1

3 2 3

Sample Output 1

When the vertices are labeled 1 through N, the following three graphs satisfy the condition:

The graph with edges 1-2 and 2-3;
The graph with edges 1-2 and 1-3;
The graph with edges 1-3 and 2-3.

Sample Input 2

4 3 2

Sample Output 2

Sample Input 3

300 290 140

Sample Output 3

211917445