Задача Простая игра

@Блондинк@ · Регистрация: 16.01.2011

Студворк — интернет-сервис помощи студентам

ПРОСТАЯ ИГРА.
Дед Мазай и заяц играют в очень простую игру. Перед ними огромная куча одинаковых морковок. Каждый из них во время своего хода может взять из этой кучи любое количество морковок, равное неотрицательной степени числа 2, т.е. 1, 2, 4, 8, … Начинает игру либо Дед Мазай, либо заяц. Затем игроки ходят по очереди. Тот, кто возьмет последнюю морковку, тот и выигрывает.
Требуется написать программу, которая при заданных исходных данных определяет победителя в этой игре. При этом следует учитывать, что игроки играют оптимально.

Технические требования:
Имя входного файла: INPUT.TXT
Имя выходного файла: OUTPUT.TXT
Ограничение по времени тестирования: 2 секунды на один тест.

Формат входных данных:
Входной файл INPUT.TXT содержит единственное целое число N (N10250), задающее число морковок в начале игры.

Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать в первой строке цифру «1», если выиграет тот, кто ходит первым, или цифру «2» - в противном случае. Если игру выиграл тот, кто ходил первым, то во второй строке этого файла должно содержаться минимальное число морковок, которое должен взять игрок, выполнявший ход первым, чтобы гарантировать свою победу.

Пример файлов входных и выходных данных:
INPUT.TXT OUTPUT.TXT
8 1
2

Указания к решению.
В этой игре 2 игрока делают ходы по очереди, и выигрывает тот, кто достигает некоторой намеченной в начале игры позиции. В данной игре позиция
может быть полностью охарактеризована числом оставшихся морковок, и выигрывающая позиция соответствует числу морковок, равному нулю.
Спраг и Грюнди предложили (соответственно в 1936 и 1939 годах) связывать с каждой игровой позицией неотрицательное число следующим образом:
1) выигрывающей позиции сопоставляем 0;
2) данной игровой позиции сопоставляем наименьшее неотрицательное целое, отличающееся от чисел, связанных с позициями, которые могут быть достигнуты, исходя из данной.
Образуем числа Спрага-Грюнди (SG) для этой игры:
• позиции 0 сопоставляем число 0, т.е. SG(0)=0;
• исходя из 1, можно получить 0 (поскольку мы имеем право взять одну морковку). Следовательно, SG(1) – наименьшее неотрицательное целое число, отличное от нуля, т.е. SG(1)=1;
• исходя из 2, можно получить 0 и 1. Значит SG(2) – наименьшее неотрицательное целое число, отличное от 0 и 1, т.е. SG(2)=2;
• пусть у нас имеется 3 морковки. Можно взять 1 или 2, в результате чего останутся 2 или 1 морковка, но не 0. Число SG(3) – наименьшее неотрицательное целое число, отличное от 1 и 2, т.е. SG(3) =0;
• из 4 можно получить позиции 0, 2 или 3 (если взять соответственно 4, 2 или 1 морковку). Следовательно SG(4) – это не 0 и не 2, значит SG(4)=1;
• из 5 получаем позиции 1, 3 или 4. Значит SG(5)=2.
Установим общий закон: SG(p) есть остаток от деления p на 3.
Теперь осталось выявить стратегию (кто выигрывает) и соотнести полученный алгоритм с ограничениями на входные данные (N10250).

Контрольные тесты
INPUT.TXT OUTPUT.TXT
2733591 2
10000000000000000 1
1
100000000000000002 2
452837423623687234663 1
1

@инна_ · 10.03.2012, 17:28

мне тоже очень нужна эта задача

valeriikozlov · 10.03.2012, 22:47

Сообщение от инна_

мне тоже очень нужна эта задача

нужна для чего, если не секрет?

@инна_ · 11.03.2012, 09:43

все просто,чтобы сдать программирование

valeriikozlov · 11.03.2012, 17:54

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var
  Str: string;
  t, i:integer;
begin  
  assign(input, 'input.txt'); reset(input);
  assign(output, 'output.txt'); rewrite(output);
  read(Str);
  t:=0;
  for i:=1 to length(Str) do
    t:=t+ord(Str[i])-ord('0');
   if (t mod 3)=0 then write('2')
   else 
   begin
   writeln('1'); write(t mod 3);
   end;
end.

Новые блоги и статьи Все статьи Все блоги /
Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем	10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .	Перемещение выделенных строк ТЧ из одного документа в другой Maks 31.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .
Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .	Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .

@Блондинк@ 1 / 1 / 0 Регистрация: 16.01.2011 Сообщений: 28

	Задача Простая игра 20.02.2012, 14:06. Показов 6278. Ответов 4 Метки нет (Все метки) ПРОСТАЯ ИГРА. Дед Мазай и заяц играют в очень простую игру. Перед ними огромная куча одинаковых морковок. Каждый из них во время своего хода может взять из этой кучи любое количество морковок, равное неотрицательной степени числа 2, т.е. 1, 2, 4, 8, … Начинает игру либо Дед Мазай, либо заяц. Затем игроки ходят по очереди. Тот, кто возьмет последнюю морковку, тот и выигрывает. Требуется написать программу, которая при заданных исходных данных определяет победителя в этой игре. При этом следует учитывать, что игроки играют оптимально. Технические требования: Имя входного файла: INPUT.TXT Имя выходного файла: OUTPUT.TXT Ограничение по времени тестирования: 2 секунды на один тест. Формат входных данных: Входной файл INPUT.TXT содержит единственное целое число N (N10250), задающее число морковок в начале игры. Формат выходных данных: Выходной файл OUTPUT.TXT должен содержать в первой строке цифру «1», если выиграет тот, кто ходит первым, или цифру «2» - в противном случае. Если игру выиграл тот, кто ходил первым, то во второй строке этого файла должно содержаться минимальное число морковок, которое должен взять игрок, выполнявший ход первым, чтобы гарантировать свою победу. Пример файлов входных и выходных данных: INPUT.TXT OUTPUT.TXT 8 1 2 Указания к решению. В этой игре 2 игрока делают ходы по очереди, и выигрывает тот, кто достигает некоторой намеченной в начале игры позиции. В данной игре позиция может быть полностью охарактеризована числом оставшихся морковок, и выигрывающая позиция соответствует числу морковок, равному нулю. Спраг и Грюнди предложили (соответственно в 1936 и 1939 годах) связывать с каждой игровой позицией неотрицательное число следующим образом: 1) выигрывающей позиции сопоставляем 0; 2) данной игровой позиции сопоставляем наименьшее неотрицательное целое, отличающееся от чисел, связанных с позициями, которые могут быть достигнуты, исходя из данной. Образуем числа Спрага-Грюнди (SG) для этой игры: • позиции 0 сопоставляем число 0, т.е. SG(0)=0; • исходя из 1, можно получить 0 (поскольку мы имеем право взять одну морковку). Следовательно, SG(1) – наименьшее неотрицательное целое число, отличное от нуля, т.е. SG(1)=1; • исходя из 2, можно получить 0 и 1. Значит SG(2) – наименьшее неотрицательное целое число, отличное от 0 и 1, т.е. SG(2)=2; • пусть у нас имеется 3 морковки. Можно взять 1 или 2, в результате чего останутся 2 или 1 морковка, но не 0. Число SG(3) – наименьшее неотрицательное целое число, отличное от 1 и 2, т.е. SG(3) =0; • из 4 можно получить позиции 0, 2 или 3 (если взять соответственно 4, 2 или 1 морковку). Следовательно SG(4) – это не 0 и не 2, значит SG(4)=1; • из 5 получаем позиции 1, 3 или 4. Значит SG(5)=2. Установим общий закон: SG(p) есть остаток от деления p на 3. Теперь осталось выявить стратегию (кто выигрывает) и соотнести полученный алгоритм с ограничениями на входные данные (N10250). Контрольные тесты INPUT.TXT OUTPUT.TXT 2733591 2 10000000000000000 1 1 100000000000000002 2 452837423623687234663 1 1 1

@инна_ 3 / 3 / 0 Регистрация: 18.01.2011 Сообщений: 34
	10.03.2012, 17:28
	мне тоже очень нужна эта задача 1

@инна_ 3 / 3 / 0 Регистрация: 18.01.2011 Сообщений: 34
	11.03.2012, 09:43
	все просто,чтобы сдать программирование 1