POJ2505 A multiplication game

2015.01.13 10:30 Tue| 0 visits oi_2015| 2015_刷题日常| Text

Solution

当年的打表题 23333。

又是 CE 了一次 233333。

可以用有向无环图的核来解释:如果一个节点的数值不小于 n,当然先手必败。能达到这一状态的必胜态节点数值在 $\lceil {n \over 9} \rceil$ 与 $n - 1$ 之间,能转移到必胜态的必败态节点数值又在 $\lceil {\lceil {n \over 9} \rceil \over 2 } \rceil $ 与 $\lceil {n \over 9} \rceil - 1$ 之间…… 由此规律显然~

Code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

double n;

int main()
{
    while(cin >> n)
    {
        while (n > 18) n = ceil(n / 18);
        if (n > 9) puts("Ollie wins.");
        else puts("Stan wins.");
    }
}