Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 100 点
問題文
3 桁の正の整数 N が与えられます。
N が 回文数であるかを判定してください。
回文数とは、10 進法において数字を逆から並べても元の数と同じになる数のことを表します。
制約
- 100≦N≦999
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
N が回文数である場合は Yes、そうでない場合は No を出力せよ。
入力例 1
575
出力例 1
Yes
N=575 は逆から数字を並べても 575 となるため回文数です。したがって、Yes と出力します。
入力例 2
123
出力例 2
No
N=123 は逆から数字を並べると 321 となり、回文数ではないため No と出力します。
入力例 3
812
出力例 3
No
Score : 100 points
Problem Statement
You are given a three-digit positive integer N.
Determine whether N is a palindromic number.
Here, a palindromic number is an integer that reads the same backward as forward in decimal notation.
Constraints
- 100≤N≤999
- N is an integer.
Input
Input is given from Standard Input in the following format:
N
Output
If N is a palindromic number, print Yes; otherwise, print No.
Sample Input 1
575
Sample Output 1
Yes
N=575 is also 575 when read backward, so it is a palindromic number. You should print Yes.
Sample Input 2
123
Sample Output 2
No
N=123 becomes 321 when read backward, so it is not a palindromic number. You should print No.
Sample Input 3
812
Sample Output 3
No
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 200 点
問題文
Alice と Bob は、ロボットを制御するためのスイッチを1つずつ持っており、ロボットを動かしています。
Alice はロボットを動かし始めて A 秒後にスイッチを押し始め、ロボットを動かし始めて B 秒後にスイッチを離しました。
Bob はロボットを動かし始めて C 秒後にスイッチを押し始め、ロボットを動かし始めて D 秒後にスイッチを離しました。
Alice と Bob が、二人ともスイッチを押していた秒数を求めてください。
制約
- 0≦A<B≦100
- 0≦C<D≦100
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
A B C D
出力
Alice と Bob が二人ともスイッチを押していた秒数を出力せよ。
入力例 1
0 75 25 100
出力例 1
50
ロボットを動し始めて 0 秒後から 75 秒後までの間、Alice はスイッチを押していました。 一方、ロボットを動し始めて 25 秒後から 100 秒後までの間、Bob はスイッチを押していました。 したがって、二人が同時にスイッチを押していた時間は、ロボットを動し始めて 25 秒後から 75 秒後までの 50 秒です。
入力例 2
0 33 66 99
出力例 2
0
Alice と Bob が同時にスイッチを押していないので、答えは 0 秒です。
入力例 3
10 90 20 80
出力例 3
60
Score : 200 points
Problem Statement
Alice and Bob are controlling a robot. They each have one switch that controls the robot.
Alice started holding down her button A second after the start-up of the robot, and released her button B second after the start-up.
Bob started holding down his button C second after the start-up, and released his button D second after the start-up.
For how many seconds both Alice and Bob were holding down their buttons?
Constraints
- 0≤A<B≤100
- 0≤C<D≤100
- All input values are integers.
Input
Input is given from Standard Input in the following format:
A B C D
Output
Print the length of the duration (in seconds) in which both Alice and Bob were holding down their buttons.
Sample Input 1
0 75 25 100
Sample Output 1
50
Alice started holding down her button 0 second after the start-up of the robot, and released her button 75 second after the start-up.
Bob started holding down his button 25 second after the start-up, and released his button 100 second after the start-up.
Therefore, the time when both of them were holding down their buttons, is the 50 seconds from 25 seconds after the start-up to 75 seconds after the start-up.
Sample Input 2
0 33 66 99
Sample Output 2
0
Alice and Bob were not holding their buttons at the same time, so the answer is zero seconds.
Sample Input 3
10 90 20 80
Sample Output 3
60
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 300 点
問題文
N 台の時計があり、i(1≦i≦N) 番目の時計の針はちょうど T_i 秒で時計盤を 1 周します。
最初、全ての時計の針は真っ直ぐ上に向いており、止まっています。
イルカは、全ての時計の針を同時に動かし始めました。
再び、全ての時計の針が真っ直ぐ上に向くのは何秒後でしょうか?
制約
- 1≦N≦100
- 1≦T_i≦10^{18}
- 入力は全て整数である。
- 答えは 10^{18} 秒以内である。
入力
入力は以下の形式で標準入力から与えられる。
N T_1 : T_N
出力
時計の針を動かし始めてから、再び全ての時計の針が真っ直ぐ上に向くまでの秒数を出力せよ。
入力例 1
2 2 3
出力例 1
6
2 つの時計があり、各時計の針が真っ直ぐ上に向くのは以下の時刻です。
- 1 番目の時計の針: 時計の針を動かし始めてから、2 秒後、4 秒後、6 秒後、...
- 2 番目の時計の針: 時計の針を動かし始めてから、3 秒後、6 秒後、9 秒後、...
したがって、2 つの時計の針が真っ直ぐ上に向くのにかかる秒数は 6 秒となります。
入力例 2
5 2 5 10 1000000000000000000 1000000000000000000
出力例 2
1000000000000000000
Score : 300 points
Problem Statement
We have N clocks. The hand of the i-th clock (1≤i≤N) rotates through 360° in exactly T_i seconds.
Initially, the hand of every clock stands still, pointing directly upward.
Now, Dolphin starts all the clocks simultaneously.
In how many seconds will the hand of every clock point directly upward again?
Constraints
- 1≤N≤100
- 1≤T_i≤10^{18}
- All input values are integers.
- The correct answer is at most 10^{18} seconds.
Input
Input is given from Standard Input in the following format:
N T_1 : T_N
Output
Print the number of seconds after which the hand of every clock point directly upward again.
Sample Input 1
2 2 3
Sample Output 1
6
We have two clocks. The time when the hand of each clock points upward is as follows:
- Clock 1: 2, 4, 6, ... seconds after the beginning
- Clock 2: 3, 6, 9, ... seconds after the beginning
Therefore, it takes 6 seconds until the hands of both clocks point directly upward.
Sample Input 2
5 2 5 10 1000000000000000000 1000000000000000000
Sample Output 2
1000000000000000000
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 400 点
問題文
N 頂点の木が与えられます。
木とはグラフの一種であり、頂点の数を N とすると、辺の数が N-1 本である閉路のない連結グラフです。
i(1≦i≦N-1) 番目の辺は 頂点 a_i と 頂点 b_i を距離 c_i で結びます。
また、Q 個の質問クエリと整数 K が与えられます。
- j(1≦j≦Q) 番目の質問クエリでは、頂点 x_j から 頂点 K を経由しつつ、頂点 y_j まで移動する場合の最短経路の距離を求めてください。
制約
- 3≦N≦10^5
- 1≦a_i,b_i≦N (1≦i≦N-1)
- 1≦c_i≦10^9 (1≦i≦N-1)
- 与えられるグラフは木である。
- 1≦Q≦10^5
- 1≦K≦N
- 1≦x_j,y_j≦N (1≦j≦Q)
- x_j≠y_j (1≦j≦Q)
- x_j≠K,y_j≠K (1≦j≦Q)
入力
入力は以下の形式で標準入力から与えられる。
N
a_1 b_1 c_1
:
a_{N-1} b_{N-1} c_{N-1}
Q K
x_1 y_1
:
x_{Q} y_{Q}
出力
質問クエリの解答を Q 行出力せよ。
j(1≦j≦Q) 行目には、j 番目のクエリの答えを出力せよ。
入力例 1
5 1 2 1 1 3 1 2 4 1 3 5 1 3 1 2 4 2 3 4 5
出力例 1
3 2 4
与えられた 3 つの質問クエリに対する最短経路は以下の通りです。
- 1 つ目の質問クエリ: 頂点 2 → 頂点 1 → 頂点 2 → 頂点 4 : 距離 1+1+1=3
- 2 つ目の質問クエリ: 頂点 2 → 頂点 1 → 頂点 3 : 距離 1+1=2
- 3 つ目の質問クエリ: 頂点 4 → 頂点 2 → 頂点 1 → 頂点 3 → 頂点 5 : 距離 1+1+1+1=4
入力例 2
7 1 2 1 1 3 3 1 4 5 1 5 7 1 6 9 1 7 11 3 2 1 3 4 5 6 7
出力例 2
5 14 22
質問クエリに対する最短経路は、必ず頂点 K=2 を通過する必要があります。
入力例 3
10 1 2 1000000000 2 3 1000000000 3 4 1000000000 4 5 1000000000 5 6 1000000000 6 7 1000000000 7 8 1000000000 8 9 1000000000 9 10 1000000000 1 1 9 10
出力例 3
17000000000
Score : 400 points
Problem Statement
You are given a tree with N vertices.
Here, a tree is a kind of graph, and more specifically, a connected undirected graph with N-1 edges, where N is the number of its vertices.
The i-th edge (1≤i≤N-1) connects Vertices a_i and b_i, and has a length of c_i.
You are also given Q queries and an integer K. In the j-th query (1≤j≤Q):
- find the length of the shortest path from Vertex x_j and Vertex y_j via Vertex K.
Constraints
- 3≤N≤10^5
- 1≤a_i,b_i≤N (1≤i≤N-1)
- 1≤c_i≤10^9 (1≤i≤N-1)
- The given graph is a tree.
- 1≤Q≤10^5
- 1≤K≤N
- 1≤x_j,y_j≤N (1≤j≤Q)
- x_j≠y_j (1≤j≤Q)
- x_j≠K,y_j≠K (1≤j≤Q)
Input
Input is given from Standard Input in the following format:
N
a_1 b_1 c_1
:
a_{N-1} b_{N-1} c_{N-1}
Q K
x_1 y_1
:
x_{Q} y_{Q}
Output
Print the responses to the queries in Q lines.
In the j-th line j(1≤j≤Q), print the response to the j-th query.
Sample Input 1
5 1 2 1 1 3 1 2 4 1 3 5 1 3 1 2 4 2 3 4 5
Sample Output 1
3 2 4
The shortest paths for the three queries are as follows:
- Query 1: Vertex 2 → Vertex 1 → Vertex 2 → Vertex 4 : Length 1+1+1=3
- Query 2: Vertex 2 → Vertex 1 → Vertex 3 : Length 1+1=2
- Query 3: Vertex 4 → Vertex 2 → Vertex 1 → Vertex 3 → Vertex 5 : Length 1+1+1+1=4
Sample Input 2
7 1 2 1 1 3 3 1 4 5 1 5 7 1 6 9 1 7 11 3 2 1 3 4 5 6 7
Sample Output 2
5 14 22
The path for each query must pass Vertex K=2.
Sample Input 3
10 1 2 1000000000 2 3 1000000000 3 4 1000000000 4 5 1000000000 5 6 1000000000 6 7 1000000000 7 8 1000000000 8 9 1000000000 9 10 1000000000 1 1 9 10
Sample Output 3
17000000000