Страница 1 из 11
Модератор форума: Екатерина_Пашкова 
Форум учителей об образовании в России и мире » Форум педагогов по предметам, разделам » Форум учителей информатики » Задача по информатике (Задача с олимпиады)
Задача по информатике
DEALДата: Понедельник, 26.11.2012, 16:59 | Сообщение # 1

Александр Девятко
Ранг: Дошколенок (?)
Группа: Зарегистрированные
Российская Федерация
Прохладный

Сообщений:
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;

Спасибо
tjulenДата: Вторник, 27.11.2012, 21:25 | Сообщение # 2

Евгений Тюленев
Ранг: Первоклашка (?)
Группа: Пользователи
Российская Федерация
Боровиха

Сообщений:
35
Награды: 1
Статус: Offline
Если вычеркнуть K символов из последовательности O, то станут ли оставшиеся непрерывной последовательностью?

Тогда:
1. посчитать количество непрерывных последовательностей - это бесконечно просто!!!
2. если количество четное то победит второй, иначе -первый.


Сообщение отредактировал 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");
Спасибо
tjulenДата: Суббота, 01.12.2012, 06:28 | Сообщение # 4

Евгений Тюленев
Ранг: Первоклашка (?)
Группа: Пользователи
Российская Федерация
Боровиха

Сообщений:
35
Награды: 1
Статус: Offline
Quote (TRUE_GEEK)
Для каждой последовательности нужно посчитать сколько раз из ней можно вычеркнуть K символов(поделить нацело кол-во элементов последовательности на k), и сложить, это и будет число ходов и тогда уже

Да, действительно так.
Спасибо
diman-mikДата: Суббота, 01.12.2012, 18:36 | Сообщение # 5

Diman-MiK Дмитрий
Ранг: Дошколенок (?)
Группа: Зарегистрированные
Российская Федерация
Новосибирск

Сообщений:
1
Награды: 0
Статус: Offline
Всем доброго дня дорогие форумчане, помогите пожалуйста решить задачу по информатике.
Нужно нарисовать блок схему и написать программу в VBA, надеюсь на вашу помощь.
http://s018.radikal.ru/i511/1212/68/608225c78235.jpg
Спасибо
lenka123Дата: Понедельник, 03.12.2012, 21:16 | Сообщение # 6

Ранг: Дошколенок (?)
Группа: Зарегистрированные
Беларусь
Minsk

Сообщений:
1
Награды: 0
Статус: Offline
Здравствуйте. Помогите, пожалуйста, с задачами.
Я думаю, для вас их решения не составят труда.
Заранее благодарен.
http://pixs.ru/showimage/Bezimeni1j_3135587_6478980.jpg
Спасибо
Форум учителей об образовании в России и мире » Форум педагогов по предметам, разделам » Форум учителей информатики » Задача по информатике (Задача с олимпиады)
Страница 1 из 11
Поиск:



Спорная ситуация с родителями или администрацией? Ищете выход из проблемы на уроке или с учеником?
Не знаете, как что-то сделать на компьютере?


Вы можете задать анонимный вопрос
х
Подробно изложите суть вашего вопроса.
Обратите внимание, что вопросы публикуются в открытом доступе не сайте, поэтому не указывайте персональные данные ваши или иных лиц. Однако стоит указать свой РЕГИОН, т.к. законодательство в разных регионах разное.
Отправить