A - Similar String

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

二つの文字 x と y は以下の 3 つの条件のうちどれか 1 つを満たすとき、似た文字と呼ばれます。

  • x と y は同じ文字
  • x と y の片方が 1 で、もう片方が l
  • x と y の片方が 0 で、もう片方が o

また、長さ N の文字列 S と T は以下の条件を満たすとき、似た文字列と呼ばれます。

  • 任意の i\ (1\leq i\leq N) について、 S の i 番目の文字と T の i 番目の文字は似た文字

英小文字及び数字からなる長さ N の文字列 S,T が与えられます。 S と T が似た文字列か判定してください。

制約

  • N は 1 以上 100 以下の整数
  • S,T は英小文字及び数字からなる長さ N の文字列

入力

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

N
S
T

出力

S と T が似た文字列の場合 Yes を、そうでない場合 No を出力せよ。

入力例 1

3
l0w
1ow

出力例 1

Yes

S の 1 文字目は lで、T の 1 文字目は 1です。これらは似た文字です。

S の 2 文字目は 0で、T の 2 文字目は oです。これらは似た文字です。

S の 3 文字目は wで、T の 3 文字目は wです。これらは似た文字です。

よって S と T は似た文字列です。

入力例 2

3
abc
arc

出力例 2

No

S の 2 文字目は bで、T の 2 文字目は rです。これらは似た文字ではありません。

よって S と T は似た文字列ではありません。

入力例 3

4
nok0
n0ko

出力例 3

Yes

Score : 100 points

Problem Statement

Two characters x and y are called similar characters if and only if one of the following conditions is satisfied:

  • x and y are the same character.
  • One of x and y is 1 and the other is l.
  • One of x and y is 0 and the other is o.

Two strings S and T, each of length N, are called similar strings if and only if:

  • for all i\ (1\leq i\leq N), the i-th character of S and the i-th character of T are similar characters.

Given two length-N strings S and T consisting of lowercase English letters and digits, determine if S and T are similar strings.

Constraints

  • N is an integer between 1 and 100.
  • Each of S and T is a string of length N consisting of lowercase English letters and digits.

Input

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

N
S
T

Output

Print Yes if S and T are similar strings, and No otherwise.

Sample Input 1

3
l0w
1ow

Sample Output 1

Yes

The 1-st character of S is l, and the 1-st character of T is 1. These are similar characters.

The 2-nd character of S is 0, and the 2-nd character of T is o. These are similar characters.

The 3-rd character of S is w, and the 3-rd character of T is w. These are similar characters.

Thus, S and T are similar strings.

Sample Input 2

3
abc
arc

Sample Output 2

No

The 2-nd character of S is b, and the 2-nd character of T is r. These are not similar characters.

Thus, S and T are not similar strings.

Sample Input 3

4
nok0
n0ko

Sample Output 3

Yes
B - Median?

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

整数 a, b, c が与えられます。b がこれらの整数の中央値であるかどうか判定してください。

制約

  • 1 \leq a, b, c \leq 100
  • 入力は全て整数

入力

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

a b c

出力

b が与えられた整数の中央値であるならば Yes、そうでないならば No と出力せよ。

入力例 1

5 3 2

出力例 1

Yes

与えられた整数を小さい順に並べると 2, 3, 5 となり、b はこれらの整数の中央値です。

入力例 2

2 5 3

出力例 2

No

b は与えられた整数の中央値ではありません。

入力例 3

100 100 100

出力例 3

Yes

Score : 100 points

Problem Statement

Given integers a, b, and c, determine if b is the median of these integers.

Constraints

  • 1 \leq a, b, c \leq 100
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

a b c

Output

If b is the median of the given integers, then print Yes; otherwise, print No.

Sample Input 1

5 3 2

Sample Output 1

Yes

The given integers are 2, 3, 5 when sorted in ascending order, of which b is the median.

Sample Input 2

2 5 3

Sample Output 2

No

b is not the median of the given integers.

Sample Input 3

100 100 100

Sample Output 3

Yes
C - Piano

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

無限に長いピアノの鍵盤があります。 この鍵盤内の連続する区間であって、白鍵 W 個と黒鍵 B 個からなるものは存在しますか？

文字列 wbwbwwbwbwbw を無限に繰り返してできる文字列を S とおきます。

S の部分文字列であって、W 個の w と B 個の b からなるものは存在しますか？

S の部分文字列とは S の部分文字列とは、ある 2 つの正整数 l,r\ (l\leq r) に対して、S の l 文字目、l+1 文字目、\dots、r 文字目をこの順に繋げてできる文字列のことをいいます。

制約

  • W,B は整数
  • 0\leq W,B \leq 100
  • W+B \geq 1

入力

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

W B

出力

S の部分文字列であって、W 個の w と B 個の b からなるものが存在するならば Yes を、存在しないならば No を出力せよ。

入力例 1

3 2

出力例 1

Yes

S の最初の 15 文字は wbwbwwbwbwbwwbw であり、S の 11 文字目から 15 文字目までを取り出してできる文字列 bwwbw は 3 個の w と 2 個の b からなる部分文字列の一例です。

入力例 2

3 0

出力例 2

No

3 個の w と 0 個の b からなる文字列は www のみですが、これは S の部分文字列ではありません。

入力例 3

92 66

出力例 3

Yes

Score: 200 points

Problem Statement

There is an infinitely long piano keyboard. Is there a continuous segment within this keyboard that consists of W white keys and B black keys?

Let S be the string formed by infinitely repeating the string wbwbwwbwbwbw.

Is there a substring of S that consists of W occurrences of w and B occurrences of b?

What is a substring of S? A substring of S is a string that can be formed by concatenating the l-th, (l+1)-th, \dots, r-th characters of S in this order for some two positive integers l and r (l\leq r).

Constraints

  • W and B are integers.
  • 0\leq W,B \leq 100
  • W+B \geq 1

Input

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

W B

Output

If there is a substring of S that consists of W occurrences of w and B occurrences of b, print Yes; otherwise, print No.

Sample Input 1

3 2

Sample Output 1

Yes

The first 15 characters of S are wbwbwwbwbwbwwbw. You can take the 11-th through 15-th characters to form the string bwwbw, which is a substring consisting of three occurrences of w and two occurrences of b.

Sample Input 2

3 0

Sample Output 2

No

The only string consisting of three occurrences of w and zero occurrences of b is www, which is not a substring of S.

Sample Input 3

92 66

Sample Output 3

Yes
D - Trick Taking

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

プレイヤー 1 、プレイヤー 2 、\ldots 、プレイヤー N と番号がつけられた N 人のプレイヤーがカードゲームで対戦します。
各プレイヤーはカードを 1 枚場に出します。

各カードは色と値の 2 つの属性を持ち、どちらの属性も正整数で表されます。
i = 1, 2, \ldots, N について、プレイヤー i が場に出したカードの色は C_i であり、値は R_i です。 R_1, R_2, \ldots, R_N はすべて異なります。

N 人のプレイヤーの中から 1 人の勝者を下記の方法で決めます。

  • 色が T であるカードが 1 枚以上場に出された場合、色が T であるカードのうち値が最大のものを出したプレイヤーが勝者である。
  • 色が T であるカードが場に 1 枚も出されなかった場合、プレイヤー 1 が出したカードと同じ色のカードのうち値が最大のものを出したプレイヤーが勝者である。（プレイヤー 1 自身も勝者となり得ることに注意してください。）

勝者となるプレイヤーの番号を出力してください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq T \leq 10^9
  • 1 \leq C_i \leq 10^9
  • 1 \leq R_i \leq 10^9
  • i \neq j \implies R_i \neq R_j
  • 入力はすべて整数

入力

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

N T
C_1 C_2 \ldots C_N
R_1 R_2 \ldots R_N

出力

答えを出力せよ。

入力例 1

4 2
1 2 1 2
6 3 4 5

出力例 1

4

色が 2 であるカードが 1 枚以上場に出されています。 よって、色が 2 であるカードのうち値が最大の 5 のカードを出した、プレイヤー 4 が勝者です。

入力例 2

4 2
1 3 1 4
6 3 4 5

出力例 2

1

色が 2 であるカードが 1 枚も場に出されていません。 よって、プレイヤー 1 が出したカードの色と同じ色（すなわち色 1 ）のカードのうち値が最大の 6 のカードを出した、プレイヤー 1 が勝者です。

入力例 3

2 1000000000
1000000000 1
1 1000000000

出力例 3

1

Score : 200 points

Problem Statement

N players with ID numbers 1, 2, \ldots, N are playing a card game.
Each player plays one card.

Each card has two parameters: color and rank, both of which are represented by positive integers.
For i = 1, 2, \ldots, N, the card played by player i has a color C_i and a rank R_i. All of R_1, R_2, \ldots, R_N are different.

Among the N players, one winner is decided as follows.

  • If one or more cards with the color T are played, the player who has played the card with the greatest rank among those cards is the winner.
  • If no card with the color T is played, the player who has played the card with the greatest rank among the cards with the color of the card played by player 1 is the winner. (Note that player 1 may win.)

Print the ID number of the winner.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq T \leq 10^9
  • 1 \leq C_i \leq 10^9
  • 1 \leq R_i \leq 10^9
  • i \neq j \implies R_i \neq R_j
  • All values in the input are integers.

Input

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

N T
C_1 C_2 \ldots C_N
R_1 R_2 \ldots R_N

Output

Print the answer.

Sample Input 1

4 2
1 2 1 2
6 3 4 5

Sample Output 1

4

Cards with the color 2 are played. Thus, the winner is player 4, who has played the card with the greatest rank, 5, among those cards.

Sample Input 2

4 2
1 3 1 4
6 3 4 5

Sample Output 2

1

No card with the color 2 is played. Thus, the winner is player 1, who has played the card with the greatest rank, 6, among the cards with the color of the card played by player 1 (color 1).

Sample Input 3

2 1000000000
1000000000 1
1 1000000000

Sample Output 3

1
E - Approximate Equalization 2

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

整数列 A=(A_1,A_2,\dots,A_N) があります。 あなたは次の操作を好きな回数（0 回でもよい）行うことができます。

  • 1\leq i,j \leq N を満たす整数 i,j を選ぶ。A_i を 1 減らし、A_j を 1 増やす。

A の最小値と最大値の差を 1 以下にするために必要な最小の操作回数を求めてください。

制約

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

入力

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

N
A_1 A_2 \dots A_N

出力

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

入力例 1

4
4 7 3 7

出力例 1

3

以下のように 3 回の操作を行うことで、A の最小値と最大値の差を 1 以下にすることができます。

  • i=2,j=3 として操作を行う。A=(4,6,4,7) になる。
  • i=4,j=1 として操作を行う。A=(5,6,4,6) になる。
  • i=4,j=3 として操作を行う。A=(5,6,5,5) になる。

3 回未満の操作で A の最小値と最大値の差を 1 以下にすることはできません。よって答えは 3 です。

入力例 2

1
313

出力例 2

0

入力例 3

10
999999997 999999999 4 3 2 4 999999990 8 999999991 999999993

出力例 3

2499999974

Score : 400 points

Problem Statement

You are given an integer sequence A=(A_1,A_2,\dots,A_N). You can perform the following operation any number of times (possibly zero).

  • Choose integers i and j with 1\leq i,j \leq N. Decrease A_i by one and increase A_j by one.

Find the minimum number of operations required to make the difference between the minimum and maximum values of A at most one.

Constraints

  • 1\leq N \leq 2\times 10^5
  • 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
A_1 A_2 \dots A_N

Output

Print the answer as an integer.

Sample Input 1

4
4 7 3 7

Sample Output 1

3

By the following three operations, the difference between the minimum and maximum values of A becomes at most one.

  • Choose i=2 and j=3 to make A=(4,6,4,7).
  • Choose i=4 and j=1 to make A=(5,6,4,6).
  • Choose i=4 and j=3 to make A=(5,6,5,5).

You cannot make the difference between maximum and minimum values of A at most one by less than three operations, so the answer is 3.

Sample Input 2

1
313

Sample Output 2

0

Sample Input 3

10
999999997 999999999 4 3 2 4 999999990 8 999999991 999999993

Sample Output 3

2499999974