Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
2 つの 整数 a,b が与えられます。 a+b=15 であるか、a\times b=15 であるか、そのどちらでもないかを判定してください。
ただし、a+b=15 と a\times b=15 が同時に成り立つことはありません。
制約
- 1 \leq a,b \leq 15
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
a b
出力
a+b=15 であれば + を、
a\times b=15 であれば * を、
どちらでもなければ x を出力してください。
入力例 1
4 11
出力例 1
+
4+11=15 です。
入力例 2
3 5
出力例 2
*
3\times 5=15 です。
入力例 3
1 1
出力例 3
x
1+1=2 であり、 1\times 1=1であるため、どちらも 15 ではありません。
Score : 100 points
Problem Statement
You are given two integers a and b. Determine if a+b=15 or a\times b=15 or neither holds.
Note that a+b=15 and a\times b=15 do not hold at the same time.
Constraints
- 1 \leq a,b \leq 15
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
a b
Output
If a+b=15, print +;
if a\times b=15, print *;
if neither holds, print x.
Sample Input 1
4 11
Sample Output 1
+
4+11=15.
Sample Input 2
3 5
Sample Output 2
*
3\times 5=15.
Sample Input 3
1 1
Sample Output 3
x
1+1=2 and 1\times 1=1, neither of which is 15.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
小文字のアルファベットからなる文字列 S が与えられます。 この文字列を w 文字ごとに改行したときに、各行の先頭の文字を上から順番につなげて得られる文字列を出力してください。
制約
- 1\leq w\leq |S| \leq 1000
- S は小文字のアルファベットのみからなる
- w は整数
入力
入力は以下の形式で標準入力から与えられる。
S w
出力
答えの文字列を 1 行に出力してください。
入力例 1
abcdefgh 3
出力例 1
adg
abcdefgh を 3 文字ごとに改行すると、
abc
def
gh
となります。これらの行の先頭の文字を上から順に読むと adg となります。
入力例 2
lllll 1
出力例 2
lllll
入力例 3
souuundhound 2
出力例 3
suudon
Score : 200 points
Problem Statement
You are given a string S consisting of lowercase English letters. We will write down this string, starting a new line after every w letters. Print the string obtained by concatenating the letters at the beginnings of these lines from top to bottom.
Constraints
- 1 \leq w \leq |S| \leq 1000
- S consists of lowercase English letters.
- w is an integer.
Input
Input is given from Standard Input in the following format:
S w
Output
Print the desired string in one line.
Sample Input 1
abcdefgh 3
Sample Output 1
adg
When we write down abcdefgh, starting a new line after every three letters, we get the following:
abc
def
gh
Concatenating the letters at the beginnings of these lines, we obtain adg.
Sample Input 2
lllll 1
Sample Output 2
lllll
Sample Input 3
souuundhound 2
Sample Output 3
suudon
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
数列 (a_1,... ,a_n) の 美しさ を、隣り合う 2 項の組であって、 差の絶対値が d であるものの個数として定義します。 例えば、d=1 であるとき、数列 (3, 2, 3, 10, 9) の美しさは 3 です。
各要素が 1 以上 n 以下の整数である長さ m の数列は全部で n^m 通り存在します。 この n^m 通りの数列すべてに対して美しさを求めて、 それらの平均を出力してください。
制約
- 0 \leq d < n \leq 10^9
- 2 \leq m \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
n m d
出力
各要素が 1 以上 n 以下の整数である長さ m の数列 の美しさの平均を出力せよ。 絶対誤差または相対誤差が 10^{-6} 以下ならば正解となる。
入力例 1
2 3 1
出力例 1
1.0000000000
(1,1,1) の美しさは 0 です。
(1,1,2) の美しさは 1 です。
(1,2,1) の美しさは 2 です。
(1,2,2) の美しさは 1 です。
(2,1,1) の美しさは 1 です。
(2,1,2) の美しさは 2 です。
(2,2,1) の美しさは 1 です。
(2,2,2) の美しさは 0 です。
これらの平均である、 (0+1+2+1+1+2+1+0)/8=1 が答えとなります。
入力例 2
1000000000 180707 0
出力例 2
0.0001807060
Score : 300 points
Problem Statement
Let us define the beauty of a sequence (a_1,... ,a_n) as the number of pairs of two adjacent elements in it whose absolute differences are d. For example, when d=1, the beauty of the sequence (3, 2, 3, 10, 9) is 3.
There are a total of n^m sequences of length m where each element is an integer between 1 and n (inclusive). Find the beauty of each of these n^m sequences, and print the average of those values.
Constraints
- 0 \leq d < n \leq 10^9
- 2 \leq m \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
n m d
Output
Print the average of the beauties of the sequences of length m where each element is an integer between 1 and n. The output will be judged correct if the absolute or relative error is at most 10^{-6}.
Sample Input 1
2 3 1
Sample Output 1
1.0000000000
The beauty of (1,1,1) is 0.
The beauty of (1,1,2) is 1.
The beauty of (1,2,1) is 2.
The beauty of (1,2,2) is 1.
The beauty of (2,1,1) is 1.
The beauty of (2,1,2) is 2.
The beauty of (2,2,1) is 1.
The beauty of (2,2,2) is 0.
The answer is the average of these values: (0+1+2+1+1+2+1+0)/8=1.
Sample Input 2
1000000000 180707 0
Sample Output 2
0.0001807060
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
kenkoooo さんはすぬけ国での旅行の計画を立てています。 すぬけ国には n 個の都市があり、m 本の電車が走っています。 都市には 1 から n の番号がつけられていて、 i 番目の電車は都市 u_i と v_i の間を両方向に走っています。 どの都市からどの都市へも電車を乗り継ぐことで到達できます。
すぬけ国で使える通貨には、円とスヌークの 2 種類があります。 どの電車の運賃も円とスヌークのどちらの通貨でも支払え、 i 番目の電車の運賃は、 円で支払う場合 a_i 円、 スヌークで払う場合 b_i スヌークです。
両替所のある都市に行くと、1 円を 1 スヌークに両替することができます。 ただし、 両替をするときには持っている円すべてをスヌークに両替しなければなりません。 つまり、kenkoooo さんの所持金が X 円であるときに両替をすると、 kenkoooo さんの所持金は X スヌークになります。 現在、両替所は n 個の都市すべてに存在しますが、 i 番目の都市の両替所は今年から i 年後に閉鎖されてしまい、 i 年後とそれ以降は使うことができません。
kenkoooo さんは 10^{15} 円を持って都市 s から旅に出て、 都市 t へ向かおうと思っています。 移動中、kenkoooo さんは両替所のある都市のいずれかで円をスヌークに両替しようと考えています。 ただし、都市 s または都市 t の両替所で両替をしてもよいものとします。
kenkoooo さんは移動の経路と両替をする都市を適切に選ぶことで、できるだけ多くのスヌークを持っている状態で 都市 t に辿り着きたいと考えています。 i=0,...,n-1 のそれぞれについて、i 年後に都市 s から都市 t へ移動した際に kenkoooo さんが所持しているスヌークの最大額を求めてください。 ただし、旅行中に年をまたぐことは無いとします。
制約
- 2 \leq n \leq 10^5
- 1 \leq m \leq 10^5
- 1 \leq s,t \leq n
- s \neq t
- 1 \leq u_i < v_i \leq n
- 1 \leq a_i,b_i \leq 10^9
- i\neq j のとき u_i \neq u_j または v_i \neq v_j
- どの都市からどの都市へも電車を乗り継ぐことで到達できる
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
n m s t u_1 v_1 a_1 b_1 : u_m v_m a_m b_m
出力
n 行出力せよ。 i 行目には、 i-1 年後に都市 s から都市 t へ移動した際に kenkoooo さんの所持しているスヌークの最大額を出力せよ。
入力例 1
4 3 2 3 1 4 1 100 1 2 1 10 1 3 20 1
出力例 1
999999999999998 999999999999989 999999999999979 999999999999897
0 年後には、都市 1 で両替をするのが最適です。
1 年後には、都市 2 で両替をするのが最適です。
両替所が閉鎖されても都市 1 を訪れることは可能であることに注意してください。
また、都市 2 で両替をするときに 1 円だけ残して残りをスヌークに両替をすると
999999999999998 スヌークを持った状態で都市 3 にたどり着けますが、
このような両替は許されていないことにも注意してください。
2 年後には、都市 3 で両替をするのが最適です。
3 年後には、都市 4 で両替をするのが最適です。
同じ電車を複数回使っても良いことに注意してください。
入力例 2
8 12 3 8 2 8 685087149 857180777 6 7 298270585 209942236 2 4 346080035 234079976 2 5 131857300 22507157 4 8 30723332 173476334 2 6 480845267 448565596 1 4 181424400 548830121 4 5 57429995 195056405 7 8 160277628 479932440 1 6 475692952 203530153 3 5 336869679 160714712 2 7 389775999 199123879
出力例 2
999999574976994 999999574976994 999999574976994 999999574976994 999999574976994 999999574976994 999999574976994 999999574976994
Score : 400 points
Problem Statement
Kenkoooo is planning a trip in Republic of Snuke. In this country, there are n cities and m trains running. The cities are numbered 1 through n, and the i-th train connects City u_i and v_i bidirectionally. Any city can be reached from any city by changing trains.
Two currencies are used in the country: yen and snuuk. Any train fare can be paid by both yen and snuuk. The fare of the i-th train is a_i yen if paid in yen, and b_i snuuk if paid in snuuk.
In a city with a money exchange office, you can change 1 yen into 1 snuuk. However, when you do a money exchange, you have to change all your yen into snuuk. That is, if Kenkoooo does a money exchange when he has X yen, he will then have X snuuk. Currently, there is a money exchange office in every city, but the office in City i will shut down in i years and can never be used in and after that year.
Kenkoooo is planning to depart City s with 10^{15} yen in his pocket and head for City t, and change his yen into snuuk in some city while traveling. It is acceptable to do the exchange in City s or City t.
Kenkoooo would like to have as much snuuk as possible when he reaches City t by making the optimal choices for the route to travel and the city to do the exchange. For each i=0,...,n-1, find the maximum amount of snuuk that Kenkoooo has when he reaches City t if he goes on a trip from City s to City t after i years. You can assume that the trip finishes within the year.
Constraints
- 2 \leq n \leq 10^5
- 1 \leq m \leq 10^5
- 1 \leq s,t \leq n
- s \neq t
- 1 \leq u_i < v_i \leq n
- 1 \leq a_i,b_i \leq 10^9
- If i\neq j, then u_i \neq u_j or v_i \neq v_j.
- Any city can be reached from any city by changing trains.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
n m s t u_1 v_1 a_1 b_1 : u_m v_m a_m b_m
Output
Print n lines. In the i-th line, print the maximum amount of snuuk that Kenkoooo has when he reaches City t if he goes on a trip from City s to City t after i-1 years.
Sample Input 1
4 3 2 3 1 4 1 100 1 2 1 10 1 3 20 1
Sample Output 1
999999999999998 999999999999989 999999999999979 999999999999897
After 0 years, it is optimal to do the exchange in City 1.
After 1 years, it is optimal to do the exchange in City 2.
Note that City 1 can still be visited even after the exchange office is closed.
Also note that, if it was allowed to keep 1 yen when do the exchange in City 2 and change the remaining yen into snuuk, we could reach City 3 with 999999999999998 snuuk, but this is NOT allowed.
After 2 years, it is optimal to do the exchange in City 3.
After 3 years, it is optimal to do the exchange in City 4.
Note that the same train can be used multiple times.
Sample Input 2
8 12 3 8 2 8 685087149 857180777 6 7 298270585 209942236 2 4 346080035 234079976 2 5 131857300 22507157 4 8 30723332 173476334 2 6 480845267 448565596 1 4 181424400 548830121 4 5 57429995 195056405 7 8 160277628 479932440 1 6 475692952 203530153 3 5 336869679 160714712 2 7 389775999 199123879
Sample Output 2
999999574976994 999999574976994 999999574976994 999999574976994 999999574976994 999999574976994 999999574976994 999999574976994
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
kenkooooさんは n 頂点 m 辺の単純連結グラフを拾いました。 グラフの頂点には 1 から n の番号が付けられていて、 i 番目の辺は頂点 u_i と v_i をつないでいます。 また、i 番目の辺には整数 s_i が定められています。
kenkooooさんは次の条件を満たすようにそれぞれの頂点に 正の整数 を書き込もうとしています。
- どの辺 i についても、頂点 u_i と v_i に書かれた正の整数の和は s_i に等しい
条件を満たすような正の整数の書き方が何通りあるか求めてください。
制約
- 2 \leq n \leq 10^5
- 1 \leq m \leq 10^5
- 1 \leq u_i < v_i \leq n
- 2 \leq s_i \leq 10^9
- i\neq j のとき u_i \neq u_j または v_i \neq v_j
- グラフは連結
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
n m u_1 v_1 s_1 : u_m v_m s_m
出力
条件を満たす正の整数の書き込み方が何通りあるか出力せよ。
入力例 1
3 3 1 2 3 2 3 5 1 3 4
出力例 1
1
頂点 1,2,3 にそれぞれ 1,2,3 を書くと条件を満たします。 これ以外に条件を満たすような整数の書き方は無いため、答えは 1 です。
入力例 2
4 3 1 2 6 2 3 7 3 4 5
出力例 2
3
頂点 1,2,3,4 に書く数をそれぞれ a,b,c,d で表すことにすると、条件を満たす (a,b,c,d)の組は以下の 3 つです。
- (a,b,c,d)=(1,5,2,3)
- (a,b,c,d)=(2,4,3,2)
- (a,b,c,d)=(3,3,4,1)
入力例 3
8 7 1 2 1000000000 2 3 2 3 4 1000000000 4 5 2 5 6 1000000000 6 7 2 7 8 1000000000
出力例 3
0
Score : 600 points
Problem Statement
Kenkoooo found a simple connected graph. The vertices are numbered 1 through n. The i-th edge connects Vertex u_i and v_i, and has a fixed integer s_i.
Kenkoooo is trying to write a positive integer in each vertex so that the following condition is satisfied:
- For every edge i, the sum of the positive integers written in Vertex u_i and v_i is equal to s_i.
Find the number of such ways to write positive integers in the vertices.
Constraints
- 2 \leq n \leq 10^5
- 1 \leq m \leq 10^5
- 1 \leq u_i < v_i \leq n
- 2 \leq s_i \leq 10^9
- If i\neq j, then u_i \neq u_j or v_i \neq v_j.
- The graph is connected.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
n m u_1 v_1 s_1 : u_m v_m s_m
Output
Print the number of ways to write positive integers in the vertices so that the condition is satisfied.
Sample Input 1
3 3 1 2 3 2 3 5 1 3 4
Sample Output 1
1
The condition will be satisfied if we write 1,2 and 3 in vertices 1,2 and 3, respectively. There is no other way to satisfy the condition, so the answer is 1.
Sample Input 2
4 3 1 2 6 2 3 7 3 4 5
Sample Output 2
3
Let a,b,c and d be the numbers to write in vertices 1,2,3 and 4, respectively. There are three quadruples (a,b,c,d) that satisfy the condition:
- (a,b,c,d)=(1,5,2,3)
- (a,b,c,d)=(2,4,3,2)
- (a,b,c,d)=(3,3,4,1)
Sample Input 3
8 7 1 2 1000000000 2 3 2 3 4 1000000000 4 5 2 5 6 1000000000 6 7 2 7 8 1000000000
Sample Output 3
0