Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
A
, B
, C
からなる長さ N の文字列 S と、1 以上 N 以下の整数 K が与えられます。
文字列 S の K 文字目を小文字に書き換え、新しくできた S を出力してください。
制約
- 1 ≤ N ≤ 50
- 1 ≤ K ≤ N
- S は
A
,B
,C
からなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N K S
出力
文字列 S の K 文字目を小文字に書き換え、新しくできた S を出力せよ。
入力例 1
3 1 ABC
出力例 1
aBC
入力例 2
4 3 CABA
出力例 2
CAbA
Score : 100 points
Problem Statement
You are given a string S of length N consisting of A
, B
and C
, and an integer K which is between 1 and N (inclusive).
Print the string S after lowercasing the K-th character in it.
Constraints
- 1 ≤ N ≤ 50
- 1 ≤ K ≤ N
- S is a string of length N consisting of
A
,B
andC
.
Input
Input is given from Standard Input in the following format:
N K S
Output
Print the string S after lowercasing the K-th character in it.
Sample Input 1
3 1 ABC
Sample Output 1
aBC
Sample Input 2
4 3 CABA
Sample Output 2
CAbA
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
長さ 4 の数字列 S が与えられます。あなたは、この数字列が以下のフォーマットのどちらであるか気になっています。
- YYMM フォーマット: 西暦年の下 2 桁と、月を 2 桁で表したもの (例えば 1 月なら
01
) をこの順に並べたもの - MMYY フォーマット: 月を 2 桁で表したもの (例えば 1 月なら
01
) と、西暦年の下 2 桁をこの順に並べたもの
与えられた数字列のフォーマットとして考えられるものが YYMM フォーマットのみである場合 YYMM
を、
MMYY フォーマットのみである場合 MMYY
を、
YYMM フォーマット と MMYY フォーマットのどちらの可能性もある場合 AMBIGUOUS
を、
どちらの可能性もない場合 NA
を出力してください。
制約
- S は長さ 4 の数字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
YYMM
, MMYY
, AMBIGUOUS
, NA
のうち正しいものを出力せよ。
入力例 1
1905
出力例 1
YYMM
19 年 5 月はありえますが、05 年 19 月はありえません。よって、これは YYMM フォーマットです。
入力例 2
0112
出力例 2
AMBIGUOUS
01 年 12 月も 12 年 1 月もありえます。よって、これはどちらの可能性もあります。
入力例 3
1700
出力例 3
NA
17 年 0 月も 00 年 17 月もありえません。よって、これはどちらの可能性もありません。
Score : 200 points
Problem Statement
You have a digit sequence S of length 4. You are wondering which of the following formats S is in:
- YYMM format: the last two digits of the year and the two-digit representation of the month (example:
01
for January), concatenated in this order - MMYY format: the two-digit representation of the month and the last two digits of the year, concatenated in this order
If S is valid in only YYMM format, print YYMM
; if S is valid in only MMYY format, print MMYY
; if S is valid in both formats, print AMBIGUOUS
; if S is valid in neither format, print NA
.
Constraints
- S is a digit sequence of length 4.
Input
Input is given from Standard Input in the following format:
S
Output
Print the specified string: YYMM
, MMYY
, AMBIGUOUS
or NA
.
Sample Input 1
1905
Sample Output 1
YYMM
May XX19 is a valid date, but 19 is not valid as a month. Thus, this string is only valid in YYMM format.
Sample Input 2
0112
Sample Output 2
AMBIGUOUS
Both December XX01 and January XX12 are valid dates. Thus, this string is valid in both formats.
Sample Input 3
1700
Sample Output 3
NA
Neither 0 nor 17 is valid as a month. Thus, this string is valid in neither format.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
すぬけ君は 1 〜 N の整数が等確率で出る N 面サイコロと表と裏が等確率で出るコインを持っています。すぬけ君は、このサイコロとコインを使って今から次のようなゲームをします。
- まず、サイコロを 1 回振り、出た目を現在の得点とする。
- 得点が 1 以上 K-1 以下である限り、すぬけ君はコインを振り続ける。表が出たら得点は 2 倍になり、裏が出たら得点は 0 になる。
- 得点が 0 になった、もしくは K 以上になった時点でゲームが終了する。このとき、得点が K 以上である場合すぬけ君の勝ち、 0 である場合すぬけ君の負けである。
N と K が与えられるので、このゲームですぬけ君が勝つ確率を求めてください。
制約
- 1 ≤ N ≤ 10^5
- 1 ≤ K ≤ 10^5
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K
出力
すぬけ君が勝つ確率を出力せよ。絶対誤差または相対誤差が 10^{-9} 以下のとき正解とみなされる。
入力例 1
3 10
出力例 1
0.145833333333
- サイコロの出た目が 1 のとき、得点が 10 以上になるためには、 4 回コインを振って 4 連続で表が出る必要があります。この確率は、 \frac{1}{3} \times (\frac{1}{2})^4 = \frac{1}{48} です。
- サイコロの出た目が 2 のとき、得点が 10 以上になるためには、 3 回コインを振って 3 連続で表が出る必要があります。この確率は、 \frac{1}{3} \times (\frac{1}{2})^3 = \frac{1}{24} です。
- サイコロの出た目が 3 のとき、得点が 10 以上になるためには、 2 回コインを振って 2 連続で表が出る必要があります。この確率は、 \frac{1}{3} \times (\frac{1}{2})^2 = \frac{1}{12} です。
よって、すぬけ君が勝つ確率は、 \frac{1}{48} + \frac{1}{24} + \frac{1}{12} = \frac{7}{48} \simeq 0.1458333333 です。
入力例 2
100000 5
出力例 2
0.999973749998
Score : 300 points
Problem Statement
Snuke has a fair N-sided die that shows the integers from 1 to N with equal probability and a fair coin. He will play the following game with them:
- Throw the die. The current score is the result of the die.
- As long as the score is between 1 and K-1 (inclusive), keep flipping the coin. The score is doubled each time the coin lands heads up, and the score becomes 0 if the coin lands tails up.
- The game ends when the score becomes 0 or becomes K or above. Snuke wins if the score is K or above, and loses if the score is 0.
You are given N and K. Find the probability that Snuke wins the game.
Constraints
- 1 ≤ N ≤ 10^5
- 1 ≤ K ≤ 10^5
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K
Output
Print the probability that Snuke wins the game. The output is considered correct when the absolute or relative error is at most 10^{-9}.
Sample Input 1
3 10
Sample Output 1
0.145833333333
- If the die shows 1, Snuke needs to get four consecutive heads from four coin flips to obtain a score of 10 or above. The probability of this happening is \frac{1}{3} \times (\frac{1}{2})^4 = \frac{1}{48}.
- If the die shows 2, Snuke needs to get three consecutive heads from three coin flips to obtain a score of 10 or above. The probability of this happening is \frac{1}{3} \times (\frac{1}{2})^3 = \frac{1}{24}.
- If the die shows 3, Snuke needs to get two consecutive heads from two coin flips to obtain a score of 10 or above. The probability of this happening is \frac{1}{3} \times (\frac{1}{2})^2 = \frac{1}{12}.
Thus, the probability that Snuke wins is \frac{1}{48} + \frac{1}{24} + \frac{1}{12} = \frac{7}{48} \simeq 0.1458333333.
Sample Input 2
100000 5
Sample Output 2
0.999973749998
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
N 頂点の木があります。 この木の i 番目の辺は頂点 u_i と頂点 v_i を結んでおり、その長さは w_i です。 あなたは以下の条件を満たすように、この木の頂点を白と黒の 2 色で塗り分けたいです (すべての頂点を同じ色で塗っても構いません)。
- 同じ色に塗られた任意の 2 頂点について、その距離が偶数である。
条件を満たす塗り分け方を 1 つ見つけて出力してください。この問題の制約下では、そのような塗り分け方が必ず 1 つは存在することが証明できます。
制約
- 入力は全て整数である。
- 1 \leq N \leq 10^5
- 1 \leq u_i < v_i \leq N
- 1 \leq w_i \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
N u_1 v_1 w_1 u_2 v_2 w_2 . . . u_{N - 1} v_{N - 1} w_{N - 1}
出力
題意の条件を満たすような頂点の塗り分け方を N 行に分けて出力せよ。
i 行目には、頂点 i を白く塗る場合は 0
を、黒く塗る場合は 1
を出力せよ。
条件を満たす塗り分け方が複数存在する場合、どれを出力してもよい。
入力例 1
3 1 2 2 2 3 1
出力例 1
0 0 1
入力例 2
5 2 5 2 2 3 10 1 3 8 3 4 2
出力例 2
1 0 1 0 1
Score : 400 points
Problem Statement
We have a tree with N vertices numbered 1 to N. The i-th edge in the tree connects Vertex u_i and Vertex v_i, and its length is w_i. Your objective is to paint each vertex in the tree white or black (it is fine to paint all vertices the same color) so that the following condition is satisfied:
- For any two vertices painted in the same color, the distance between them is an even number.
Find a coloring of the vertices that satisfies the condition and print it. It can be proved that at least one such coloring exists under the constraints of this problem.
Constraints
- All values in input are integers.
- 1 \leq N \leq 10^5
- 1 \leq u_i < v_i \leq N
- 1 \leq w_i \leq 10^9
Input
Input is given from Standard Input in the following format:
N u_1 v_1 w_1 u_2 v_2 w_2 . . . u_{N - 1} v_{N - 1} w_{N - 1}
Output
Print a coloring of the vertices that satisfies the condition, in N lines.
The i-th line should contain 0
if Vertex i is painted white and 1
if it is painted black.
If there are multiple colorings that satisfy the condition, any of them will be accepted.
Sample Input 1
3 1 2 2 2 3 1
Sample Output 1
0 0 1
Sample Input 2
5 2 5 2 2 3 10 1 3 8 3 4 2
Sample Output 2
1 0 1 0 1
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 枚のカードが一列に伏せられており、各カードには整数 1 または 2 が書かれています。
i 番目のカードに書かれている整数を A_i とします。
あなたの目的は A_1, A_2, ..., A_N を当てることです。
次のことが分かっています。
- i = 1, 2, ..., M について A_{X_i} + A_{Y_i} + Z_i は偶数である。
あなたは魔法使いです。次の魔法を何度でも使うことができます。
魔法: コストを 1 払う。カードを 1 枚選び、そのカードに書かれた整数 A_i を知る。
最小で何コスト払えば、A_1, A_2, ..., A_N 全てを確実に当てることができるでしょうか。
なお、与えられる入力には矛盾がないことが保証されます。
制約
- 入力は全て整数である。
- 2 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 1 \leq X_i < Y_i \leq N
- 1 \leq Z_i \leq 100
- (X_i, Y_i) の組は互いに異なる。
- 与えられる入力には矛盾がない(すなわち、条件を満たす A_1, A_2, ..., A_N が存在する)。
入力
入力は以下の形式で標準入力から与えられる。
N M X_1 Y_1 Z_1 X_2 Y_2 Z_2 \vdots X_M Y_M Z_M
出力
A_1, A_2, ..., A_N 全てを確実に当てるために払う必要のあるコストの合計の最小値を出力せよ。
入力例 1
3 1 1 2 1
出力例 1
2
1 枚目と 3 枚目のカードに対してそれぞれ 1 回ずつ魔法を使えば、A_1, A_2, A_3 全てを当てることができます。
入力例 2
6 5 1 2 1 2 3 2 1 3 3 4 5 4 5 6 5
出力例 2
2
入力例 3
100000 1 1 100000 100
出力例 3
99999
Score : 500 points
Problem Statement
There are N cards placed face down in a row. On each card, an integer 1 or 2 is written.
Let A_i be the integer written on the i-th card.
Your objective is to guess A_1, A_2, ..., A_N correctly.
You know the following facts:
- For each i = 1, 2, ..., M, the value A_{X_i} + A_{Y_i} + Z_i is an even number.
You are a magician and can use the following magic any number of times:
Magic: Choose one card and know the integer A_i written on it. The cost of using this magic is 1.
What is the minimum cost required to determine all of A_1, A_2, ..., A_N?
It is guaranteed that there is no contradiction in given input.
Constraints
- All values in input are integers.
- 2 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 1 \leq X_i < Y_i \leq N
- 1 \leq Z_i \leq 100
- The pairs (X_i, Y_i) are distinct.
- There is no contradiction in input. (That is, there exist integers A_1, A_2, ..., A_N that satisfy the conditions.)
Input
Input is given from Standard Input in the following format:
N M X_1 Y_1 Z_1 X_2 Y_2 Z_2 \vdots X_M Y_M Z_M
Output
Print the minimum total cost required to determine all of A_1, A_2, ..., A_N.
Sample Input 1
3 1 1 2 1
Sample Output 1
2
You can determine all of A_1, A_2, A_3 by using the magic for the first and third cards.
Sample Input 2
6 5 1 2 1 2 3 2 1 3 3 4 5 4 5 6 5
Sample Output 2
2
Sample Input 3
100000 1 1 100000 100
Sample Output 3
99999
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
以下の条件を満たす、長さ 2^{M + 1} の数列 a = {a_1,\ a_2,\ ...,\ a_{2^{M + 1}}} を、存在するならば 1 つ構築してください。
- a は 0 以上 2^M 未満の整数を、それぞれちょうど 2 つずつ含む。
- a_i = a_j を満たす任意の i,\ j \ (i < j) について、a_i \ xor \ a_{i + 1} \ xor \ ... \ xor \ a_j = K である。
xor (排他的論理和) とは
整数 c_1, c_2, ..., c_n の xor は以下のように定義されます。
- c_1 \ xor \ c_2 \ xor \ ... \ xor \ c_n を二進表記した際の 2^k (k \geq 0) の位の数は、c_1, c_2, ..., c_n のうち二進表記した際の 2^k の位の数が 1 となるものが奇数個ならば 1、偶数個ならば 0 である。
例えば、3 \ xor \ 5 = 6 です (二進表記すると: 011
xor 101
= 110
です)。
制約
- 入力は全て整数である。
- 0 \leq M \leq 17
- 0 \leq K \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
M K
出力
条件を満たす数列 a が存在しなければ -1
を出力せよ。
存在するならば、a の要素を空白区切りで出力せよ。
条件を満たす数列が複数存在する場合、どれを出力してもよい。
入力例 1
1 0
出力例 1
0 0 1 1
このケースでは、条件を満たす数列は複数存在します。
例えば a = {0, 0, 1, 1} の場合、a_i = a_j を満たす (i,\ j)\ (i < j) として (1, 2) と (3, 4) があります。a_1 \ xor \ a_2 = 0,\ a_3 \ xor \ a_4 = 0 であるため、この a は与えられた条件を満たしています。
入力例 2
1 1
出力例 2
-1
条件を満たす数列は存在しません。
入力例 3
5 58
出力例 3
-1
条件を満たす数列は存在しません。
Score : 600 points
Problem Statement
Construct a sequence a = {a_1,\ a_2,\ ...,\ a_{2^{M + 1}}} of length 2^{M + 1} that satisfies the following conditions, if such a sequence exists.
- Each integer between 0 and 2^M - 1 (inclusive) occurs twice in a.
- For any i and j (i < j) such that a_i = a_j, the formula a_i \ xor \ a_{i + 1} \ xor \ ... \ xor \ a_j = K holds.
What is xor (bitwise exclusive or)?
The xor of integers c_1, c_2, ..., c_n is defined as follows:
- When c_1 \ xor \ c_2 \ xor \ ... \ xor \ c_n is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if the number of integers among c_1, c_2, ...c_m whose binary representations have 1 in the 2^k's place is odd, and 0 if that count is even.
For example, 3 \ xor \ 5 = 6. (If we write it in base two: 011
xor 101
= 110
.)
Constraints
- All values in input are integers.
- 0 \leq M \leq 17
- 0 \leq K \leq 10^9
Input
Input is given from Standard Input in the following format:
M K
Output
If there is no sequence a that satisfies the condition, print -1
.
If there exists such a sequence a, print the elements of one such sequence a with spaces in between.
If there are multiple sequences that satisfies the condition, any of them will be accepted.
Sample Input 1
1 0
Sample Output 1
0 0 1 1
For this case, there are multiple sequences that satisfy the condition.
For example, when a = {0, 0, 1, 1}, there are two pairs (i,\ j)\ (i < j) such that a_i = a_j: (1, 2) and (3, 4). Since a_1 \ xor \ a_2 = 0 and a_3 \ xor \ a_4 = 0, this sequence a satisfies the condition.
Sample Input 2
1 1
Sample Output 2
-1
No sequence satisfies the condition.
Sample Input 3
5 58
Sample Output 3
-1
No sequence satisfies the condition.