A - Horizon

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

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

制約

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

入力

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

H

出力

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


入力例 1

333

出力例 1

65287.907678222

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


入力例 2

634

出力例 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:

H

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

333

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

634

Sample Output 2

90086.635834623

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

B - Order Something Else

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

高橋君は、レストランで「AtCoder ドリンク」というドリンクを飲もうとしています。 AtCoder ドリンクは定価である P 円を払えば飲むことができます。

また、高橋君は割引券を持っており、それを使うと AtCoder ドリンクを定価より安い価格である Q 円で飲むことができますが、 その場合には AtCoder ドリンクの他に、N 品ある料理の中から 1 つを追加で注文しなければなりません。 i = 1, 2, \ldots, N について、i 番目の料理の価格は D_i 円です。

高橋君がドリンクを飲むため支払う合計金額の最小値を出力してください。

制約

  • 1 \leq N \leq 100
  • 1 \leq Q \lt P \leq 10^5
  • 1 \leq D_i \leq 10^5
  • 入力はすべて整数

入力

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

N P Q
D_1 D_2 \ldots D_N

出力

答えを出力せよ。


入力例 1

3 100 50
60 20 40

出力例 1

70

割引券を使用して 2 番目の料理を注文することで、ドリンク代 50 円と料理代 20 円の合計 70 円の支払いで AtCoder ドリンクを飲むことができ、支払う合計金額が最小となります。


入力例 2

3 100 50
60000 20000 40000

出力例 2

100

割引券を使用せず定価の 100 円で AtCoder ドリンクを飲むことで、支払う合計金額が最小となります。

Score : 100 points

Problem Statement

Takahashi wants a beverage called AtCoder Drink in a restaurant. It can be ordered at a regular price of P yen.

He also has a discount coupon that allows him to order it at a lower price of Q yen. However, he must additionally order one of the restaurant's N dishes to use that coupon. For each i = 1, 2, \ldots, N, the price of the i-th dish is D_i yen.

Print the minimum total amount of money that he must pay to get the drink.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq Q \lt P \leq 10^5
  • 1 \leq D_i \leq 10^5
  • All input values are integers.

Input

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

N P Q
D_1 D_2 \ldots D_N

Output

Print the answer.


Sample Input 1

3 100 50
60 20 40

Sample Output 1

70

If he uses the coupon and orders the second dish, he can get the drink by paying 50 yen for it and 20 yen for the dish, for a total of 70 yen, which is the minimum total payment needed.


Sample Input 2

3 100 50
60000 20000 40000

Sample Output 2

100

The total payment will be minimized by not using the coupon and paying the regular price of 100 yen.

C - Frequency

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

英小文字からなる文字列 S が与えられます。S に最も多く出現する文字を求めてください。そのような文字が複数ある場合は、そのうちアルファベット順で最も早いものを答えてください。

制約

  • 1 \leq |S| \leq 1000(|S| は文字列 S の長さ)
  • S の各文字は英小文字である。

入力

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

S

出力

S に最も多く出現する文字のうちアルファベット順で最も早いものを出力せよ。


入力例 1

frequency

出力例 1

e

frequency には e が 2 回出現し、これは他のどの文字よりも多いため e を出力します。


入力例 2

atcoder

出力例 2

a

atcoder には a, t, c, o, d, e, r が 1 回ずつ出現するため、このうちアルファベット順で最も早い a を出力します。


入力例 3

pseudopseudohypoparathyroidism

出力例 3

o

Score: 200 points

Problem Statement

You are given a string S consisting of lowercase English letters. Find the character that appears most frequently in S. If multiple such characters exist, report the one that comes earliest in alphabetical order.

Constraints

  • 1 \leq |S| \leq 1000 (|S| is the length of the string S.)
  • Each character in S is a lowercase English letter.

Input

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

S

Output

Among the characters that appear most frequently in S, print the one that comes earliest in alphabetical order.


Sample Input 1

frequency

Sample Output 1

e

In frequency, the letter e appears twice, which is more than any other character, so you should print e.


Sample Input 2

atcoder

Sample Output 2

a

In atcoder, each of the letters a, t, c, o, d, e, and r appears once, so you should print the earliest in alphabetical order, which is a.


Sample Input 3

pseudopseudohypoparathyroidism

Sample Output 3

o
D - Overlapping sheets

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

座標平面上に N 枚の長方形のシートが張られています。

各シートが覆う長方形領域の各辺はそれぞれ x 軸または y 軸と平行であり、
具体的には、i 枚目のシートはちょうど A_i \leq x\leq B_i かつ C_i \leq y\leq D_i をみたす領域全体を覆っています。

1 枚以上のシートによって覆われている領域 の面積を S とすると、 S は制約の条件下で整数となる事が証明できます。
S を整数の形で出力してください。

制約

  • 2\leq N\leq 100
  • 0\leq A_i<B_i\leq 100
  • 0\leq C_i<D_i\leq 100
  • 入力はすべて整数

入力

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

N
A_1 B_1 C_1 D_1
A_2 B_2 C_2 D_2
\vdots
A_N B_N C_N D_N

出力

1 枚以上のシートによって覆われている領域の面積 S を整数で出力せよ。


入力例 1

3
0 5 1 3
1 4 0 5
2 5 2 4

出力例 1

20

3 枚のシートによって覆われている領域は次のようになります。
ここで、赤色・黄色・青色はそれぞれ 1 枚目・ 2 枚目・ 3 枚目のシートによって覆われている領域を表しています。

よって、1 枚以上のシートによって覆われている領域の面積は S=20 となります。


入力例 2

2
0 100 0 100
0 100 0 100

出力例 2

10000

異なるシートが同じ領域を覆っている事があることに注意してください。


入力例 3

3
0 1 0 1
0 3 0 5
5 10 0 10

出力例 3

65

Score : 200 points

Problem Statement

There are N rectangular sheets spread out on a coordinate plane.

Each side of the rectangular region covered by each sheet is parallel to the x- or y-axis.
Specifically, the i-th sheet covers exactly the region satisfying A_i \leq x\leq B_i and C_i \leq y\leq D_i.

Let S be the area of the region covered by one or more sheets. It can be proved that S is an integer under the constraints.
Print S as an integer.

Constraints

  • 2\leq N\leq 100
  • 0\leq A_i<B_i\leq 100
  • 0\leq C_i<D_i\leq 100
  • All input values are integers.

Input

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

N
A_1 B_1 C_1 D_1
A_2 B_2 C_2 D_2
\vdots
A_N B_N C_N D_N

Output

Print the area S of the region covered by one or more sheets as an integer.


Sample Input 1

3
0 5 1 3
1 4 0 5
2 5 2 4

Sample Output 1

20

The three sheets cover the following regions.
Here, red, yellow, and blue represent the regions covered by the first, second, and third sheets, respectively.

Therefore, the area of the region covered by one or more sheets is S=20.


Sample Input 2

2
0 100 0 100
0 100 0 100

Sample Output 2

10000

Note that different sheets may cover the same region.


Sample Input 3

3
0 1 0 1
0 3 0 5
5 10 0 10

Sample Output 3

65
E - Cross

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

縦 H マス横 W マスのグリッドがあります。グリッドの上から i 行目、左から j 列目のマスを (i, j) と呼びます。
グリッドの各マスには # と . のいずれかの文字が書かれています。(i, j) に書かれている文字を C[i][j] とします。また、整数 i, j が 1 \leq i \leq H と 1 \leq j \leq W の少なくとも一方を満たさない場合、 C[i][j] を . と定義します。

正整数 a, b, n が以下の条件を全て満たす時、(a,b) および (a+d,b+d),(a+d,b-d),(a-d,b+d),(a-d,b-d) (1 \leq d \leq n) の 4n + 1 マスを (a,b) を中心とするサイズ n のバツ印 と呼びます。

  • C[a][b] は # である。
  • 1 \leq d \leq n を満たす整数 d について、 C[a+d][b+d],C[a+d][b-d],C[a-d][b+d],C[a-d][b-d] はいずれも # である。
  • C[a+n+1][b+n+1],C[a+n+1][b-n-1],C[a-n-1][b+n+1],C[a-n-1][b-n-1] のうち少なくとも 1 つは . である。

例えば次の図で示された例では、(2, 2) を中心とするサイズ 1 のバツ印と (3, 7) を中心とするサイズ 2 のバツ印がグリッド上にあります。

image

グリッドにはいくつかのバツ印があります。バツ印を構成するマス以外に # は書かれていません。
また、異なるバツ印を構成するマス同士は頂点を共有しません。以下の 2 つのグリッドは異なるバツ印を構成するマス同士が頂点を共有している例で、このようなグリッドの状態は入力として与えられません。 例えば左のグリッドでは (3, 3) と (4, 4) が頂点を共有しているのが条件に反しています。

image2

N = \min(H, W) とします。また、サイズ n のバツ印の個数を S_n とします。S_1, S_2, \dots, S_N を計算してください。

制約

  • 3 \leq H, W \leq 100
  • C[i][j] は # または .
  • 異なるバツ印を構成するマス同士は頂点を共有しない
  • H, W は整数

入力

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

H W
C[1][1]C[1][2]\dots C[1][W]
C[2][1]C[2][2]\dots C[2][W]
\vdots
C[H][1]C[H][2]\dots C[H][W]

出力

S_1, S_2, \dots, S_N を空白区切りで出力せよ。


入力例 1

5 9
#.#.#...#
.#...#.#.
#.#...#..
.....#.#.
....#...#

出力例 1

1 1 0 0 0

問題文に書かれた説明の通り、(2, 2) を中心とするサイズ 1 のバツ印と (3, 7) を中心とするサイズ 2 のバツ印が書かれています。


入力例 2

3 3
...
...
...

出力例 2

0 0 0

バツ印が 1 個も書かれていない場合もあります。


入力例 3

3 16
#.#.....#.#..#.#
.#.......#....#.
#.#.....#.#..#.#

出力例 3

3 0 0

入力例 4

15 20
#.#..#.............#
.#....#....#.#....#.
#.#....#....#....#..
........#..#.#..#...
#.....#..#.....#....
.#...#....#...#..#.#
..#.#......#.#....#.
...#........#....#.#
..#.#......#.#......
.#...#....#...#.....
#.....#..#.....#....
........#.......#...
#.#....#....#.#..#..
.#....#......#....#.
#.#..#......#.#....#

出力例 4

5 0 1 0 0 0 1 0 0 0 0 0 0 0 0

Score : 300 points

Problem Statement

We have a grid with H horizontal rows and W vertical columns. We denote by (i, j) the cell at the i-th row from the top and j-th column from the left of the grid.
Each cell in the grid has a symbol # or . written on it. Let C[i][j] be the character written on (i, j). For integers i and j such that at least one of 1 \leq i \leq H and 1 \leq j \leq W is violated, we define C[i][j] to be ..

(4n+1) squares, consisting of (a, b) and (a+d,b+d),(a+d,b-d),(a-d,b+d),(a-d,b-d) (1 \leq d \leq n, 1 \leq n), are said to be a cross of size n centered at (a,b) if and only if all of the following conditions are satisfied:

  • C[a][b] is #.
  • C[a+d][b+d],C[a+d][b-d],C[a-d][b+d], and C[a-d][b-d] are all #, for all integers d such that 1 \leq d \leq n,
  • At least one of C[a+n+1][b+n+1],C[a+n+1][b-n-1],C[a-n-1][b+n+1], and C[a-n-1][b-n-1] is ..

For example, the grid in the following figure has a cross of size 1 centered at (2, 2) and another of size 2 centered at (3, 7).

image

The grid has some crosses. No # is written on the cells except for those comprising a cross.
Additionally, no two squares that comprise two different crosses share a corner. The two grids in the following figure are the examples of grids where two squares that comprise different crosses share a corner; such grids are not given as an input. For example, the left grid is invalid because (3, 3) and (4, 4) share a corner.

image2

Let N = \min(H, W), and S_n be the number of crosses of size n. Find S_1, S_2, \dots, S_N.

Constraints

  • 3 \leq H, W \leq 100
  • C[i][j] is # or ..
  • No two different squares that comprise two different crosses share a corner.
  • H and W are integers.

Input

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

H W
C[1][1]C[1][2]\dots C[1][W]
C[2][1]C[2][2]\dots C[2][W]
\vdots
C[H][1]C[H][2]\dots C[H][W]

Output

Print S_1, S_2, \dots, and S_N, separated by spaces.


Sample Input 1

5 9
#.#.#...#
.#...#.#.
#.#...#..
.....#.#.
....#...#

Sample Output 1

1 1 0 0 0

As described in the Problem Statement, there are a cross of size 1 centered at (2, 2) and another of size 2 centered at (3, 7).


Sample Input 2

3 3
...
...
...

Sample Output 2

0 0 0

There may be no cross.


Sample Input 3

3 16
#.#.....#.#..#.#
.#.......#....#.
#.#.....#.#..#.#

Sample Output 3

3 0 0

Sample Input 4

15 20
#.#..#.............#
.#....#....#.#....#.
#.#....#....#....#..
........#..#.#..#...
#.....#..#.....#....
.#...#....#...#..#.#
..#.#......#.#....#.
...#........#....#.#
..#.#......#.#......
.#...#....#...#.....
#.....#..#.....#....
........#.......#...
#.#....#....#.#..#..
.#....#......#....#.
#.#..#......#.#....#

Sample Output 4

5 0 1 0 0 0 1 0 0 0 0 0 0 0 0