Старая форма входа
Регистрация
Телеграм-канал учителям
Анонсы вебинаровСтатьиРазборы

Сообщество тех, кто повышает качество преподавания, интересуется психологией, применяет ИКТ и зарабатывает

Дорогие друзья!
Наш форум закрыт для общения сейчас,
но вы можете задать свой вопрос или перейти в чат Телеграм.
Пожалуйста, напишите на почту files@21vu.ru ваш вопрос, ситуацию, чтобы обратиться к коллегам в чате.
Если вы хотите просто вступить в чат, также напишите на почту, укажите сведения о себе: ФИО, кто вы, кто по профессии, чем можете быть полезны педагогам, и мы направим вас в Чат Телеграм.
  • Страница 1 из 1
  • 1
Модератор форума: Екатерина_Пашкова  
Форум учителей об образовании в России и мире » Форум педагогов по предметам, разделам » Форум учителей информатики » Задача по информатике (Задача с олимпиады)
Задача по информатике
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
TRUE_GEEK

Иван Павлов
Ранг: Школьник (?)
Группа: Пользователи
Сообщений:
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

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
Форум учителей об образовании в России и мире » Форум педагогов по предметам, разделам » Форум учителей информатики » Задача по информатике (Задача с олимпиады)
  • Страница 1 из 1
  • 1
Поиск:



Отзывы

Егорова Елена 5.0
Отзыв о товаре ША PRO Анализ техники чтения по классам
и четвертям
Хочу выразить большую благодарность от лица педагогов начальных классов гимназии «Пущино» программистам, создавшим эту замечательную программу! То, что раньше мы делали «врукопашную», теперь можно оформить в таблицу и получить анализ по каждому ученику и отчёт по классу. Великолепно, восторг! Преимущества мы оценили сразу. С начала нового учебного года будем активно пользоваться. Поэтому никаких пожеланий у нас пока нет, одни благодарности. Очень простая и понятная инструкция, что немаловажно! Благодарю Вас и Ваших коллег за этот важный труд. Очень приятно, когда коллеги понимают, как можно «упростить» работу учителя.
Наговицина Ольга Витальевна 5.0
учитель химии и биологии, СОШ с. Чапаевка, Новоорский район, Оренбургская область
Отзыв о товаре ША Шаблон Excel Анализатор результатов ОГЭ
по ХИМИИ
Спасибо, аналитическая справка замечательная получается, ОГЭ химия и биология. Очень облегчило аналитическую работу, выявляются узкие места в подготовке к экзамену. Нагрузка у меня, как и у всех учителей большая. Ваш шаблон экономит время, своим коллегам я Ваш шаблон показала, они так же его приобрели. Спасибо.
Чазова Александра 5.0
Отзыв о товаре ША Шаблон Excel Анализатор результатов ОГЭ по
МАТЕМАТИКЕ
Очень хороший шаблон, удобен в использовании, анализ пробного тестирования занял считанные минуты. Возникли проблемы с распечаткой отчёта, но надо ещё раз разобраться. Большое спасибо за качественный анализатор.
Лосеева Татьяна Борисовна 5.0
учитель начальных классов, МБОУ СОШ №1, г. Красновишерск, Пермский край
Отзыв о товаре Изготовление сертификата или свидетельства конкурса
Большое спасибо за оперативное изготовление сертификатов! Все очень красиво. Мой ученик доволен, свой сертификат он вложил в портфолио. Обязательно продолжим с Вами сотрудничество!
Язенина Ольга Анатольевна 4.0
учитель начальных классов, ОГБОУ "Центр образования для детей с особыми образовательными потребностями г. Смоленска"
Отзыв о товаре Вебинар Как создать интересный урок:
инструменты и приемы
Я посмотрела вебинар! Осталась очень довольна полученной информацией. Всё очень чётко, без "воды". Всё, что сказано, показано, очень пригодится в практике любого педагога. И я тоже обязательно воспользуюсь полезными материалами вебинара. Спасибо большое лектору за то, что она поделилась своим опытом!
Арапханова Ашат 5.0
ША Табель посещаемости + Сводная для ДОУ ОКУД
Хотела бы поблагодарить Вас за такую помощь. Разобралась сразу же, всё очень аккуратно и оперативно. Нет ни одного недостатка. Я не пожалела, что доверилась и приобрела у вас этот табель. Благодаря Вам сэкономила время, сейчас же составляю табель для работников. Удачи и успехов Вам в дальнейшем!
Дамбаа Айсуу 5.0
Отзыв о товаре ША Шаблон Excel Анализатор результатов ЕГЭ по
РУССКОМУ ЯЗЫКУ
Спасибо огромное, очень много экономит времени, т.к. анализ уже готовый, и особенно радует, что есть варианты с сочинением, без сочинения, только анализ сочинения! Превосходно!
Спорная ситуация с родителями или администрацией? Ищете выход из проблемы на уроке или с учеником?
Не знаете, как что-то сделать на компьютере?


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