A - wwwvvvvvv

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

v と w のみからなる文字列 S が与えられます。

S の中に、下に尖っている部分が何箇所あるかを出力してください(入出力例にある図もご参照ください)。

制約

  • S は v と w のみからなる文字列
  • S の長さは 1 以上 100 以下

入力

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

S

出力

答えを整数として出力せよ。


入力例 1

vvwvw

出力例 1

7

vvwvw

上の画像のように、vvwvw という文字列には下に尖った部分が 7 箇所あります。


入力例 2

v

出力例 2

1

入力例 3

wwwvvvvvv

出力例 3

12

Score : 100 points

Problem Statement

You are given a string S consisting of v and w.

Print the number of "bottoms" in the string S (see the figure at Sample Input/Output).

Constraints

  • S is a string consisting of v and w.
  • The length of S is between 1 and 100, inclusive.

Input

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

S

Output

Print the answer as an integer.


Sample Input 1

vvwvw

Sample Output 1

7

vvwvw

The image above shows the seven "bottoms" in the string vvwvw.


Sample Input 2

v

Sample Output 2

1

Sample Input 3

wwwvvvvvv

Sample Output 3

12
B - First Player

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

人 1 、人 2 、\ldots 、人 N と番号付けられた N 人が、この順番で時計回りに円卓に座っています。 特に、時計回りで人 N の次の位置には人 1 が座っています。

i = 1, 2, \ldots, N について、人 i の名前は S_i 、年齢は A_i です。 ここで、異なる 2 人が同じ名前や同じ年齢であることはありません。

年齢が最も小さい人を起点として、座っている位置の時計回りの順番で、N 人全員の名前を出力してください。

制約

  • 2 \leq N \leq 100
  • N は整数
  • S_i は英小文字のみからなる長さ 1 以上 10 以下の文字列
  • i \neq j \implies S_i \neq S_j
  • 0 \leq A_i \leq 10^9
  • A_i は整数
  • i \neq j \implies A_i \neq A_j

入力

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

N
S_1 A_1
S_2 A_2
\vdots
S_N A_N

出力

N 行出力せよ。 i = 1, 2, \ldots, N について、i 行目には、年齢が最も小さい人を起点として時計回りで i 番目の位置に座っている人の名前を出力せよ。


入力例 1

5
alice 31
bob 41
carol 5
dave 92
ellen 65

出力例 1

carol
dave
ellen
alice
bob

年齢が最も小さい人は人 3 です。よって、人 3 を起点として座っている位置の時計回りの順番、すなわち、人 3 、人 4 、人 5 、人 1 、人 2 の順に名前を出力します。


入力例 2

2
takahashi 1000000000
aoki 999999999

出力例 2

aoki
takahashi

Score : 100 points

Problem Statement

There are N people numbered 1, 2, \ldots, N, sitting in this clockwise order around a round table. In particular, person 1 is sitting next to person N in the clockwise direction.

For each i = 1, 2, \ldots, N, person i has a name S_i and an age A_i. Here, no two people have the same name or the same age.

Starting from the youngest person, print the names of all N people in the order of their seating positions in clockwise order.

Constraints

  • 2 \leq N \leq 100
  • N is an integer.
  • S_i is a string of length between 1 and 10, consisting of lowercase English letters.
  • i \neq j \implies S_i \neq S_j
  • 0 \leq A_i \leq 10^9
  • A_i is an integer.
  • i \neq j \implies A_i \neq A_j

Input

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

N
S_1 A_1
S_2 A_2
\vdots
S_N A_N

Output

Print N lines. For each i = 1, 2, \ldots, N, the i-th line should contain the name of the person sitting in the i-th position clockwise from the youngest person.


Sample Input 1

5
alice 31
bob 41
carol 5
dave 92
ellen 65

Sample Output 1

carol
dave
ellen
alice
bob

The youngest person is person 3. Therefore, starting from person 3, print the names in the clockwise order of their seating positions: person 3, person 4, person 5, person 1, and person 2.


Sample Input 2

2
takahashi 1000000000
aoki 999999999

Sample Output 2

aoki
takahashi
C - Minimize Abs 1

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

長さ N の整数列 A=(A_1,A_2,\ldots,A_N) 及び整数 L,R が与えられます。ここで L,R は L\leq R を満たします。

i=1,2,\ldots,N について以下の 2 つの条件を共に満たす整数 X_i を求めてください。なお、求める整数は常に一意に定まります。

  • L\leq X_i \leq R
  • L 以上 R 以下であるようなどの整数 Y についても |X_i - A_i| \leq |Y-A_i| を満たす

制約

  • 1\leq N\leq 2\times 10^5
  • 1\leq L\leq R \leq 10^9
  • 1\leq A_i\leq 10^9
  • 入力は全て整数

入力

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

N L R
A_1 \ldots A_N

出力

i=1,2,\ldots,N について X_i を空白区切りで出力せよ。


入力例 1

5 4 7
3 1 4 9 7

出力例 1

4 4 4 7 7

i=1 では、

  • |4-3|=1
  • |5-3|=2
  • |6-3|=3
  • |7-3|=4

より X_i = 4 です。


入力例 2

3 10 10
11 10 9

出力例 2

10 10 10

Score : 200 points

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N and integers L and R such that L\leq R.

For each i=1,2,\ldots,N, find the integer X_i that satisfies both of the following conditions. Note that the integer to be found is always uniquely determined.

  • L\leq X_i \leq R.
  • For every integer Y such that L \leq Y \leq R, it holds that |X_i - A_i| \leq |Y - A_i|.

Constraints

  • 1\leq N\leq 2\times 10^5
  • 1\leq L\leq R \leq 10^9
  • 1\leq A_i\leq 10^9
  • All input values are integers.

Input

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

N L R
A_1 \ldots A_N

Output

Print X_i for i=1,2,\ldots,N, separated by spaces.


Sample Input 1

5 4 7
3 1 4 9 7

Sample Output 1

4 4 4 7 7

For i=1:

  • |4-3|=1
  • |5-3|=2
  • |6-3|=3
  • |7-3|=4

Thus, X_i = 4.


Sample Input 2

3 10 10
11 10 9

Sample Output 2

10 10 10
D - Japanese Cursed Doll

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

N 人の人がおり、i 人目 (1\leq i\leq N) の現在の髪の長さは L_i です。
すべての人は 1 日経つごとに髪の長さが 1 ずつ増えます。

髪の長さが T 以上の人が初めて P 人以上になるのは現在から何日後か出力してください。
ただし、現在の時点ですでに髪の長さが T 以上の人が P 人以上にいる場合は 0 を出力してください。

制約

  • 1\leq N\leq 100
  • 1\leq L_i\leq 100
  • 1\leq T\leq 100
  • 1\leq P\leq N
  • 入力はすべて整数

入力

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

N T P
L_1 L_2 \ldots L_N

出力

髪の長さが T 以上の人が初めて P 人以上になるのは現在から何日後か出力せよ。 ただし、現在の時点ですでに条件をみたしている場合は 0 を出力せよ。


入力例 1

5 10 3
3 11 1 6 2

出力例 1

7

5 人の人がおり、現在の時点で髪の長さはそれぞれ 3,11,1,6,2 であるため、髪の長さが 10 以上の人は 1 人です。

現在から 7 日後にはそれぞれの人の髪の長さは順に 10,18,8,13,9 となり、髪の長さが 10 以上の人は 3 人となります。
現在から 6 日後の時点では髪の長さが 10 以上の人は 2 人であるため条件をみたしておらず、よって 7 を出力します。


入力例 2

2 5 2
10 10

出力例 2

0

現在の時点ですでに髪の長さが 5 以上の人が 2 人いるため条件をみたしており、0 を出力します。


入力例 3

3 10 1
1 2 3

出力例 3

7

Score : 200 points

Problem Statement

There are N people, and the current hair length of the i-th person (1 \leq i \leq N) is L_i.
Each person's hair grows by 1 per day.

Print the number of days after which the number of people whose hair length is at least T becomes P or more for the first time.
If there are already P or more people whose hair length is at least T now, print 0.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq L_i \leq 100
  • 1 \leq T \leq 100
  • 1 \leq P \leq N
  • All input values are integers.

Input

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

N T P
L_1 L_2 \ldots L_N

Output

Print the number of days after which the number of people whose hair length is at least T becomes P or more for the first time. If this condition is already satisfied now, print 0.


Sample Input 1

5 10 3
3 11 1 6 2

Sample Output 1

7

There are five people, and their current hair lengths are 3, 11, 1, 6, 2, so there is one person whose hair length is at least 10.

After seven days, the hair lengths of the people will be 10, 18, 8, 13, 9, respectively, and there will be three people whose hair length is at least 10.
After six days, there are only two people whose hair length is at least 10, not satisfying the condition, so print 7.


Sample Input 2

2 5 2
10 10

Sample Output 2

0

Since there are already two people whose hair length is at least 5 now, satisfying the condition, so print 0.


Sample Input 3

3 10 1
1 2 3

Sample Output 3

7
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