Решение задачи Игра умножения с Меньшиков

Без пояснения   Просмотров: 52


Слава и Оля играют в игру умножения - умножают целое число P на одно из чисел от 2 до 9. Слава всегда начинает с P = 1, делает умножение, затем число умножает Оля, затем Слава и т.д. Перед началом игры им задают случайное число N, и победителем считается тот, кто первым получит P >= N. Определить, кто выиграет при заданном N, если оба играют наилучшим образом.


Код

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

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться