A - Odds of Oddness

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

このとき、a が奇数である確率を答えてください。

• 1 ≤ N ≤ 100

### 入力

N


### 出力

a が奇数である確率を出力せよ。 出力は、ジャッジの出力との絶対誤差または相対誤差が 10^{-6} 以下のとき正解と判定される。

### 入力例 1

4


### 出力例 1

0.5000000000


4 以下の正整数は 1 , 2 , 3 , 44 つであり、そのうち奇数は 1 , 32 つです。以上より、答えは \frac{2}{4} = 0.5 です。

### 入力例 2

5


### 出力例 2

0.6000000000


### 入力例 3

1


### 出力例 3

1.0000000000


Score : 100 points

### Problem Statement

Given is an integer N.

Takahashi chooses an integer a from the positive integers not greater than N with equal probability.

Find the probability that a is odd.

### Constraints

• 1 \leq N \leq 100

### Input

Input is given from Standard Input in the following format:

N


### Output

Print the probability that a is odd. Your output will be considered correct when its absolute or relative error from the judge's output is at most 10^{-6}.

### Sample Input 1

4


### Sample Output 1

0.5000000000


There are four positive integers not greater than 4: 1, 2, 3, and 4. Among them, we have two odd numbers: 1 and 3. Thus, the answer is \frac{2}{4} = 0.5.

### Sample Input 2

5


### Sample Output 2

0.6000000000


### Sample Input 3

1


### Sample Output 3

1.0000000000

B - Roller Coaster

Time Limit: 2 sec / Memory Limit: 1024 MB

### 制約

• 1 \le N \le 10^5
• 1 \le K \le 500
• 1 \le h_i \le 500
• 入力はすべて整数

### 入力

N K
h_1 h_2 \ldots h_N


### 入力例 1

4 150
150 140 100 200


### 出力例 1

2


### 入力例 2

1 500
499


### 出力例 2

0


### 入力例 3

5 1
100 200 300 400 500


### 出力例 3

5


Score : 200 points

### Problem Statement

N friends of Takahashi has come to a theme park.

To ride the most popular roller coaster in the park, you must be at least K centimeters tall.

The i-th friend is h_i centimeters tall.

How many of the Takahashi's friends can ride the roller coaster?

### Constraints

• 1 \le N \le 10^5
• 1 \le K \le 500
• 1 \le h_i \le 500
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

N K
h_1 h_2 \ldots h_N


### Output

Print the number of people among the Takahashi's friends who can ride the roller coaster.

### Sample Input 1

4 150
150 140 100 200


### Sample Output 1

2


Two of them can ride the roller coaster: the first and fourth friends.

### Sample Input 2

1 500
499


### Sample Output 2

0


### Sample Input 3

5 1
100 200 300 400 500


### Sample Output 3

5

C - Go to School

Time Limit: 2 sec / Memory Limit: 1024 MB

### 制約

• 1 \le N \le 10^5
• 1 \le A_i \le N
• A_i \neq A_j (i \neq j)
• 入力はすべて整数

### 入力

N
A_1 A_2 \ldots A_N


### 入力例 1

3
2 3 1


### 出力例 1

3 1 2


### 入力例 2

5
1 2 3 4 5


### 出力例 2

1 2 3 4 5


### 入力例 3

8
8 2 7 3 4 5 6 1


### 出力例 3

8 2 4 5 6 7 3 1


Score : 300 points

### Problem Statement

Takahashi is a teacher responsible for a class of N students.

The students are given distinct student numbers from 1 to N.

Today, all the students entered the classroom at different times.

According to Takahashi's record, there were A_i students in the classroom when student number i entered the classroom (including student number i).

From these records, reconstruct the order in which the students entered the classroom.

### Constraints

• 1 \le N \le 10^5
• 1 \le A_i \le N
• A_i \neq A_j (i \neq j)
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N


### Output

Print the student numbers of the students in the order the students entered the classroom.

### Sample Input 1

3
2 3 1


### Sample Output 1

3 1 2


First, student number 3 entered the classroom.

Then, student number 1 entered the classroom.

Finally, student number 2 entered the classroom.

### Sample Input 2

5
1 2 3 4 5


### Sample Output 2

1 2 3 4 5


### Sample Input 3

8
8 2 7 3 4 5 6 1


### Sample Output 3

8 2 4 5 6 7 3 1

D - Disjoint Set of Common Divisors

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

AB の正の公約数の中からいくつかを選びます。

ただし、選んだ整数の中のどの異なる 2 つの整数についても互いに素でなければなりません。

### 制約

• 入力は全て整数である。
• 1 \leq A, B \leq 10^{12}

### 入力

A B


### 入力例 1

12 18


### 出力例 1

3


1218 の正の公約数は 1, 2, 3, 6 です。

122331 は互いに素なので、1, 2, 3 を選ぶことができ、このときが最大です。

### 入力例 2

420 660


### 出力例 2

4


### 入力例 3

1 2019


### 出力例 3

1


12019 の正の公約数は 1 しかありません。

Score : 400 points

### Problem Statement

Given are positive integers A and B.

Let us choose some number of positive common divisors of A and B.

Here, any two of the chosen divisors must be coprime.

At most, how many divisors can we choose?

Definition of common divisor

An integer d is said to be a common divisor of integers x and y when d divides both x and y.

Definition of being coprime

Integers x and y are said to be coprime when x and y have no positive common divisors other than 1.

Definition of dividing

An integer x is said to divide another integer y when there exists an integer \alpha such that y = \alpha x.

### Constraints

• All values in input are integers.
• 1 \leq A, B \leq 10^{12}

### Input

Input is given from Standard Input in the following format:

A B


### Output

Print the maximum number of divisors that can be chosen to satisfy the condition.

### Sample Input 1

12 18


### Sample Output 1

3


12 and 18 have the following positive common divisors: 1, 2, 3, and 6.

1 and 2 are coprime, 2 and 3 are coprime, and 3 and 1 are coprime, so we can choose 1, 2, and 3, which achieve the maximum result.

### Sample Input 2

420 660


### Sample Output 2

4


### Sample Input 3

1 2019


### Sample Output 3

1


1 and 2019 have no positive common divisors other than 1.

E - Get Everything

Time Limit: 2 sec / Memory Limit: 1024 MB

### 制約

• 入力は全て整数
• 1 ≤ N ≤ 12
• 1 ≤ M ≤ 10^3
• 1 \leq a_i \leq 10^5
• 1 \leq b_i \leq N
• 1 \leq c_{i1} < c_{i2} < ... < c_{i{b_i}} \leq N

### 入力

N M
a_1 b_1
c_{11} c_{12} ... c_{1{b_1}}
:
a_M b_M
c_{M1} c_{M2} ... c_{M{b_M}}


### 入力例 1

2 3
10 1
1
15 1
2
30 2
1 2


### 出力例 1

25


1 と鍵 2 を購入すると、全ての宝箱を開けることが出来ます。このときの費用は 25 円であり、これが最小値です。

### 入力例 2

12 1
100000 1
2


### 出力例 2

-1


### 入力例 3

4 6
67786 3
1 3 4
3497 1
2
44908 3
2 3 4
2156 3
2 3 4
26230 1
2
86918 1
3


### 出力例 3

69942


Score : 500 points

### Problem Statement

We have N locked treasure boxes, numbered 1 to N.

A shop sells M keys. The i-th key is sold for a_i yen (the currency of Japan), and it can unlock b_i of the boxes: Box c_{i1}, c_{i2}, ..., c_{i{b_i}}. Each key purchased can be used any number of times.

Find the minimum cost required to unlock all the treasure boxes. If it is impossible to unlock all of them, print -1.

### Constraints

• All values in input are integers.
• 1 \leq N \leq 12
• 1 \leq M \leq 10^3
• 1 \leq a_i \leq 10^5
• 1 \leq b_i \leq N
• 1 \leq c_{i1} < c_{i2} < ... < c_{i{b_i}} \leq N

### Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
c_{11} c_{12} ... c_{1{b_1}}
:
a_M b_M
c_{M1} c_{M2} ... c_{M{b_M}}


### Output

Print the minimum cost required to unlock all the treasure boxes. If it is impossible to unlock all of them, print -1.

### Sample Input 1

2 3
10 1
1
15 1
2
30 2
1 2


### Sample Output 1

25


We can unlock all the boxes by purchasing the first and second keys, at the cost of 25 yen, which is the minimum cost required.

### Sample Input 2

12 1
100000 1
2


### Sample Output 2

-1


We cannot unlock all the boxes.

### Sample Input 3

4 6
67786 3
1 3 4
3497 1
2
44908 3
2 3 4
2156 3
2 3 4
26230 1
2
86918 1
3


### Sample Output 3

69942

F - Pure

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

N 頂点 M 辺の有向グラフ G が与えられます。
このグラフの頂点には 1 から N までの番号が付けられており、i 番目の辺は頂点 A_i から頂点 B_i に向けて張られています。
このグラフは自己辺や多重辺を持たないことが保証されています。

すべての頂点の入次数が 1、出次数が 1 であるような G の誘導部分グラフ (注記を参照) が存在するか判定し、 存在するならその一例を示してください。
ただし、空グラフは含めないものとします。

### 注記

• V'V の (空でない) 部分集合である。
• E' は、E の辺であって両端点がともに V' に含まれるものすべてを含む集合である。

### 制約

• 1 \leq N \leq 1000
• 0 \leq M \leq 2000
• 1 \leq A_i,B_i \leq N
• A_i \neq B_i
• (A_i, B_i) はすべて異なる。
• 入力はすべて整数である。

### 入力

N M
A_1 B_1
A_2 B_2
:
A_M B_M


### 出力

K
v_1
v_2
:
v_K


これは、頂点数が K、頂点集合が \{v_1, v_2, \ldots, v_K\} であるような G の誘導部分グラフを表します。(v_1, v_2, \ldots, v_K の順序は問いません。) 条件を満たす G の誘導部分グラフが複数存在するときは、そのうちのどれを出力しても構いません。

### 入力例 1

4 5
1 2
2 3
2 4
4 1
4 3


### 出力例 1

3
1
2
4


### 入力例 2

4 5
1 2
2 3
2 4
1 4
4 3


### 出力例 2

-1


### 入力例 3

6 9
1 2
2 3
3 4
4 5
5 6
5 1
5 2
6 1
6 2


### 出力例 3

4
2
3
4
5


Score : 600 points

### Problem Statement

Given is a directed graph G with N vertices and M edges.
The vertices are numbered 1 to N, and the i-th edge is directed from Vertex A_i to Vertex B_i.
It is guaranteed that the graph contains no self-loops or multiple edges.

Determine whether there exists an induced subgraph (see Notes) of G such that the in-degree and out-degree of every vertex are both 1. If the answer is yes, show one such subgraph.
Here the null graph is not considered as a subgraph.

### Notes

For a directed graph G = (V, E), we call a directed graph G' = (V', E') satisfying the following conditions an induced subgraph of G:

• V' is a (non-empty) subset of V.
• E' is the set of all the edges in E that have both endpoints in V'.

### Constraints

• 1 \leq N \leq 1000
• 0 \leq M \leq 2000
• 1 \leq A_i,B_i \leq N
• A_i \neq B_i
• All pairs (A_i, B_i) are distinct.
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
A_2 B_2
:
A_M B_M


### Output

If there is no induced subgraph of G that satisfies the condition, print -1. Otherwise, print an induced subgraph of G that satisfies the condition, in the following format:

K
v_1
v_2
:
v_K


This represents the induced subgraph of G with K vertices whose vertex set is \{v_1, v_2, \ldots, v_K\}. (The order of v_1, v_2, \ldots, v_K does not matter.) If there are multiple subgraphs of G that satisfy the condition, printing any of them is accepted.

### Sample Input 1

4 5
1 2
2 3
2 4
4 1
4 3


### Sample Output 1

3
1
2
4


The induced subgraph of G whose vertex set is \{1, 2, 4\} has the edge set \{(1, 2), (2, 4), (4, 1)\}. The in-degree and out-degree of every vertex in this graph are both 1.

### Sample Input 2

4 5
1 2
2 3
2 4
1 4
4 3


### Sample Output 2

-1


There is no induced subgraph of G that satisfies the condition.

### Sample Input 3

6 9
1 2
2 3
3 4
4 5
5 6
5 1
5 2
6 1
6 2


### Sample Output 3

4
2
3
4
5