v 0. Pasted by slipstak2 as cpp at 2010-11-29 17:18:06 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 <vector>
  8. #include <algorithm>
  9.  
  10. using namespace std;
  11.  
  12. int n;
  13. void input()
  14. {
  15.     cin>>n;
  16. }
  17. long long maxValue = 4294967295;
  18. vector<long long> mas;
  19. void findMas()
  20. {
  21.     mas.push_back(1);
  22.     vector<long long>::iterator iter;
  23.     for (int i=0;i<mas.size();i++)
  24.     {
  25.         for (int j=2;j<=9;j++)
  26.         {
  27.             long long curValue = mas[i] * j;
  28.             if (curValue < maxValue)
  29.             {
  30.                 iter = lower_bound(mas.begin(),mas.end(),curValue);
  31.                 if (iter == mas.end() || *iter != curValue)
  32.                     mas.insert(iter,curValue);             
  33.             }
  34.         }
  35.     }   
  36. }
  37.  
  38. void solve()
  39. {
  40.     findMas();
  41.     vector<bool> isWin(mas.size());
  42.     vector<long long>::iterator iter;
  43.     for (int i = mas.size()-1;i>=0;i--)
  44.     {
  45.         bool isCurWin = false;
  46.         for (int j=2;j<=9;j++)
  47.         {
  48.             long long curValue = mas[i] * j;
  49.             if (curValue >=n)
  50.             {
  51.                 isCurWin = true;
  52.                 break;
  53.             }
  54.             iter = lower_bound(mas.begin(),mas.end(),curValue);
  55.             if (iter != mas.end() && *iter == curValue)
  56.             {
  57.                 int index = iter - mas.begin();
  58.                 if (!isWin[index])
  59.                 {
  60.                     isCurWin = true;
  61.                     break;
  62.                 }               
  63.             }
  64.         }
  65.         isWin[i] = isCurWin;
  66.     }
  67.     if (isWin[0])
  68.         cout<<"Stan wins.";
  69.     else
  70.         cout<<"Ollie wins.";
  71. }
  72. int main()
  73. {
  74.     freopen("input.txt","r",stdin);
  75.     freopen("output.txt","w",stdout);
  76.    
  77.     input();
  78.     solve();
  79.     return 0;
  80. }


Editing is locked.