A. Domino on Windowsill
Solution:
Place the domino upright in vertical is fine. Then place in horizontal for the extra part.
Code:
B. Binary Removals
Solution:
Enumerate the position of the last 0. Then try to match the requirement. If all positions failed, then return "No".
There are two special cases:
- All numbers are 1. For this case, the position of last 0 should be -1.
- All numbers are 0. For this case, the position of last 0 should be $|s|$
Code:
C. Minimum Grid Path
Solution:
Because there is no difference in the direction of the first step. So we let the first step is to the right.
So we can find that: the even segments are to right, and odd segments are to up. It's greedy. The length of segments with minimal $c_i$ as longer as possible.
It can be seen as a DP problem. But after compress state, it not a really DP problem. $$dp[i]=(\sum_{j=0}^{i}c_j)+(\min\limits_{0<j<=i,j\%2=0}{c_j})\times{times_0}+(\min\limits_{0<j<=i,j\%2=1}{c_j})\times{times_1}$$
$times$ represent the remaining length after all the $c$ move only one step for the current direction. And assign this remaining length to the minimal $c$ to each direction.
Code:
D. The Number of Pairs
Solution:
First of all, we should know that: $lcm(a,b)=gcd(a,b)\times{f}$.
So immediately transform the original condition to get: $$c \cdot f \cdot gcd(a, b)-d \cdot gcd(a, b) = x$$
Of course $gcd(a,b)\neq 0$, So:$$c \cdot f - d = \frac x {gcd(a,b)}$$
It's very clear now.
Enumerate this $gcd(a,b)$. Calculate corresponding $f$. And base on the number of prime factors of $\frac f {gcd(a,b)}$ (Let's call it $count$). Now we can get the number of all possibilities, which is $2^{count}$.
Finally, it should be noted that this problem needs to preprocess out the $count$. Otherwise, will get TLE.
Code:
