C - Failing Grade

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

N 人の学生が試験を受けました。学生には学生 1, 学生 2, \dots, 学生 N と番号がついていて、学生 i は a_i 点を取りました。

P 点未満の点数を取った学生は "不可" となり単位を取得できません。 "不可" となった学生の人数を答えてください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq P \leq 100
  • 0 \leq a_i \leq 100 (1 \leq i \leq N)
  • 入力はすべて整数である。

入力

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

N P
a_1 a_2 \dots a_N

出力

"不可" となった学生の人数を出力せよ。


入力例 1

4 50
80 60 40 0

出力例 1

2

学生 1 は 80 点、学生 2 は 60 点と、 50 点以上の点数を取っているので "不可" とならず単位を取得できています。
一方、学生 3 は 40 点、学生 4 は 0 点で、 50 点を下回る点数を取っているので "不可" となります。よって答えは 2 人です。


入力例 2

3 90
89 89 89

出力例 2

3

入力例 3

2 22
6 37

出力例 3

1

Score : 200 points

Problem Statement

N students took an exam. The students are labeled as Student 1, Student 2, \dots, Student N, and Student i scored a_i points.

A student who scored less than P points are considered to have failed the exam and cannot earn the credit. Find the number of students who failed the exam.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq P \leq 100
  • 0 \leq a_i \leq 100 (1 \leq i \leq N)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N P
a_1 a_2 \dots a_N

Output

Print the number of students who failed the exam.


Sample Input 1

4 50
80 60 40 0

Sample Output 1

2

Students 1 and 2, who scored 80 and 60 points, respectively, succeeded in scoring at least 50 points to earn the credit.
On the other hand, Students 3 and 4, who scored 40 and 0 points, respectively, fell below 50 points and failed the exam. Thus, the answer is 2.


Sample Input 2

3 90
89 89 89

Sample Output 2

3

Sample Input 3

2 22
6 37

Sample Output 3

1
D - Same Name

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

N 人の人がいます。i \, (1 \leq i \leq N) 人目の人の姓は S_i、名は T_i です。

同姓同名であるような人の組が存在するか、すなわち 1 \leq i \lt j \leq N かつ S_i=S_j かつ T_i=T_j を満たすような整数対 (i,j) が存在するか判定してください。

制約

  • 2 \leq N \leq 1000
  • N は整数
  • S_i,T_i は英小文字のみからなる長さ 1 以上 10 以下の文字列

入力

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

N
S_1 T_1
S_2 T_2
\hspace{0.6cm}\vdots
S_N T_N

出力

同姓同名であるような人の組が存在するなら Yes を、存在しないなら No を出力せよ。


入力例 1

3
tanaka taro
sato hanako
tanaka taro

出力例 1

Yes

1 人目の人と 3 人目の人が同姓同名です。


入力例 2

3
saito ichiro
saito jiro
saito saburo

出力例 2

No

同姓同名であるような人の組は存在しません。


入力例 3

4
sypdgidop bkseq
bajsqz hh
ozjekw mcybmtt
qfeysvw dbo

出力例 3

No

Score : 200 points

Problem Statement

There are N people. The family name and given name of the i-th person (1 \leq i \leq N) are S_i and T_i, respectively.

Determine whether there is a pair of people with the same family and given names. In other words, determine whether there is a pair of integers (i,j) such that 1 \leq i \lt j \leq N, S_i=S_j, and T_i=T_j.

Constraints

  • 2 \leq N \leq 1000
  • N is an integer.
  • Each of S_i and T_i is a string of length between 1 and 10 (inclusive) consisting of English lowercase letters.

Input

Input is given from Standard Input in the following format:

N
S_1 T_1
S_2 T_2
\hspace{0.6cm}\vdots
S_N T_N

Output

If there is a pair of people with the same family and given names, print Yes; otherwise, print No.


Sample Input 1

3
tanaka taro
sato hanako
tanaka taro

Sample Output 1

Yes

The first and third persons have the same family and given names.


Sample Input 2

3
saito ichiro
saito jiro
saito saburo

Sample Output 2

No

No two persons have the same family and given names.


Sample Input 3

4
sypdgidop bkseq
bajsqz hh
ozjekw mcybmtt
qfeysvw dbo

Sample Output 3

No
E - String Delimiter

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

英小文字、,、" からなる長さ N の文字列 S が与えられます。S に含まれる " の個数は偶数であることが保証されています。

S に含まれる " の個数を 2K 個とすると、各 i=1,2,\ldots,K について 2i-1 番目の " から 2i 番目の " までの文字のことを 括られた文字 と呼びます。

あなたの仕事は、 S に含まれる , のうち、括られた文字 でないもの を . で置き換えて得られる文字列を答えることです。

制約

  • N は 1 以上 2\times 10^5 以下の整数
  • S は英小文字、,、" からなる長さ N の文字列
  • S に含まれる " の個数は偶数

入力

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

N
S

出力

答えを出力せよ。


入力例 1

8
"a,b"c,d

出力例 1

"a,b"c.d

S のうち "a,b" が括られた文字であり、c,d は括られた文字ではありません。

S に含まれる , のうち、括られた文字でないのは S の左から 7 番目の文字なので、7 番目の文字を . で置き換えたものが答えとなります。


入力例 2

5
,,,,,

出力例 2

.....

入力例 3

20
a,"t,"c,"o,"d,"e,"r,

出力例 3

a."t,"c."o,"d."e,"r.

Score : 300 points

Problem Statement

You are given a string S of length N consisting of lowercase English letters, ,, and ". It is guaranteed that S contains an even number of ".

Let 2K be the number of " in S. For each i=1,2,\ldots,K, the characters from the (2i-1)-th " through the (2i)-th " are said to be enclosed.

Your task is to replace each , in S that is not an enclosed character with . and print the resulting string.

Constraints

  • N is an integer between 1 and 2\times 10^5, inclusive.
  • S is a string of length N consisting of lowercase English letters, ,, and ".
  • S contains an even number of ".

Input

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

N
S

Output

Print the answer.


Sample Input 1

8
"a,b"c,d

Sample Output 1

"a,b"c.d

In S, "a,b" are enclosed characters, and c,d are not.

The , in S that is not an enclosed character is the seventh character from the left in S, so replace that character with . to get the answer.


Sample Input 2

5
,,,,,

Sample Output 2

.....

Sample Input 3

20
a,"t,"c,"o,"d,"e,"r,

Sample Output 3

a."t,"c."o,"d."e,"r.
F - The Kth Time Query

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

長さ N の数列 A = (a_1, a_2, \dots, a_N) があります。
以下で説明される Q 個のクエリに答えてください。

  • クエリ i : 整数の組 (x_i, k_i) が与えられます。A の要素を a_1, a_2, \dots と前から順に見ていったときに、数 x_i が k_i 回目に登場するのは A の前から何番目の要素を見たときかを出力してください。
    ただし条件を満たす要素が存在しない場合は -1 を出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 0 \leq a_i \leq 10^9 (1 \leq i \leq N)
  • 0 \leq x_i \leq 10^9 (1 \leq i \leq Q)
  • 1 \leq k_i \leq N (1 \leq i \leq Q)
  • 入力はすべて整数である。

入力

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

N Q
a_1 a_2 \dots a_N
x_1 k_1
x_2 k_2
\vdots
x_Q k_Q

出力

Q 行出力せよ。i 行目ではクエリ i に対する答えを出力せよ。


入力例 1

6 8
1 1 2 3 1 2
1 1
1 2
1 3
1 4
2 1
2 2
2 3
4 1

出力例 1

1
2
5
-1
3
6
-1
-1

A の中で 1 は a_1, a_2, a_5 に登場します。よって、クエリ 1 からクエリ 4 の答えは順に 1, 2, 5, -1 となります。


入力例 2

3 2
0 1000000000 999999999
1000000000 1
123456789 1

出力例 2

2
-1

Score : 300 points

Problem Statement

We have a sequence of N numbers: A = (a_1, a_2, \dots, a_N).
Process the Q queries explained below.

  • Query i: You are given a pair of integers (x_i, k_i). Let us look at the elements of A one by one from the beginning: a_1, a_2, \dots Which element will be the k_i-th occurrence of the number x_i?
    Print the index of that element, or -1 if there is no such element.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 0 \leq a_i \leq 10^9 (1 \leq i \leq N)
  • 0 \leq x_i \leq 10^9 (1 \leq i \leq Q)
  • 1 \leq k_i \leq N (1 \leq i \leq Q)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
a_1 a_2 \dots a_N
x_1 k_1
x_2 k_2
\vdots
x_Q k_Q

Output

Print Q lines. The i-th line should contain the answer to Query i.


Sample Input 1

6 8
1 1 2 3 1 2
1 1
1 2
1 3
1 4
2 1
2 2
2 3
4 1

Sample Output 1

1
2
5
-1
3
6
-1
-1

1 occurs in A at a_1, a_2, a_5. Thus, the answers to Query 1 through 4 are 1, 2, 5, -1 in this order.


Sample Input 2

3 2
0 1000000000 999999999
1000000000 1
123456789 1

Sample Output 2

2
-1
G - 8 Puzzle on Graph

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は道端であるパズルを拾いました。
このパズルは、9 個の頂点と M 本の辺からなる無向グラフ、および、8 つのコマで構成されます。

グラフの 9 つの頂点はそれぞれ頂点 1、頂点 2、\ldots、頂点 9 と呼ばれ、 i = 1, 2, \ldots, M について、i 番目の辺は頂点 u_i と頂点 v_i を結んでいます。
8 つのコマはそれぞれコマ 1、コマ 2、\ldots、コマ 8 と呼ばれ、 j = 1, 2, \ldots, 8 について、コマ j は頂点 p_j に置かれています。 ここで、すべてのコマはそれぞれ異なる頂点に置かれていることが保証されます。 コマが置かれていない「空の頂点」がただ一つ存在することに注意してください。

高橋君はこのパズルに対して下記の操作を好きな回数( 0 回でもよい)だけ行うことができます。

空の頂点に隣接する頂点に置かれたコマを 1 つ選び、選んだコマを空の頂点に移動する。

高橋君は上記の操作を繰り返して、このパズルを「完成」させようとしています。 パズルは、下記の状態を満たしたときに完成となります。

j = 1, 2, \ldots, 8 について、コマ j は 頂点 j に置かれている。

高橋君がパズルを完成させることが可能かどうかを判定し、可能な場合はそのために必要な操作回数の最小値を出力してください。

制約

  • 0 \leq M \leq 36
  • 1 \leq u_i, v_i \leq 9
  • 与えられるグラフは多重辺、自己ループを持たない
  • 1 \leq p_j \leq 9
  • j \neq j' \Rightarrow p_j \neq p_{j'}
  • 入力はすべて整数

入力

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

M
u_1 v_1
u_2 v_2
\vdots
u_M v_M
p_1 p_2 \ldots p_8

出力

高橋君がパズルを完成させることが可能な場合は、そのために必要な操作回数の最小値を出力せよ。 高橋君がパズルを完成させることが不可能な場合は、-1 を出力せよ。


入力例 1

5
1 2
1 3
1 9
2 9
3 9
3 9 2 4 5 6 7 8

出力例 1

5

下記の手順によって、5 回の操作でパズルを完成させることができます。

  1. コマ 2 を頂点 9 から頂点 1 に移動する。
  2. コマ 3 を頂点 2 から頂点 9 に移動する。
  3. コマ 2 を頂点 1 から頂点 2 に移動する。
  4. コマ 1 を頂点 3 から頂点 1 に移動する。
  5. コマ 3 を頂点 9 から頂点 3 に移動する。

一方、5 回未満の操作でパズルを完成させることはできません。よって、5 を出力します。
与えられるグラフは連結とは限らないことに注意してください。


入力例 2

5
1 2
1 3
1 9
2 9
3 9
1 2 3 4 5 6 7 8

出力例 2

0

パズルは初めから完成しています。よって、完成させるために必要な操作回数の最小値は 0 回です。


入力例 3

12
8 5
9 6
4 5
4 1
2 5
8 9
2 1
3 6
8 7
6 5
7 4
2 3
1 2 3 4 5 6 8 7

出力例 3

-1

操作の繰り返しによってパズルを完成させることができないので、-1 を出力します。


入力例 4

12
6 5
5 4
4 1
4 7
8 5
2 1
2 5
6 9
3 6
9 8
8 7
3 2
2 3 4 6 1 9 7 8

出力例 4

16

Score : 400 points

Problem Statement

Takahashi found a puzzle along some road.
It is composed of an undirected graph with nine vertices and M edges, and eight pieces.

The nine vertices of the graph are called Vertex 1, Vertex 2, \ldots, Vertex 9. For each i = 1, 2, \ldots, M, the i-th edge connects Vertex u_i and Vertex v_i.
The eight pieces are called Piece 1, Piece 2, \ldots, Piece 8. For each j = 1, 2, \ldots, 8, Piece j is on Vertex p_j.
Here, it is guaranteed that all pieces are on distinct vertices. Note that there is exactly one empty vertex without a piece.

Takahashi can do the following operation on the puzzle any number of times (possibly zero).

Choose a piece on a vertex adjacent to the empty vertex, and move it to the empty vertex.

By repeating this operation, he aims to complete the puzzle. The puzzle is considered complete when the following holds.

  • For each j = 1, 2, \ldots, 8, Piece j is on Vertex j.

Determine whether it is possible for Takahashi to complete the puzzle. If it is possible, find the minimum number of operations needed to do so.

Constraints

  • 0 \leq M \leq 36
  • 1 \leq u_i, v_i \leq 9
  • The given graph has no multi-edges or self-loops.
  • 1 \leq p_j \leq 9
  • j \neq j' \Rightarrow p_j \neq p_{j'}
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

M
u_1 v_1
u_2 v_2
\vdots
u_M v_M
p_1 p_2 \ldots p_8

Output

If it is possible for Takahashi to complete the puzzle, find the minimum number of operations needed to do so. Otherwise, print -1.


Sample Input 1

5
1 2
1 3
1 9
2 9
3 9
3 9 2 4 5 6 7 8

Sample Output 1

5

The following procedure completes the puzzle in five operations.

  1. Move Piece 2 from Vertex 9 to Vertex 1.
  2. Move Piece 3 from Vertex 2 to Vertex 9.
  3. Move Piece 2 from Vertex 1 to Vertex 2.
  4. Move Piece 1 from Vertex 3 to Vertex 1.
  5. Move Piece 3 from Vertex 9 to Vertex 3.

On the other hand, it is impossible to complete the puzzle in less than five operations. Thus, we should print 5.
Note that the given graph may not be connected.


Sample Input 2

5
1 2
1 3
1 9
2 9
3 9
1 2 3 4 5 6 7 8

Sample Output 2

0

The puzzle is already complete from the beginning. Thus, the minimum number of operations needed to complete the puzzle is 0.


Sample Input 3

12
8 5
9 6
4 5
4 1
2 5
8 9
2 1
3 6
8 7
6 5
7 4
2 3
1 2 3 4 5 6 8 7

Sample Output 3

-1

No sequence of operations can complete the puzzle, so we should print -1.


Sample Input 4

12
6 5
5 4
4 1
4 7
8 5
2 1
2 5
6 9
3 6
9 8
8 7
3 2
2 3 4 6 1 9 7 8

Sample Output 4

16