|
Задача по информатике
|
|
|
DEAL | Дата: Понедельник, 26.11.2012, 16:59 | Сообщение # 1 |
DEAL
Ранг: Дошколенок (?)
Группа: Зарегистрированные
|
| Сообщений: |
1 |
| Награды: |
0 |
| Статус: |
Offline |
|
Задача.
Есть строка из символов 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;
26.11.2012
|
|
|
|
| |
|
|
tjulen | Дата: Вторник, 27.11.2012, 21:25 | Сообщение # 2 |
tjulen
Ранг: Первоклашка (?)
Группа: Пользователи
|
| Сообщений: |
35 |
| Награды: |
1 |
| Статус: |
Offline |
|
Если вычеркнуть K символов из последовательности O, то станут ли оставшиеся непрерывной последовательностью?
Тогда:
1. посчитать количество непрерывных последовательностей - это бесконечно просто!!!
2. если количество четное то победит второй, иначе -первый.
27.11.2012
Сообщение отредактировал tjulen - Вторник, 27.11.2012, 21:30
|
|
|
|
| |
|
|
TRUE_GEEK | Дата: Среда, 28.11.2012, 22:28 | Сообщение # 3 |
| Сообщений: |
57 |
| Награды: |
0 |
| Статус: |
Offline |
|
Quote (tjulen) 1. посчитать количество непрерывных последовательностей - это бесконечно просто!!!
А если элементов в последовательности >=2K или <K ?
Для каждой последовательности нужно посчитать сколько раз из ней можно вычеркнуть K символов(поделить нацело кол-во элементов последовательности на k), и сложить, это и будет число ходов и тогда уже:
Quote (tjulen) 2. если количество четное то победит второй, иначе -первый.
На вскидку будет примерно так:
while(str[i])
{
j=i;
while(str[j]=='O')++j;
step+=(j-i)/K;
while(str[j]=='X')++j;
i=j;
}
if(step%2)printf("1\n");
else printf("2\n");
28.11.2012
|
|
|
|
| |
|
|
tjulen | Дата: Суббота, 01.12.2012, 06:28 | Сообщение # 4 |
tjulen
Ранг: Первоклашка (?)
Группа: Пользователи
|
| Сообщений: |
35 |
| Награды: |
1 |
| Статус: |
Offline |
|
Quote (TRUE_GEEK) Для каждой последовательности нужно посчитать сколько раз из ней можно вычеркнуть K символов(поделить нацело кол-во элементов последовательности на k), и сложить, это и будет число ходов и тогда уже
Да, действительно так.
01.12.2012
|
|
|
|
| |
|
|
diman-mik | Дата: Суббота, 01.12.2012, 18:36 | Сообщение # 5 |
diman-mik
Ранг: Дошколенок (?)
Группа: Зарегистрированные
|
| Сообщений: |
1 |
| Награды: |
0 |
| Статус: |
Offline |
|
Всем доброго дня дорогие форумчане, помогите пожалуйста решить задачу по информатике.
Нужно нарисовать блок схему и написать программу в VBA, надеюсь на вашу помощь.
http://s018.radikal.ru/i511/1212/68/608225c78235.jpg
01.12.2012
|
|
|
|
| |
|
|
lenka123 | Дата: Понедельник, 03.12.2012, 21:16 | Сообщение # 6 |
lenka123
Ранг: Дошколенок (?)
Группа: Зарегистрированные
|
| Сообщений: |
1 |
| Награды: |
0 |
| Статус: |
Offline |
|
Здравствуйте. Помогите, пожалуйста, с задачами.
Я думаю, для вас их решения не составят труда.
Заранее благодарен.
http://pixs.ru/showimage/Bezimeni1j_3135587_6478980.jpg
03.12.2012
|
|
|
|
| |
|
