## C - Dice and Coin

### 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:

1. Throw the die. The current score is the result of the die.
2. 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.
3. 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 Output 1

• 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}×(\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}×(\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}×(\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}≃0.1458333333$$.

Show code

## D - Even Relation

### Problem Statement

We have a tree with $$N$$ vertices numbered $$1$$ to $$N$$. The $$i$$-th edge in the tree connects Vertex ui 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≤N≤10^5$$
• $$1≤u_i<v_i≤N$$
• $$1≤w_i≤10^9$$

### Input

Input is given from Standard Input in the following format:

$$\begin{matrix} N\\ u_1&v_1&w_1\\ u_2&v_2&w_2\\ \vdots\\ u_{N-1}&v_{N-1}&w_{N-1} \end{matrix}$$

### 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.

Show code

## E - 1 or 2

### 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≤N≤10^5$$
• $$1≤M≤10^5$$
• $$1≤X_i<Y_i≤N$$
• $$1≤Z_i≤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:

$$\begin{matrix} N&M\\ X_1&Y_1&Z_1\\ X_2&Y_2&Z_2\\ \vdots\\ X_M&Y_M&Z_M \end{matrix}$$

### Output

Print the minimum total cost required to determine all of $$A_1,A_2,...,A_N$$.

### Sample Output 1

You can determine all of $$A_1,A_2,A_3$$ by using the magic for the first and third cards.

Show code

## F - XOR Matching

### 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≥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≤M≤17$$
• $$0≤K≤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 Output 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 Output 2

No sequence satisfies the condition.

### Sample Output 3

No sequence satisfies the condition.

### 解题思路

$\forall k\in\mathbb{N}^+,\bigoplus_{i=0}^{2^k-1}i=0$

• $$K\geqslant 2^M$$, 则一定无解

• $$M=1$$, 则 $$K=0$$ 有解，$$K=1$$ 无解

• 其余情况我们可以这样构造

0 1 ... K-1 K+1 ... 2^M-2 2^M-1 K 2^M-1 2^M-2 ... K+1 K-1 ... 1 0 K

Show code