Paste will expire never.
- // Меньшиков. Тренировка 7.
- // 7C. Игра умножения [multgame]
- // Одномерное ДП без map. Доступ к ответу решенной подзадаче за O(logN)
- // ibelyaev: 25Nov2010
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <algorithm>
- using namespace std;
- int n;
- void input()
- {
- cin>>n;
- }
- long long maxValue = 4294967295;
- vector<long long> mas;
- void findMas()
- {
- mas.push_back(1);
- vector<long long>::iterator iter;
- for (int i=0;i<mas.size();i++)
- {
- for (int j=2;j<=9;j++)
- {
- long long curValue = mas[i] * j;
- if (curValue < maxValue)
- {
- iter = lower_bound(mas.begin(),mas.end(),curValue);
- if (iter == mas.end() || *iter != curValue)
- mas.insert(iter,curValue);
- }
- }
- }
- }
- void solve()
- {
- findMas();
- vector<bool> isWin(mas.size());
- vector<long long>::iterator iter;
- for (int i = mas.size()-1;i>=0;i--)
- {
- bool isCurWin = false;
- for (int j=2;j<=9;j++)
- {
- long long curValue = mas[i] * j;
- if (curValue >=n)
- {
- isCurWin = true;
- break;
- }
- iter = lower_bound(mas.begin(),mas.end(),curValue);
- if (iter != mas.end() && *iter == curValue)
- {
- int index = iter - mas.begin();
- if (!isWin[index])
- {
- isCurWin = true;
- break;
- }
- }
- }
- isWin[i] = isCurWin;
- }
- if (isWin[0])
- cout<<"Stan wins.";
- else
- cout<<"Ollie wins.";
- }
- int main()
- {
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- input();
- solve();
- return 0;
- }
Editing is locked.