Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
整数 N が与えられます。
高橋君は、N 以下の正整数の中から等確率で 1 つを選んで a とします。
このとき、a が奇数である確率を答えてください。
制約
- 1 ≤ N ≤ 100
入力
入力は以下の形式で標準入力から与えられる。
N
出力
a が奇数である確率を出力せよ。 出力は、ジャッジの出力との絶対誤差または相対誤差が 10^{-6} 以下のとき正解と判定される。
入力例 1
4
出力例 1
0.5000000000
4 以下の正整数は 1 , 2 , 3 , 4 の 4 つであり、そのうち奇数は 1 , 3 の 2 つです。以上より、答えは \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
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
高橋君の仲間たちは N 人で遊園地に遊びにいきました。
遊園地の一番人気のジェットコースターに乗るためには、身長が K cm以上必要です。
高橋君の i 番目の仲間の身長は h_i cm です。
高橋君の仲間たちのうち、一番人気のジェットコースターに乗ることができる人の数を求めてください。
制約
- 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
一番人気のジェットコースターに乗ることができるのは、1 番目の仲間と 4 番目の仲間の 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
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
高橋くんは N 人の生徒たちのいるクラスの担当教師です。
生徒たちには 1 から N までの出席番号が重複なく割り当てられています。
今日は全ての生徒たちが相異なるタイミングで登校しました。
高橋くんは、出席番号 i の生徒が登校した時点で、教室に A_i 人の生徒たちがいたことを記録しています(出席番号 i の生徒を含む)。
記録された情報を元に、生徒たちの登校した順番を復元してください。
制約
- 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
最初に出席番号 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
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
正整数 A, B が与えられます。
A と B の正の公約数の中からいくつかを選びます。
ただし、選んだ整数の中のどの異なる 2 つの整数についても互いに素でなければなりません。
最大でいくつ選べるでしょうか。
公約数とは
整数 d が整数 x と整数 y の公約数であるとは、d が x と y をともに割り切ることをいいます。
互いに素とは
整数 x, y が互いに素であるとは、x, y の正の公約数が 1 のみであることをいいます。
割り切るとは
整数 x が整数 y を割り切るとは、y = \alpha x なる整数 \alpha が存在することをいいます。
制約
- 入力は全て整数である。
- 1 \leq A, B \leq 10^{12}
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
条件を満たすように選べる整数の個数の最大値を出力せよ。
入力例 1
12 18
出力例 1
3
12 と 18 の正の公約数は 1, 2, 3, 6 です。
1 と 2、2 と 3、3 と 1 は互いに素なので、1, 2, 3 を選ぶことができ、このときが最大です。
入力例 2
420 660
出力例 2
4
入力例 3
1 2019
出力例 3
1
1 と 2019 の正の公約数は 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.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
鍵のかかった宝箱が N 個あり、1 から N までの番号がつけられています。
店で M 個の鍵が売られています。i 個目の鍵は a_i 円で販売されており、b_i 種類の宝箱 c_{i1} , c_{i2} , ..., c_{i{b_i}} を開けることが出来ます。購入した鍵は何度でも使うことが出来ます。
全ての宝箱を開ける為に必要な費用の最小値を答えてください。全ての宝箱を開けることが不可能である場合は -1 を出力してください。
制約
- 入力は全て整数
- 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 を出力せよ。
入力例 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
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
N 頂点 M 辺の有向グラフ G が与えられます。
このグラフの頂点には 1 から N までの番号が付けられており、i 番目の辺は頂点 A_i から頂点 B_i に向けて張られています。
このグラフは自己辺や多重辺を持たないことが保証されています。
すべての頂点の入次数が 1、出次数が 1 であるような G の誘導部分グラフ (注記を参照) が存在するか判定し、
存在するならその一例を示してください。
ただし、空グラフは含めないものとします。
注記
有向グラフ G = (V, E) に対し、次のような条件を満たす有向グラフ G' = (V', E') を 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
出力
条件を満たす G の誘導部分グラフが存在しないとき、-1 と出力してください。
そうでないとき、以下のフォーマットで条件を満たす G の誘導部分グラフの一例を出力してください。
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
頂点集合が \{1, 2, 4\} であるような G の誘導部分グラフの辺集合は \{(1, 2), (2, 4), (4, 1)\} であり、すべての頂点の入次数が 1、出次数が 1 となります。
入力例 2
4 5 1 2 2 3 2 4 1 4 4 3
出力例 2
-1
条件を満たす G の誘導部分グラフは存在しません。
入力例 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