AtCoder Daily Training EASY 2025/03/05 20:00start

A - Horizon

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

地上 x メートルの高さから見える水平線は \sqrt{x(12800000+x)} メートル先にあるとするとき、地上 H メートルの高さから見える水平線が何メートル先にあるか求めてください。

制約

1 \leq H \leq 10^5
H は整数である

入力

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

出力

答えを出力せよ。
なお、想定解との絶対誤差または相対誤差が 10^{-6} 以下であれば、正解として扱われる。

入力例 1

出力例 1

65287.907678222

\sqrt{333(12800000+333)} = 65287.9076782\ldots です。65287.91 などの出力でも正解となります。

入力例 2

出力例 2

90086.635834623

\sqrt{634(12800000+634)} = 90086.6358346\ldots です。

Score : 100 points

Problem Statement

Assuming that the horizon seen from a place x meters above the ground is \sqrt{x(12800000+x)} meters away, find how many meters away the horizon seen from a place H meters above the ground is.

Constraints

1 \leq H \leq 10^5
H is an integer.

Input

Input is given from Standard Input in the following format:

Output

Print the answer.
Your answer will be considered correct when the absolute or relative error from the judge's answer is at most 10^{-6}.

Sample Input 1

Sample Output 1

65287.907678222

We have \sqrt{333(12800000+333)} = 65287.9076782\ldots. Outputs such as 65287.91 would also be accepted.

Sample Input 2

Sample Output 2

90086.635834623

We have \sqrt{634(12800000+634)} = 90086.6358346\ldots.

B - Lacked Number

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

数字のみからなる、長さがちょうど 9 の文字列 S が与えられます。
S には 0 から 9 までのうち、ちょうど 1 つの数字を除いた 9 種類の数字が一度ずつ登場します。

S に登場しない唯一の数字を出力してください。

制約

S は数字のみからなる長さ 9 の文字列である。
S の文字はすべて相異なる。

入力

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

出力

S に登場しない唯一の数字を出力せよ。

入力例 1

023456789

出力例 1

文字列 023456789 には 1 のみが登場していません。よって、1 を出力します。

入力例 2

459230781

出力例 2

文字列 459230781 には 6 のみが登場していません。よって、6 を出力します。

文字列に数字が現れる順番は昇順とは限らないので注意してください。

Score : 100 points

Problem Statement

You are given a string S of length exactly 9 consisting of digits. One but all digits from 0 to 9 appear exactly once in S.

Print the only digit missing in S.

Constraints

S is a string of length 9 consisting of digits.
All characters in S are distinct.

Input

Input is given from Standard Input in the following format:

Output

Print the only digit missing in S.

Sample Input 1

023456789

Sample Output 1

The string 023456789 only lacks 1. Thus, 1 should be printed.

Sample Input 2

459230781

Sample Output 2

The string 459230781 only lacks 6. Thus, 6 should be printed.

Note that the digits in the string may not appear in increasing order.

C - Round-Robin Tournament

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

1 から N までの番号が付いた N 人のプレイヤーが総当たり戦をしました。この総当たり戦で行われた試合全てについて、二人の一方が勝ち、もう一方が負けました。

総当たり戦の結果は N 個の長さ N の文字列 S_1,S_2,\ldots,S_N によって以下の形式で与えられます。

i\neq j のとき、S_i の j 文字目は o, x のいずれかであり、o のときプレイヤー i がプレイヤー j に勝ったことを、x のときプレイヤー i がプレイヤー j に負けたことを意味する。
i=j のとき、S_i の j 文字目は - である。

総当たり戦で勝った試合数が多いほうが順位が上であり、勝った試合数が同じ場合は、プレイヤーの番号が小さいほうが順位が上となります。 N 人のプレイヤーの番号を順位が高い順に答えてください。

制約

2\leq N\leq 100
N は整数
S_i は o, x, - からなる長さ N の文字列
S_1,\ldots,S_N は問題文中の形式を満たす

入力

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

N 
S_1
S_2
\vdots
S_N

出力

N 人のプレイヤーの番号を、順位が高い順に空白区切りで出力せよ。

入力例 1

3
-xx
o-x
oo-

出力例 1

3 2 1

プレイヤー 1 は 0 勝、プレイヤー 2 は 1 勝、プレイヤー 3 は 2 勝なので、プレイヤーの番号は順位が高い順に 3,2,1 です。

入力例 2

7
-oxoxox
x-xxxox
oo-xoox
xoo-ooo
ooxx-ox
xxxxx-x
oooxoo-

出力例 2

4 7 3 1 5 2 6

プレイヤー 4 とプレイヤー 7 はどちらも 5 勝ですが、プレイヤー番号が小さいプレイヤー 4 のほうが順位が上になります。

Score : 200 points

Problem Statement

There are N players numbered 1 to N, who have played a round-robin tournament. For every match in this tournament, one player won and the other lost.

The results of the matches are given as N strings S_1,S_2,\ldots,S_N of length N each, in the following format:

If i\neq j, the j-th character of S_i is o or x. o means that player i won against player j, and x means that player i lost to player j.
If i=j, the j-th character of S_i is -.

The player with more wins ranks higher. If two players have the same number of wins, the player with the smaller player number ranks higher. Report the player numbers of the N players in descending order of rank.

Constraints

2\leq N\leq 100
N is an integer.
S_i is a string of length N consisting of o, x, and -.
S_1,\ldots,S_N conform to the format described in the problem statement.

Input

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

N 
S_1
S_2
\vdots
S_N

Output

Print the player numbers of the N players in descending order of rank.

Sample Input 1

3
-xx
o-x
oo-

Sample Output 1

3 2 1

Player 1 has 0 wins, player 2 has 1 win, and player 3 has 2 wins. Thus, the player numbers in descending order of rank are 3,2,1.

Sample Input 2

7
-oxoxox
x-xxxox
oo-xoox
xoo-ooo
ooxx-ox
xxxxx-x
oooxoo-

Sample Output 2

4 7 3 1 5 2 6

Both players 4 and 7 have 5 wins, but player 4 ranks higher because their player number is smaller.

D - Hammer

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

数直線の原点に高橋君がいます。高橋君は座標 X にあるゴールに移動しようとしています。

座標 Y には壁があり、最初、高橋君は壁を超えて移動することができません。
座標 Z にあるハンマーを拾った後でなら、壁を破壊して通過できるようになります。

高橋君がゴールに到達することが可能か判定し、可能であれば移動距離の最小値を求めてください。

制約

-1000 \leq X,Y,Z \leq 1000
X,Y,Z は相異なり、いずれも 0 でない
入力に含まれる値は全て整数である

入力

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

X Y Z

出力

高橋君がゴールに到達することが可能であれば、移動距離の最小値を出力せよ。不可能であれば、かわりに -1 と出力せよ。

入力例 1

10 -10 1

出力例 1

高橋君はまっすぐゴールに向かうことができます。

入力例 2

20 10 -10

出力例 2

ゴールは壁の向こう側にあります。まずハンマーを拾い、壁を壊すことでゴールに到達することができます。

入力例 3

100 1 1000

出力例 3

-1

Score : 200 points

Problem Statement

Takahashi is at the origin of a number line. He wants to reach a goal at coordinate X.

There is a wall at coordinate Y, which Takahashi cannot go beyond at first.
However, after picking up a hammer at coordinate Z, he can destroy that wall and pass through.

Determine whether Takahashi can reach the goal. If he can, find the minimum total distance he needs to travel to do so.

Constraints

-1000 \leq X,Y,Z \leq 1000
X, Y, and Z are distinct, and none of them is 0.
All values in the input are integers.

Input

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

X Y Z

Output

If Takahashi can reach the goal, print the minimum total distance he needs to travel to do so. If he cannot, print -1 instead.

Sample Input 1

10 -10 1

Sample Output 1

Takahashi can go straight to the goal.

Sample Input 2

20 10 -10

Sample Output 2

The goal is beyond the wall. He can get there by first picking up the hammer and then destroying the wall.

Sample Input 3

100 1 1000

Sample Output 3

-1

E - Counting Squares

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

二次元平面があります。1 以上 9 以下の整数 r,c について、S_{r} の c 番目の文字が # であるとき座標 (r,c) にポーンが置いてあり、S_{r} の c 番目の文字が . であるとき座標 (r,c) に何も置かれていません。

この平面上の正方形であって、4 頂点全てにポーンが置いてあるものの個数を求めてください。

制約

S_1,\ldots,S_9 はそれぞれ # と . からなる長さ 9 の文字列

入力

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

S_1
S_2
\vdots
S_9

出力

答えを出力せよ。

入力例 1

##.......
##.......
.........
.......#.
.....#...
........#
......#..
.........
.........

出力例 1

座標 (1,1),(1,2),(2,2),(2,1) を頂点とする正方形は、4 頂点全てにポーンが置かれています。

座標 (4,8),(5,6),(7,7),(6,9) を頂点とする正方形も、4 頂点全てにポーンが置かれています。

よって答えは 2 です。

入力例 2

.#.......
#.#......
.#.......
.........
....#.#.#
.........
....#.#.#
........#
.........

出力例 2

Score : 300 points

Problem Statement

There is a two-dimensional plane. For integers r and c between 1 and 9, there is a pawn at the coordinates (r,c) if the c-th character of S_{r} is #, and nothing if the c-th character of S_{r} is ..

Find the number of squares in this plane with pawns placed at all four vertices.

Constraints

Each of S_1,\ldots,S_9 is a string of length 9 consisting of # and ..

Input

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

S_1
S_2
\vdots
S_9

Output

Print the answer.

Sample Input 1

##.......
##.......
.........
.......#.
.....#...
........#
......#..
.........
.........

Sample Output 1

The square with vertices (1,1), (1,2), (2,2), and (2,1) have pawns placed at all four vertices.

The square with vertices (4,8), (5,6), (7,7), and (6,9) also have pawns placed at all four vertices.

Thus, the answer is 2.

Sample Input 2

.#.......
#.#......
.#.......
.........
....#.#.#
.........
....#.#.#
........#
.........