UVa_00847_A_Multiplication_Game.cpp

Problem Links:

poj2505, uva00847,

Problem:

A multiplication game

Stan and Ollie play the game of multiplication by multiplying an integer p by one of the numbers 2 to 9. Stan always starts with p = 1, does his multiplication, then Ollie multiplies the number, then Stan and so on. Before a game starts, they draw an integer 1 < n < 4294967295 and the winner is who first reaches pn.

Input and Output 

Each line of input contains one integer number n. For each line of input output one line either

Stan wins.

or

Ollie wins.

assuming that both of them play perfectly.

Sample input 

162
17
34012226

Sample Output 

Stan wins.
Ollie wins.
Stan wins.

---

Miguel Revilla 2002-06-15

Solution:

We can easily observe that if the drawn number is in range [2, 9], Stan will win, and if it is in range [10, 18], Ollie will win. Suppose that one of Span's win range is [m, n], it can be extend to the next win range of [2*m+1, 2*9*n)]. Thus, the range width expands by a factor of 18. Then we can reduce the drawn number to the initial win ranges to check who will win the game.

Link: http://blog.csdn.net/liukaipeng/archive/2008/11/24/3363601.aspx

Source Code:

//Fri Mar 25 16:21:13 CDT 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int main(int argc, char* argv[])
{
    //freopen("input.in", "r", stdin);
    //freopen("output.out", "w", stdout);
    int n;
    while (cin >> n)
    {
        int p = 1;
        for (; p < n; p *= 18);
        if (p >= 2 * n)
            cout << "Stan wins." << endl;
        else
            cout << "Ollie wins." << endl;
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}