Codeforces Round #730 ABCD Solutions (Java/C++)

A. Exciting Bets

Solution:

If the two numbers are the same, then obviously the answer is infinity.

If the two numbers are different, then let us represent these two numbers to a and a+x.
Let us represent the GCD after the operations to q. Then we have $a+y\equiv 0\pmod q$ and $a+y+x\equiv 0\pmod q$. So, we have $x\equiv 0\pmod q$.
So that, $q\leq x$. Because in the worst case, the two numbers can be change to 0 and x. So that the maximal GCD must be x.

So, we only need to find the multiple of x near a.

Code:

Java

C++

B. Customising the Track

Solution:

Obviously, even distribution is enough. Assuming that the remainder after uniform distribution is x, there are x roads out of n roads with 1 more car. So the final result is $x\cdot (n-x)$.

Code:

Java

C++

C. Need for Pink Slips

Solution:

Just simulation with brute force DFS. Although the input probability can have 4 decimal places, since v is at least 0.1, there are at most 10 levels of recursion.

Code:

Java

C++

D. RPD and Rap Sheet (Easy/Hard)

Solution:

First of all, we found that the XOR operation follow this rule: If $a\oplus b=c$, then $c\ominus a=b$.

Assume that the initial password is x. After several queries, the current password can actually be deduced. Let us represent the value of i-th query is $q_i$, the next password is $x_i$, then we have$$\begin{equation*}
x\oplus x_1=q_1\\
x_1\oplus x_2=q_2\\
x_2\oplus x_3=q_3\\
...\\
\end{equation*}$$

So that, we can enumerate the initial passwords sequentially from 0. And according to our assumed initial password, deduce the current password and query it.
For example 4th query, the assumed initial password is 3. So the query should be $q_3 \ominus q_2 \oplus q_1 \ominus 3$.
For example 5th query, the assumed initial password is 4. So the query should be $q_4 \ominus q_3 \oplus q_2 \ominus q_1 \oplus 4$.

Code:

Java

C++