Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 100 点
問題文
3 つの整数 A,B,C が与えられます。
整数 C が A 以上 かつ B 以下であるかを判定してください。
制約
- -100≦A,B,C≦100
- A,B,C は全て整数
入力
入力は以下の形式で標準入力から与えられる。
A B C
出力
条件を満たす場合はYes、そうでない場合はNoを出力せよ。
入力例 1
1 3 2
出力例 1
Yes
整数 C=2 は A=1 以上 かつ、B=3 以下 であるためYesと出力します。
入力例 2
6 5 4
出力例 2
No
整数 C=4 は A=6 以上ではないためNoと出力します。
入力例 3
2 2 2
出力例 3
Yes
Score : 100 points
Problem Statement
You are given three integers A, B and C. Determine whether C is not less than A and not greater than B.
Constraints
- -100≤A,B,C≤100
- A, B and C are all integers.
Input
Input is given from Standard Input in the following format:
A B C
Output
If the condition is satisfied, print Yes; otherwise, print No.
Sample Input 1
1 3 2
Sample Output 1
Yes
C=2 is not less than A=1 and not greater than B=3, and thus the output should be Yes.
Sample Input 2
6 5 4
Sample Output 2
No
C=4 is less than A=6, and thus the output should be No.
Sample Input 3
2 2 2
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 200 点
問題文
N 個の都市があり、M 本の道路があります。
i(1≦i≦M) 番目の道路は、都市 a_i と 都市 b_i (1≦a_i,b_i≦N) を双方向に結んでいます。
同じ 2 つの都市を結ぶ道路は、1 本とは限りません。
各都市から他の都市に向けて、何本の道路が伸びているか求めてください。
制約
- 2≦N,M≦50
- 1≦a_i,b_i≦N
- a_i ≠ b_i
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N M a_1 b_1 : a_M b_M
出力
答えを N 行に出力せよ。
i(1≦i≦N) 行目には、都市 i から他の都市に向けて、何本の道路が伸びているかを出力せよ。
入力例 1
4 3 1 2 2 3 1 4
出力例 1
2 2 1 1
- 都市 1 からは 1 番目と 3 番目の道路が伸びています。
- 都市 2 からは 1 番目と 2 番目の道路が伸びています。
- 都市 3 からは 2 番目の道路が伸びています。
- 都市 4 からは 3 番目の道路が伸びています。
入力例 2
2 5 1 2 2 1 1 2 2 1 1 2
出力例 2
5 5
入力例 3
8 8 1 2 3 4 1 5 2 8 3 7 5 2 4 1 6 8
出力例 3
3 3 2 2 2 1 1 2
Score : 200 points
Problem Statement
There are N cities and M roads. The i-th road (1≤i≤M) connects two cities a_i and b_i (1≤a_i,b_i≤N) bidirectionally. There may be more than one road that connects the same pair of two cities. For each city, how many roads are connected to the city?
Constraints
- 2≤N,M≤50
- 1≤a_i,b_i≤N
- a_i ≠ b_i
- All input values are integers.
Input
Input is given from Standard Input in the following format:
N M a_1 b_1 : a_M b_M
Output
Print the answer in N lines. In the i-th line (1≤i≤N), print the number of roads connected to city i.
Sample Input 1
4 3 1 2 2 3 1 4
Sample Output 1
2 2 1 1
- City 1 is connected to the 1-st and 3-rd roads.
- City 2 is connected to the 1-st and 2-nd roads.
- City 3 is connected to the 2-nd road.
- City 4 is connected to the 3-rd road.
Sample Input 2
2 5 1 2 2 1 1 2 2 1 1 2
Sample Output 2
5 5
Sample Input 3
8 8 1 2 3 4 1 5 2 8 3 7 5 2 4 1 6 8
Sample Output 3
3 3 2 2 2 1 1 2
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 300 点
問題文
空の配列が 1 つあります。
この配列に、整数を配列に挿入する操作を N 回行います。
i(1≦i≦N) 回目の操作では、配列に整数 a_i を b_i 個挿入します。
N 回の挿入操作後の配列の中で、K 番目に小さい数を求めてください。
例えば、配列が \{1,2,2,3,3,3\} の時、4 番目に小さい数は 3 となります。
制約
- 1≦N≦10^5
- 1≦a_i,b_i≦10^5
- 1≦K≦b_1…+…b_n
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N K a_1 b_1 : a_N b_N
出力
N 回の挿入操作後の配列の中で、K 番目に小さい数を出力せよ。
入力例 1
3 4 1 1 2 2 3 3
出力例 1
3
操作後の配列は、問題文に書かれている例と同じです。
入力例 2
10 500000 1 100000 1 100000 1 100000 1 100000 1 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000
出力例 2
1
Score : 300 points
Problem Statement
There is an empty array. The following N operations will be performed to insert integers into the array. In the i-th operation (1≤i≤N), b_i copies of an integer a_i are inserted into the array. Find the K-th smallest integer in the array after the N operations. For example, the 4-th smallest integer in the array \{1,2,2,3,3,3\} is 3.
Constraints
- 1≤N≤10^5
- 1≤a_i,b_i≤10^5
- 1≤K≤b_1…+…b_n
- All input values are integers.
Input
Input is given from Standard Input in the following format:
N K a_1 b_1 : a_N b_N
Output
Print the K-th smallest integer in the array after the N operations.
Sample Input 1
3 4 1 1 2 2 3 3
Sample Output 1
3
The resulting array is the same as the one in the problem statement.
Sample Input 2
10 500000 1 100000 1 100000 1 100000 1 100000 1 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000
Sample Output 2
1
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 400 点
問題文
N 頂点 M 辺の重み付き有向グラフがあります。
i(1≦i≦M) 番目の辺は 頂点 a_i から 頂点 b_i を重み c_i で結びます。
このグラフと駒を利用して、次の1人ゲームを行います。
最初、駒を頂点 1 に置いて、プレイヤーのスコアを 0 とします。
プレイヤーは、次の条件で駒を繰り返し移動させることができます。
- 頂点 a_i に駒があるとき、i 番目の辺を利用して頂点 b_i に移動する。移動後にプレイヤーのスコアが c_i 加算される。
頂点 N に駒があるときのみ、ゲームを終了できます。
なお、与えられる有向グラフの上で頂点 1 から頂点 N に移動できることは保障されています。
プレイヤーがゲーム終了時のスコアを出来るだけ大きくするような行動を取ったとき、ゲーム終了時のスコアはいくつになるでしょうか?
ゲーム終了時のスコアをいくらでも大きくできる場合は inf と出力してください。
制約
- 2≦N≦1000
- 1≦M≦min(N(N-1),2000)
- 1≦a_i,b_i≦N (1≦i≦M)
- a_i≠b_i (1≦i≦M)
- a_i≠a_j または b_i≠b_j (1≦i<j≦M)
- -10^9≦c_i≦10^9 (1≦i≦M)
- c_i は整数である。
- 与えられるグラフには、頂点 1 から頂点 N への経路が存在する。
入力
入力は以下の形式で標準入力から与えられる。
N M a_1 b_1 c_1 a_2 b_2 c_2 : a_M b_M c_M
出力
もし、ゲーム終了時のスコアをいくらでも大きくできる場合は inf、そうでない場合はゲーム終了時のスコアの最大値を出力せよ。
入力例 1
3 3 1 2 4 2 3 3 1 3 5
出力例 1
7
駒を頂点 N=3 に移動できる経路は以下の 2 通りです。
- 頂点 1 → 頂点 2 → 頂点 3 : スコア 4+3=7
- 頂点 1 → 頂点 3 : スコア 5
したがって、ゲーム終了時のスコアの最大値は 7 となります。
入力例 2
2 2 1 2 1 2 1 1
出力例 2
inf
頂点 1 → 頂点 2 → 頂点 1 → 頂点 2 … と移動することで、ゲーム終了時のスコアをいくらでも増やせます。
入力例 3
6 5 1 2 -1000000000 2 3 -1000000000 3 4 -1000000000 4 5 -1000000000 5 6 -1000000000
出力例 3
-5000000000
Score : 400 points
Problem Statement
There is a directed graph with N vertices and M edges. The i-th edge (1≤i≤M) points from vertex a_i to vertex b_i, and has a weight c_i. We will play the following single-player game using this graph and a piece.
Initially, the piece is placed at vertex 1, and the score of the player is set to 0. The player can move the piece as follows:
- When the piece is placed at vertex a_i, move the piece along the i-th edge to vertex b_i. After this move, the score of the player is increased by c_i.
The player can end the game only when the piece is placed at vertex N. The given graph guarantees that it is possible to traverse from vertex 1 to vertex N.
When the player acts optimally to maximize the score at the end of the game, what will the score be?
If it is possible to increase the score indefinitely, print inf.
Constraints
- 2≤N≤1000
- 1≤M≤min(N(N-1),2000)
- 1≤a_i,b_i≤N (1≤i≤M)
- a_i≠b_i (1≤i≤M)
- a_i≠a_j or b_i≠b_j (1≤i<j≤M)
- -10^9≤c_i≤10^9 (1≤i≤M)
- c_i is an integer.
- In the given graph, there exists a path from vertex 1 to vertex N.
Input
Input is given from Standard Input in the following format:
N M a_1 b_1 c_1 a_2 b_2 c_2 : a_M b_M c_M
Output
Print the maximum possible score at the end of the game, if it is finite. If it is possible to increase the score indefinitely, print inf.
Sample Input 1
3 3 1 2 4 2 3 3 1 3 5
Sample Output 1
7
There are two ways to move the piece to vertex N=3:
- vertex 1 → vertex 2 → vertex 3 : score 4+3=7
- vertex 1 → vertex 3 : score 5
Thus, the maximum possible score at the end of the game is 7.
Sample Input 2
2 2 1 2 1 2 1 1
Sample Output 2
inf
It is possible to increase the score indefinitely by alternating between vertex 1 and 2.
Sample Input 3
6 5 1 2 -1000000000 2 3 -1000000000 3 4 -1000000000 4 5 -1000000000 5 6 -1000000000
Sample Output 3
-5000000000