21 Days Training // Day 10

T1. Game

There are 2 difficulties in this problem.

1. The maximum number of N ( 10^{1000002} ) is too large so that you cannot record this number except string or bigint.
2. The operations ( get 2^k gold ) makes the problem even harder.

About ??% people may give up at this time.
However, if the porblem is too big, solve it form some small points.

Try to find the pattern when N = 0, 1, 2, … .

Table :

N	1	2	3
stat	N	N	P

Here, we denote the previous player as P, the next player as N.
In each condition, N always acts first, and then P.
Why do we use P/N rather that the 2 players ?
Because in later analysis, when we jump to these condition again, the order will change.
This notation is called P-N posiion.
For most conditions, P-N position is periodic.

For example, when N=3 , whether N get 1 or 2 gold, P can get 2 or 1 gold immediately after it and win.

However, only 3 samples cannot directly show the pattern, so continue!

N	4	5	6	7	8	9
stat	N	N	P	N	N	P

Explaination :

1. When N=4 , N can get 4 gold and directly win.
2. When N=5 , N can get 2 gold. Since when N = 3 , P wins, and after 1 action, the N becomes P.
3. When N=6 , whether N get 1, 2, 4 gold, the next pos is N pos (a.k.a current P), so this is a P-position.
4. Try to get P-N position when N=7,8,9 .

For these 9 conditions, we can see that P-N position has a period with the length of 3.
If you calculate these stats when N=10, 100, 114514, … , you can get the same conclusion.

But why ?

Here comes the proof :

1. You can notice that 2^k \equiv 1 \pmod{3} when 2 \mid k , and 2^k \equiv 2 \pmod{3} when 2 \nmid k .
2. When N=1, 2, 3 , the conclusion is right with out doubt.
3. When N \ge 4 , there are 2 possiblities :
4. When 3 \nmid N , it means that N \equiv 1 \pmod{3} or N \equiv 2 \pmod{3} . According to conclusion 1, there always exists k that satisfies 2^k \equiv 1 \pmod{3} or 2^k \equiv 2 \pmod{3} , So you can select a appropriate k to make 3 \mid N .
5. When 3 \mid N , since there is no k that satisfies 2^k \equiv 0 \pmod{3} after an operation, N must satisfies 3 \nmid N .
6. Since 3 \mid 0 is a P-position, 3 \nmid 1 and 3 \nmid 2 are N-position, 3 \mid N always connects to 3 \nmid N, and 3 \nmid N can connect to 3 \mid N, 3 \nmid N is a N-position, 3 \mid N is a P-position.

So, in this problem, we can first calculate N%3. If it is 0, the 2nd palyer wins. If it is not 0, the 1st player wins.

The core content ends here.

---

An extra problem : When N_{\max}=10^{1000002}, how can we calculate N%3.
It is extremely easy :

1. Let N=\sum_{i=0}^k a_i 10^{i} , it is also equals to N = \overline{a_ka_{k-1}…a_1a_0}
2. Directly calculate N \operatorname{mod} 3 , here , for each term a_i 10^{i} , a_i 10^{i} \equiv a_i \operatorname{mod} 3 \times 10^{i} \operatorname{mod} 3 \pmod{3} .
3. Since 10 \equiv 1 \pmod{3} , a_i 10^{i} \equiv a_i \pmod{3}
4. Therefore, N \equiv \sum_{i=0}^k a_i \pmod{3} .

So, for an extremely large N, calculate the sum of its digits, and modulo the result by 3, you can get the result.

Code :

#include <bits/stdc++.h>
using namespace std;

int main() {
    for (int i=0;i<3;i++) {
        string X;cin >> X;
        int det=0;
        for (int j=0;j<X.length();j++) det+=X[j]-&#039;0&#039;;
        if (!(det%3)) {
            cout << "King will win." << endl;
        }
        else {
            cout << "MaoLaoDa will win.";
            cout << endl << det%3 << endl;
        }
    }
    return 0;
}