A - Find Takahashi

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

AtCoder 村には N 本の橋があり、i 本目( i は 1 以上 N 以下の整数)の橋の高さは H_i です。
ここで、AtCoder 村にある N 本の橋のうち、どの相異なる 2 本の橋も高さが異なります。

AtCoder 村で最も高い橋は何本目の橋か出力してください。

制約

  • 1\leq N \leq 100
  • 1\leq H_i \leq 10^9
  • H_i はすべて異なる
  • 入力はすべて整数

入力

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

N
H_1 H_2 \ldots H_N

出力

AtCoder 村で最も高い橋は何本目の橋かを、整数で出力せよ。


入力例 1

3
50 80 70

出力例 1

2

AtCoder 村には 3 本の橋があります。
1,2,3 本目の橋の高さはそれぞれ, 50,80,70 であり、 最も高い橋は 2 本目の橋です。
よって、2 を出力します。


入力例 2

1
1000000000

出力例 2

1

AtCoder 村に橋が 1 本しか存在しないため、2 本目以降の橋は存在せず、最も高い橋は 1 本目の橋となります。


入力例 3

10
22 75 26 45 72 81 47 29 97 2

出力例 3

9

AtCoder 村には 10 本の橋があり、それらのうち最も高い橋は 9 番目の橋(高さは 97 )です。

Score : 100 points

Problem Statement

There are N bridges in AtCoder Village. The height of the bridge numbered i is H_i (i is an integer between 1 and N).
Every two different bridges in the village have different heights.

Print the number representing the highest bridge in the village.

Constraints

  • 1\leq N \leq 100
  • 1\leq H_i \leq 10^9
  • All H_i are different.
  • All values in the input are integers.

Input

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

N
H_1 H_2 \ldots H_N

Output

Print the integer representing the highest bridge in AtCoder village.


Sample Input 1

3
50 80 70

Sample Output 1

2

The village has three bridges.
The first, second, and third bridges have heights of 50, 80, and 70, respectively, so the second bridge is the highest.
Thus, 2 should be printed.


Sample Input 2

1
1000000000

Sample Output 2

1

The village has only one bridge, so the first bridge is the highest.


Sample Input 3

10
22 75 26 45 72 81 47 29 97 2

Sample Output 3

9

The village has ten bridges, and the ninth bridge (with a height of 97) is the highest.

B - Intersection

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

数直線があり、高橋君はこれを赤色と青色で次のように塗りました。

  • X=L_1 から X=R_1 までをすべて赤色で塗る。
  • X=L_2 から X=R_2 までをすべて青色で塗る。

数直線のうち、赤色と青色の両方で塗られている部分の長さを求めてください。

制約

  • 0\leq L_1<R_1\leq 100
  • 0\leq L_2<R_2\leq 100
  • 入力はすべて整数

入力

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

L_1 R_1 L_2 R_2

出力

両方の色で塗られている部分の長さを整数で出力せよ。


入力例 1

0 3 1 5

出力例 1

2

X=0 から X=3 までが赤く、 X=1 から X=5 までが青く塗られています。

よって、両方の色で塗られている部分は X=1 から X=3 までであり、その長さは 2 となります。


入力例 2

0 1 4 5

出力例 2

0

両方の色で塗られている部分はありません。


入力例 3

0 3 3 7

出力例 3

0

赤色と青色で塗られている部分が接している場合でも、 両方の色で塗られている部分の長さは 0 となります。

Score : 100 points

Problem Statement

We have a number line. Takahashi painted some parts of this line, as follows:

  • First, he painted the part from X=L_1 to X=R_1 red.
  • Next, he painted the part from X=L_2 to X=R_2 blue.

Find the length of the part of the line painted both red and blue.

Constraints

  • 0\leq L_1<R_1\leq 100
  • 0\leq L_2<R_2\leq 100
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

L_1 R_1 L_2 R_2

Output

Print the length of the part of the line painted both red and blue, as an integer.


Sample Input 1

0 3 1 5

Sample Output 1

2

The part from X=0 to X=3 is painted red, and the part from X=1 to X=5 is painted blue.

Thus, the part from X=1 to X=3 is painted both red and blue, and its length is 2.


Sample Input 2

0 1 4 5

Sample Output 2

0

No part is painted both red and blue.


Sample Input 3

0 3 3 7

Sample Output 3

0

If the part painted red and the part painted blue are adjacent to each other, the length of the part painted both red and blue is 0.

C - Perfect String

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

英大文字と英小文字からなる文字列のうち、以下の条件を全て満たすものを素晴らしい文字列ということとします。

  • 英大文字が文字列の中に現れる。
  • 英小文字が文字列の中に現れる。
  • 全ての文字が相異なる。

例えば、AtCoder や Aa は素晴らしい文字列ですが、atcoder や Perfect は素晴らしい文字列ではありません。

文字列 S が与えられるので、S が素晴らしい文字列か判定してください。

制約

  • 1 \le |S| \le 100
  • S は英大文字と英小文字からなる文字列である。

入力

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

S

出力

S が素晴らしい文字列ならば Yes を、そうでないならば No を出力せよ。


入力例 1

AtCoder

出力例 1

Yes

AtCoder は、英大文字が含まれ、英小文字も含まれ、かつ全ての文字が相異なるため素晴らしい文字列です。


入力例 2

Aa

出力例 2

Yes

A と a は違う文字であることに注意してください。この文字列は素晴らしい文字列です。


入力例 3

atcoder

出力例 3

No

英大文字が含まれていないため、素晴らしい文字列ではありません。


入力例 4

Perfect

出力例 4

No

2 文字目と 5 文字目が等しいため、素晴らしい文字列ではありません。

Score : 200 points

Problem Statement

Let us call a string consisting of uppercase and lowercase English alphabets a wonderful string if all of the following conditions are satisfied:

  • The string contains an uppercase English alphabet.
  • The string contains a lowercase English alphabet.
  • All characters in the string are pairwise distinct.

For example, AtCoder and Aa are wonderful strings, while atcoder and Perfect are not.

Given a string S, determine if S is a wonderful string.

Constraints

  • 1 \le |S| \le 100
  • S is a string consisting of uppercase and lowercase English alphabets.

Input

Input is given from Standard Input in the following format:

S

Output

If S is a wonderful string, print Yes; otherwise, print No.


Sample Input 1

AtCoder

Sample Output 1

Yes

AtCoder is a wonderful string because it contains an uppercase English alphabet, a lowercase English alphabet, and all characters in the string are pairwise distinct.


Sample Input 2

Aa

Sample Output 2

Yes

Note that A and a are different characters. This string is a wonderful string.


Sample Input 3

atcoder

Sample Output 3

No

It is not a wonderful string because it does not contain an uppercase English alphabet.


Sample Input 4

Perfect

Sample Output 4

No

It is not a wonderful string because the 2-nd and the 5-th characters are the same.

D - Line Sensor

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

縦 H マス、横 W マスのグリッドがあります。上から i 行目、左から j 列目のマスを (i,j) と表します。
各マスの状態は文字 C_{i,j} で表されます。C_{i,j} が . ならば (i, j) には何も置かれておらず、 # ならば箱が 1 個置かれています。

1 \leq j \leq W を満たす整数 j に対して、整数 X_j を次のように定義します。

  • j 列目に置かれている箱の個数。言い換えると、C_{i,j} が # であるような整数 i の個数。

X_1, X_2, \dots, X_W をすべて求めてください。

制約

  • 1 \leq H \leq 1000
  • 1 \leq W \leq 1000
  • H, W は整数
  • C_{i, j} は . または #

入力

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

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}

出力

X_1, X_2, \dots, X_W を以下の形式に従って出力せよ。

X_1 X_2 \dots X_W

入力例 1

3 4
#..#
.#.#
.#.#

出力例 1

1 2 0 3

1 列目の箱が置かれているマスは (1, 1) の 1 ヵ所です。よって X_1 = 1 です。
2 列目の箱が置かれているマスは (2, 2), (3, 2) の 2 ヵ所です。よって X_2 = 2 です。
3 列目の箱が置かれているマスは存在しません。よって X_3 = 0 です。
4 列目の箱が置かれているマスは (1, 4), (2, 4), (3, 4) の 3 ヵ所です。よって X_4 = 3 です。
よって (X_1, X_2, X_3, X_4) = (1, 2, 0, 3) が答えとなります。


入力例 2

3 7
.......
.......
.......

出力例 2

0 0 0 0 0 0 0

箱が置かれているマスが存在しない場合もあります。


入力例 3

8 3
.#.
###
.#.
.#.
.##
..#
##.
.##

出力例 3

2 7 4

入力例 4

5 47
.#..#..#####..#...#..#####..#...#...###...#####
.#.#...#.......#.#...#......##..#..#...#..#....
.##....#####....#....#####..#.#.#..#......#####
.#.#...#........#....#......#..##..#...#..#....
.#..#..#####....#....#####..#...#...###...#####

出力例 4

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

Score : 200 points

Problem Statement

There is a grid with H rows from top to bottom and W columns from left to right. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.
The squares are described by characters C_{i,j}. If C_{i,j} is ., (i, j) is empty; if it is #, (i, j) contains a box.

For integers j satisfying 1 \leq j \leq W, let the integer X_j defined as follows.

  • X_j is the number of boxes in the j-th column. In other words, X_j is the number of integers i such that C_{i,j} is #.

Find all of X_1, X_2, \dots, X_W.

Constraints

  • 1 \leq H \leq 1000
  • 1 \leq W \leq 1000
  • H and W are integers.
  • C_{i, j} is . or #.

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 X_1, X_2, \dots, X_W in the following format:

X_1 X_2 \dots X_W

Sample Input 1

3 4
#..#
.#.#
.#.#

Sample Output 1

1 2 0 3

In the 1-st column, one square, (1, 1), contains a box. Thus, X_1 = 1.
In the 2-nd column, two squares, (2, 2) and (3, 2), contain a box. Thus, X_2 = 2.
In the 3-rd column, no squares contain a box. Thus, X_3 = 0.
In the 4-th column, three squares, (1, 4), (2, 4), and (3, 4), contain a box. Thus, X_4 = 3.
Therefore, the answer is (X_1, X_2, X_3, X_4) = (1, 2, 0, 3).


Sample Input 2

3 7
.......
.......
.......

Sample Output 2

0 0 0 0 0 0 0

There may be no square that contains a box.


Sample Input 3

8 3
.#.
###
.#.
.#.
.##
..#
##.
.##

Sample Output 3

2 7 4

Sample Input 4

5 47
.#..#..#####..#...#..#####..#...#...###...#####
.#.#...#.......#.#...#......##..#..#...#..#....
.##....#####....#....#####..#.#.#..#......#####
.#.#...#........#....#......#..##..#...#..#....
.#..#..#####....#....#####..#...#...###...#####

Sample Output 4

0 5 1 2 2 0 0 5 3 3 3 3 0 0 1 1 3 1 1 0 0 5 3 3 3 3 0 0 5 1 1 1 5 0 0 3 2 2 2 2 0 0 5 3 3 3 3
E - Invisible Hand

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

りんご市場に N 人の売り手と M 人の買い手がいます。

i 番目の売り手は、A_i 円以上でならりんごを売ってもよいと考えています。

i 番目の買い手は、B_i 円以下でならりんごを買ってもよいと考えています。

次の条件を満たすような最小の整数 X を求めてください。

条件:りんごを X 円で売ってもよいと考える売り手の人数が、りんごを X 円で買ってもよいと考える買い手の人数以上である。

制約

  • 1 \leq N,M \leq 2\times 10^5
  • 1\leq A_i,B_i \leq 10^9
  • 入力は全て整数である

入力

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

N M
A_1 \ldots A_N
B_1 \ldots B_M

出力

答えを出力せよ。


入力例 1

3 4
110 90 120
100 80 120 10000

出力例 1

110

りんごを 110 円で売ってもよいと考える売り手は 1,2 番目の 2 人であり、りんごを 110 円で買ってもよいと考える買い手は 3,4 番目の 2 人であるため、110 は条件を満たします。

110 未満の整数が条件を満たすことはないため、これが答えです。


入力例 2

5 2
100000 100000 100000 100000 100000
100 200

出力例 2

201

入力例 3

3 2
100 100 100
80 120

出力例 3

100

Score : 300 points

Problem Statement

There are N sellers and M buyers in an apple market.

The i-th seller may sell an apple for A_i yen or more (yen is the currency in Japan).

The i-th buyer may buy an apple for B_i yen or less.

Find the minimum integer X that satisfies the following condition.

Condition: The number of people who may sell an apple for X yen is greater than or equal to the number of people who may buy an apple for X yen.

Constraints

  • 1 \leq N,M \leq 2\times 10^5
  • 1\leq A_i,B_i \leq 10^9
  • All input values are integers.

Input

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

N M
A_1 \ldots A_N
B_1 \ldots B_M

Output

Print the answer.


Sample Input 1

3 4
110 90 120
100 80 120 10000

Sample Output 1

110

Two sellers, the 1-st and 2-nd, may sell an apple for 110 yen; two buyers, the 3-rd and 4-th, may buy an apple for 110 yen. Thus, 110 satisfies the condition.

Since an integer less than 110 does not satisfy the condition, this is the answer.


Sample Input 2

5 2
100000 100000 100000 100000 100000
100 200

Sample Output 2

201

Sample Input 3

3 2
100 100 100
80 120

Sample Output 3

100