Alexander Malinov

Диаманти

Пешляка и Гошляка имали диаманти. Двамата правят купчина от N на брой (от които един е син, а всички останали червени) и вместо да ги продават за кеш, те си цъкали някаква игричка. Подредили диамантите в редичка, като на позиция M поставили синия. Те се редуват в играта, като Пешляка винаги е пръв. На всеки ход, играча избира K последователни диаманта, един от които трябва да бъде син, и ги поставя в обратен ред.

Победител е този, който успее да сложи синия диамант в позиция L. Пешляка и Гошляка изиграват общо G на брой игри. Вашата задача е да намерите кой е победителя при използване на оптимална стратегия от двамата за всяка една от тях.

Вход

На първият ред от входа ще прочетете числото G.

На следващите G редa от входа, ще прочетете всяка една отделна игра и нейните числа N, M, K и L, разделени с интервал.

Входът на програмата ще бъде винаги валиден и в описания формат. Няма нужда да бъде проверяван изрично.

Изход

За всяка една игра трябва да изпишете “Peshlyaka”, “Goshlyaka” или “Draw” (при равенство).

Ограничения

• 
  Всички позиции в задачата започват от 1 (първа).
  
• 
  N ще бъде между 1 и 2 000 000, включително. G ще бъде между 3 и 10, включително.
  
• 
  М, К и L ще бъдат между 1 и N, включително.
  
• 
  M и L ще бъдат различни.
  
• 
  Позволено време за програмата: 0.05 секунди.
  
• 
  Позволена памет: 16 MB.
  

Пример

Вход	Изход
3 3 1 1 2 5 1 2 2 5 5 2 3	Draw Peshlyaka Goshlyaka

Telerik Software Academy 2012	of	facebook.com/TelerikAcademy

Каталог: svn -> algo-academy -> 2013-11-Cpp-Basics-and-Game-Theory -> Contest
algo-academy -> Alexander Malinov
Contest -> Alexander Malinov
algo-academy -> Alexander Malinov
algo-academy -> Alexander Malinov
algo-academy -> Alexander Malinov
algo-academy -> Alexander Malinov
algo-academy -> Alexander Malinov

Изтегляне 17.34 Kb.

Сподели с приятели: