## Friday, March 25, 2011

### UVa_00847_A_Multiplication_Game.cpp

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 n.

## 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.

```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.

## 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;
}