Решение: Нека си представим следната подзадача




ИмеРешение: Нека си представим следната подзадача
Дата на преобразуване17.01.2013
Размер36.87 Kb.
ТипРешение
източникhttp://infoman.musala.com/magazine/archive/issue22/game.rtf
Балканска олимпиада по информатика 2002

Ден 2, Задача 1 - Игра


Двама играчи играят, вземайки последователно камъчета от купчинка. Купчинката съдържа N камъчета. Играчът, който вземе последното камъче, е победител. Правилата на играта са следните:


Играчът, който започва пръв, може да вземе произволен брой камъчета L1, но не и цялата куп­­­чинка, т.е. 1 <= L1 <= N–1. След това, играчите един след друг, вземат от купчинката едно или повече камъчета, но не повече от удвоения брой на камъчетата, взети от предишния играч. Така играчът, който е наред, може да вземе L2 камъчета, където

1 <= L2 <= 2*L1, (L1 е броят на камъчетата, взети от предишния играч).


Напишете програма, която да играе срещу компютъра и да победи. При подходяща стратегия от ваша страна и ако сте пръв, вие винаги може да победите.


Отначало трябва да прочетете от файла c:\day2\problem1\game.in броя N на камъчетата в купчинката. След това, трябва да определите броя L1 на камъчетата, които ще вземете. С тези две стойности вие трябва да извикате процедурата move(N1,L1,N2,L2), която ще върне други две стойности: броя N2 на камъчетата, които остават в купчинката след вашия ход (очевидно N2=N1–L1) и броя L2 на камъчетата, които взема компютърът. При първото извикване на процедурата move имаме N1=N.


След това, трябва да определите следващото количество камъчета L1, което вземате и новата стойност на N1, (N1=N2–L2), да извикате процедурата move, и т.н.


Вашата програма ще завърши, когато купчинката стане празна. Играчът, който вземе последното камъче, е победител.


Пример


N=10


Ваш ход Ход на компютъра


N1 L1 N2 L2

10 2 8 1

7 2 5 1

4 1 3 1

2 2 0


Поздравления! Вие победихте!


Забележка. Внимавайте вашата програма да спазва правилата на играта. В случай, че извършите непозволен ход, програмата ви автоматично ще бъде прекъсната. Процедурата move следи вашите ходове. Ако стратегията ви не е оптимална, компютърът ще победи.


РЕШЕНИЕ:


Нека си представим следната подзадача:

В момента единият играч е на ход. Остават му K топчета. Преди него е игран ход с взимане L топчета. Пита се дали е възможно играчът който е на ход да спечели играта при правилна стратегия.

Забелязваме, че има една стойност M(K) за която при L >= M(K) играчът който е на ход печели, а при L
Очевидно М(1) = 1.

Ето как намираме M(K) при К>1:

Проверяваме за всички числа J от 1 до K-1, дали ако вземем J топчета ще доведем противника в губеща позиция – те.е дали M(K-J) > J. И така докато намерим число J, за което M(K-J)>J. Тогава J е нашият печеливш ход в тази ситуация. Ще отбелязваме този печеливш ход със S(K). Тогава M(K)=(S(K)+1)/2 (цялата му част), т.к. според правилата на играта, за да караме S(K) трябва предишния хода е поне S(K)/2 (закръглено нагоре), което е равно на (S(K)+1)/2 закръглено надолу.


В решението по-долу бележим:

how[i] = M(K)

which[i] = S(K)

В първата част построяваме масивите how и which от 1 до N, а във втората част само играем which[n] при останали n числа.


По-подробен анализ на задачата ще ви доведе до извода, че когато N е от редицата на Фибоначи , започваща с 1 и 2, то играта не може да бъде спечелена, а в останалите случаи – може, но в интерес на истината това не ви е необходимо за решаването на задачата...:)


Велин Цанов

Свързани:

Решение: Нека си представим следната подзадача iconВяра регионален месечник
Нека се радваме на пролетната красота, нека сърцата ни са отворени и пълни с добрини за всеки, нека усмивките ни са истински, нека...
Решение: Нека си представим следната подзадача iconНов български университет департамент Информатика XVIII републиканска студентска олимпиада по програмиране 13 14 май 2006 г
В дискретната математика също се дефинират функции, изследват се техните свойства и те намират приложение в други области на информатиката....
Решение: Нека си представим следната подзадача iconОтворете си Библиите. Нека да влезем в ценното Слово на Господаря. Не обичате ли да Му служите?
Слово на Господаря. Не обичате ли да Му служите? Каква привилегия е за нас! Скъпи Исусе, помажи Своите хора да приемат и да получат...
Решение: Нека си представим следната подзадача iconБългарска православна църковна община
Тази светла радост е за всички и всеки трябва да бъде в празнично настроение. Но нека не празнуваме този ден по светски, а божествено;...
Решение: Нека си представим следната подзадача iconКоледно тържество
И нека лудува студеният вятър, и нека фъртуна фучи под бялата дреха се топли земята и житното зрънце мълчи
Решение: Нека си представим следната подзадача iconДнес, Татко, дай ни истина, знание, откровение, в името на Исус. Нека да хванем помазанието! Нека радостта в нас така да се умножи, че да достигнем нови
Исус. Нека да хванем помазанието! Нека радостта в нас така да се умножи, че да достигнем нови височини заради помазанието. Помажи...
Решение: Нека си представим следната подзадача iconД-р. Джордж Д. Ворис разработка на посланието към евреите
А. Ст. 1 "Поради това, нека оставим първоначалното учение за Христа и нека се стремим към съвършенство."
Решение: Нека си представим следната подзадача iconСедем ключа за помазанието Сега Татко, когато уча, нека помазанието Ти слезе със сила! Нека хората да схванат истината, която ще споделим днес, в името на Исус

Решение: Нека си представим следната подзадача iconГлобалната манипулация кратък анализ
Първо нека кажа за всички, които напуснаха този свят в резултат на случилото се в Ню Йорк, Вашингтон и Питсбърг на 11 септември Мир...
Решение: Нека си представим следната подзадача icon555 Писмо от Г. Делчев до М. Герджиков
Струмичката чета нека приеме моите сърдечни поздрави и нека ме не чака, а да слиза во полето и да работи онова, което й се предпише...
Поставете бутон на вашия сайт:
Документация


Базата данни е защитена от авторски права ©bgconv.com 2012
прилага по отношение на администрацията
Документация
Дом