Paste will expire never.
- // Меньшиков. Тренировка 7.
- // 7C. Игра умножения [multgame]
- // ДП с запоминанием, использующим map. Доступ к ответу решенной подзадачи за O(logN)
- // ibelyaev: 25Nov2010
- #include <iostream>
- #include <cstdio>
- #include <map>
- using namespace std;
- int n;
- void input()
- {
- cin>>n;
- }
- map<long long, short> memIsWin;
- // 1 - win
- // -1 - not win
- short isWin(long long value)
- {
- if (memIsWin[value] != 0)
- return memIsWin[value];
- short isCurWin = -1;
- for (int i=2;i<=9;i++)
- {
- if (value * i >= n || isWin(value*i) == -1)
- {
- isCurWin = 1;
- break;
- }
- }
- memIsWin[value] = isCurWin;
- return isCurWin;
- }
- void solve()
- {
- if (isWin(1) == 1)
- 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.