v 0. Pasted by slipstak2 as cpp at 2010-11-29 17:09:31 MSK and set expiration to never.

Paste will expire never.

  1. // Меньшиков. Тренировка 7.
  2. // 7C. Игра умножения [multgame]
  3. // ДП с запоминанием, использующим map. Доступ к ответу решенной подзадачи за O(logN)
  4. // ibelyaev: 25Nov2010
  5. #include <iostream>
  6. #include <cstdio>
  7. #include <map>
  8.  
  9. using namespace std;
  10.  
  11. int n;
  12. void input()
  13. {
  14.     cin>>n;
  15. }
  16. map<long long, short> memIsWin;
  17. //  1 - win
  18. // -1 - not win
  19. short isWin(long long value)
  20. {
  21.     if (memIsWin[value] != 0)
  22.         return memIsWin[value];
  23.     short isCurWin = -1;
  24.     for (int i=2;i<=9;i++)
  25.     {
  26.         if (value * i >= n || isWin(value*i) == -1)
  27.         {
  28.             isCurWin = 1;
  29.             break;
  30.         }
  31.     }
  32.     memIsWin[value] = isCurWin;
  33.     return isCurWin;
  34. }
  35. void solve()
  36. {
  37.     if (isWin(1) == 1)
  38.         cout<<"Stan wins.";
  39.     else
  40.         cout<<"Ollie wins.";
  41. }
  42. int main()
  43. {
  44.     freopen("input.txt","r",stdin);
  45.     freopen("output.txt","w",stdout);
  46.    
  47.     input();
  48.     solve();
  49.     return 0;
  50. }


Editing is locked.