Задача.
Есть строка из символов X или O. X означает, что место занято, O - пусто. Есть еще число К. Двое игроков могут по очереди вычеркивать ровно K идущих подряд пустых мест, то есть K подряд идущих символов O. Кто ничего не может вычеркнуть тот проиграл, определить кто выиграет. Программе дается число K и сама строка.
я решил данную задачу с помощью теории игр Шпрага-Гранди, но хотелось бы посмотреть как можно решить ее другими способами, а также найти где ее можно сдать.
Вот мой исходный код на с++:
#include <iostream>
using namespace std;
#define Max 50
int main()
{
freopen("input.txt", "r", stdin);
freopen("OUTPUT.txt", "w", stdout);
int a[Max]; //храним значение функции шпрага-гранди
int k;
char b[Max];
cin>>k;
cin>>b;
memset(a,0,Max*sizeof(int));
for(int i=k; i<Max; i++)
{
int b[Max];
memset(b,0,Max*sizeof(int));
for(int j=0; j<=i-k; j++)
{
b[a[j]^a[i-j-k]]=1;
}
int l=0;
while(b[l]!=0) l++;
a[i]=l;
}
int i=0;
int ans=2;
while(b[i]>0)
{
int l=i;
while(b[l]=='O' && b[l]>0) l++;
ans^=a[l-i];
i=l;
while(b[i]=='X') i++;
}
if(ans!=0) ans=1;
cout<<ans;
}Добавлено (26.11.2012, 16:59)
---------------------------------------------
вместо ans=2 нужно написать ans=0;