Friday, March 25, 2011


Problem Links:

poj2505, uva00847,


  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 p$ \ge$n.

Input and Output 

Each line of input contains one integer number n. For each line of input output one line either
Stan wins.
Ollie wins.
assuming that both of them play perfectly.

Sample input 


Sample Output 

Stan wins.
Ollie wins.
Stan wins.

Miguel Revilla 2002-06-15


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.


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("", "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;
            cout << "Ollie wins." << endl;
    return 0;

No comments :