A - Conflict

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

N 個の商品があります。高橋君と青木君がどの商品を欲しがっているかを表す長さ N の文字列 T,A が与えられます。T,A の i\ (1\leq i\leq N) 文字目をそれぞれ T_i,A_i とします。

高橋君は T_i が o のとき i 番目の商品を欲しがっており、T_i が x のとき i 番目の商品を欲しがっていません。 同様に、青木君は A_i が o のとき i 番目の商品を欲しがっており、A_i が x のとき i 番目の商品を欲しがっていません。

2 人ともが欲しがっている商品が存在するか判定してください。

制約

  • 1\leq N\leq 100
  • N は整数
  • T,A は o および x からなる長さ N の文字列

入力

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

N
T
A

出力

2 人とも欲しがっている商品が存在するならば Yes を、存在しないならば No を出力せよ。


入力例 1

4
oxoo
xoox

出力例 1

Yes

3 つ目の商品は 2 人ともが欲しがっているため、Yes を出力します。


入力例 2

5
xxxxx
ooooo

出力例 2

No

2 人とも欲しがっている商品は存在しないため、No を出力します。


入力例 3

10
xoooxoxxxo
ooxooooxoo

出力例 3

Yes

Score : 100 points

Problem Statement

There are N items. You are given strings T and A of length N that represent which items Takahashi and Aoki want, respectively. Let T_i and A_i be the i-th (1\leq i\leq N) characters of T and A, respectively.

Takahashi wants the i-th item when T_i is o, and does not want the i-th item when T_i is x. Similarly, Aoki wants the i-th item when A_i is o, and does not want the i-th item when A_i is x.

Determine whether there exists an item that both of them want.

Constraints

  • 1\leq N\leq 100
  • N is an integer.
  • T and A are strings of length N consisting of o and x.

Input

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

N
T
A

Output

If there exists an item that both of them want, output Yes; otherwise, output No.


Sample Input 1

4
oxoo
xoox

Sample Output 1

Yes

The third item is wanted by both of them, so output Yes.


Sample Input 2

5
xxxxx
ooooo

Sample Output 2

No

There is no item that both of them want, so output No.


Sample Input 3

10
xoooxoxxxo
ooxooooxoo

Sample Output 3

Yes
B - Median?

Time Limit: 2 sec / Memory Limit: 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 - The Honest Woodcutters

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

N 人の木こり 1,2,\dots,N が斧を 1 個ずつ持っています。 全員が斧を池に落としてしまいました。
池に N 個の斧 1,2,\dots,N が沈んでいました。
各木こり i は「自分が持っていた斧は斧 A_i である」と主張しています。
一方、この池の女神は、各斧 i を持っていたのは木こり B_i であることを知っています。

N 人の木こり全員が本当のことを言っているかどうかを判定してください。

制約

  • 1 \leq N \leq 100
  • 1 \leq A_i \leq N
  • 1 \leq B_i \leq N
  • A_i \neq A_j\;(i \neq j)
  • B_i \neq B_j\;(i \neq j)
  • 入力される値はすべて整数

入力

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

N  
A_1 A_2 \dots A_N  
B_1 B_2 \dots B_N  

出力

N 人の木こり全員が本当のことを言っているならば Yes を、そうでないならば No を出力せよ。


入力例 1

3
3 1 2
2 3 1

出力例 1

Yes

N 人の木こり全員が本当のことを言っています。


入力例 2

4
1 2 3 4
1 3 2 4

出力例 2

No

木こり 2,3 の 2 人は嘘をついています。


入力例 3

5
2 4 5 1 3
4 1 5 2 3

出力例 3

Yes

Score : 200 points

Problem Statement

N woodcutters 1, 2, \dots, N each have one axe. All of them dropped their axes into a pond.
N axes 1, 2, \dots, N were found sunk in the pond.
Each woodcutter i claims that "I owned axe A_i."
On the other hand, the goddess of this pond knows that the woodcutter who owned axe i is woodcutter B_i.

Determine whether all N woodcutters are telling the truth.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq A_i \leq N
  • 1 \leq B_i \leq N
  • A_i \neq A_j\;(i \neq j)
  • B_i \neq B_j\;(i \neq j)
  • 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  
B_1 B_2 \dots B_N  

Output

Output Yes if all N woodcutters are telling the truth, and No otherwise.


Sample Input 1

3
3 1 2
2 3 1

Sample Output 1

Yes

All N woodcutters are telling the truth.


Sample Input 2

4
1 2 3 4
1 3 2 4

Sample Output 2

No

Woodcutters 2 and 3 are lying.


Sample Input 3

5
2 4 5 1 3
4 1 5 2 3

Sample Output 3

Yes
D - Precondition

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

英小文字および英大文字のみからなる文字列 S, T が与えられます。

文字列 S が以下の条件を満たしているか判定してください。

  • S の先頭でない英大文字の直前の文字はすべて T に含まれる。より形式的には、2 \leq i \leq |S| なる整数 i について S の i 番目の文字が英大文字ならば、S の i-1 番目の文字は T に含まれる。

制約

  • S, T は長さ 1 以上 100 以下の英小文字および英大文字のみからなる文字列

入力

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

S
T

出力

S が問題文中の条件を満たしているとき Yes と出力せよ。そうでないとき、No と出力せよ。


入力例 1

AtCoder
Total

出力例 1

Yes

S の先頭でない英大文字は 3 番目の文字の C のみです。この直前の文字である t は T に含まれているため、Yes と出力すればよいです。


入力例 2

aBCdE
abcdcba

出力例 2

No

S の 3 番目の文字は英大文字 C であり、その直前の文字は B ですが、B は T に含まれていません。


入力例 3

abcde
XYZ

出力例 3

Yes

Score : 200 points

Problem Statement

You are given strings S and T consisting of lowercase and uppercase English letters.

Determine whether the string S satisfies the following condition:

  • Every uppercase letter in S that is not at the beginning is immediately preceded by a character contained in T. More formally, for all integers i such that 2 \leq i \leq |S|, if the i-th character of S is uppercase, then the (i-1)-th character of S is contained in T.

Constraints

  • Each of S and T is a string consisting of lowercase and uppercase English letters with length between 1 and 100, inclusive.

Input

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

S
T

Output

If S satisfies the condition in the problem statement, output Yes. Otherwise, output No.


Sample Input 1

AtCoder
Total

Sample Output 1

Yes

The only uppercase letter in S that is not at the beginning is the 3rd character C. The immediately preceding character t is contained in T, so output Yes.


Sample Input 2

aBCdE
abcdcba

Sample Output 2

No

The 3rd character of S is the uppercase letter C, and its immediately preceding character is B, but B is not contained in T.


Sample Input 3

abcde
XYZ

Sample Output 3

Yes
E - Sake or Water

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 個のカップがあり、それぞれのカップには無色透明な液体が入っています。
具体的には、i 番目 (1\leq i\leq N) のカップには A_i ml の液体が入っています。
また、これらのうちちょうど K 個のカップには日本酒が入っており、それ以外には水が入っていることが分かっています。
ただし、どのカップに日本酒が入っているかについては分かっていません。

高橋君は(1 つ以上の)いくつかのカップを選んでそれらに入った液体をすべて飲むことができます。
どのカップに日本酒が入っているかによらず、高橋君が確実に X ml 以上の日本酒を飲むためには、最低何個のカップを選ぶ必要があるか求めてください。
そのような選び方が不可能である場合には -1 を出力してください。

制約

  • 1 \leq K \leq N \leq 3\times 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq X \leq 3\times 10^{14}
  • 入力はすべて整数

入力

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

N K X
A_1 A_2 \ldots A_N

出力

条件をみたすために高橋君が選ぶ必要があるカップの個数の最小値を出力せよ。 そのような選び方が不可能である場合には -1 を出力せよ。


入力例 1

3 2 5
10 6 8

出力例 1

2

高橋君が 1 番目と 3 番目のカップを選んで飲んだ場合を考えます。

3 個のカップのうち 2 個に日本酒が入っているため、次の 3 通りが考えられます。

  • 1,2 番目のカップに日本酒が入っていた場合

高橋君は 10 ml の日本酒と 8 ml の水を飲むことになります。

  • 1,3 番目のカップに日本酒が入っていた場合

高橋君は 18 ml の日本酒を飲むことになります。

  • 2,3 番目のカップに日本酒が入っていた場合

高橋君は 8 ml の日本酒と 10 ml の水を飲むことになります。

よって、いずれの場合でも 5 ml 以上の日本酒を飲むことができます。
一方で、どのカップに日本酒が入っているか分かっていない状態で、1 つのみのカップを選んで条件をみたすようにすることは不可能です。

よって、2 を出力します。


入力例 2

2 1 8
6 10

出力例 2

-1

1 番目のカップに日本酒が入っていた場合、どのようにカップを選んでも 8 ml 以上の日本酒を飲むことは不可能です。
よって、-1 を出力します。


入力例 3

5 3 3000000000
1000000000 1000000000 1000000000 1000000000 1000000000

出力例 3

5

Score : 300 points

Problem Statement

There are N cups, each containing a colorless and transparent liquid.
Specifically, the i-th (1\leq i\leq N) cup contains A_i ml of liquid.
It is known that exactly K of these cups contain sake (rice wine), and the rest contain water.
However, it is not known which cups contain sake.

Takahashi can choose some (one or more) cups and drink all the liquid in them.
Find the minimum number of cups he needs to choose to ensure he drinks at least X ml of sake, regardless of which cups contain sake.
If such a choice is impossible, print -1.

Constraints

  • 1 \leq K \leq N \leq 3\times 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq X \leq 3\times 10^{14}
  • All input values are integers.

Input

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

N K X
A_1 A_2 \ldots A_N

Output

Print the minimum number of cups Takahashi needs to choose to satisfy the condition. If such a choice is impossible, print -1.


Sample Input 1

3 2 5
10 6 8

Sample Output 1

2

Consider the case where Takahashi chooses the first and third cups and drinks them.

Two out of the three cups contain sake, so the following three cases are possible:

  • If the first and second cups contain sake

He drinks 10 ml of sake and 8 ml of water.

  • If the first and third cups contain sake

He drinks 18 ml of sake.

  • If the second and third cups contain sake

He drinks 8 ml of sake and 10 ml of water.

Thus, in all cases, he can drink at least 5 ml of sake.
On the other hand, it is impossible to satisfy the condition by choosing only one cup without knowing which cups contain sake.

Therefore, print 2.


Sample Input 2

2 1 8
6 10

Sample Output 2

-1

If the first cup contained sake, it is impossible to drink 8 ml or more of sake no matter which cups are chosen.
Therefore, print -1.


Sample Input 3

5 3 3000000000
1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

5