Alexander Malinov

Задача 2 – Зарове на хижа

Пенка и Евлоги решили да отидат на хижа да разпуснат малко от натовареното им ежедневие. Поради много перипетии по пътя – шосе тип „дупки с малко път“, прегорял съединител на една от колите и потенциална катастрофа с надъхан софийски джип – те закъсняли и забавленията били вече в разгара си. Тъкмо да влязат в миришещия на нафта ресторант, но една телеришка черна нинджа им препречила пътя на входа:

„О, млади падауани, за да влезете през портала към рая, трябва да докажете пред себе си, че сте достойни ловки ученици и да ме победите в древната игра на черните зарове!“ – казала нинджата с митичен и силен глас, който сякаш идвал от небесата.

Правилата на играта са следните:

1. 
   Нинджата дава един черен зар на Пенка и един на Евлоги.
   
2. 
   Заровете са многостенни (с N на брой стени общо) и числата на единия зар се допълват с числата на другия.
   
3. 
   Числата върху двата зара общо са от 1 до N включително, като всяко число се среща максимум по веднъж. Това е пример за валидни два зара: „1 5 3“ и „2 4“, а това е пример за невалидни: „1 6 2“ и „1 4“.
   
4. 
   Заровете са много по-древни, отколкото би могъл човек да предположи, затова някой от техните стени са изтрити и Пенка и Евлоги не могат да видят числата написани върху тях. Изтритата стена на зара се отбелязва с “_“ (долна черта без кавичките). Валидни зарове с изтрити стени са: „_ 5 3“ и „_ _“, както и „_ _ 3“ и „_ 4“, така и „_ _ _“ и „_ _“. Нинджата вижда всичко и навсякъде, затова тя знае на коя стена кое число отговаря, за разлика от двамата играчи.
   
5. 
   Пенка и Евлоги хвърлят двата си зара едновременно и избират една от двете стени, които им са се паднали, и го използват като брой точки. С всяко хвърляне на заровете общия им брой точки нараства, в зависимост от стената, която са избрали. Ако числото е изтрито и не се вижда, нинджата им го добавя към общия брой точки, без те да знаят крайния резултат.
   
6. 
   Нинджата назовава две случайни числа: PointsToReach – общия брой точки, които Пенка и Евлоги трябва да съберат и MaxThrows – максималния брой хвърляния, с които тези точки трябва да бъдат достигнати.
   
7. 
   Ако Пенка и Евлоги успеят да съберат нужните точки с по-малко от максималния брой хвърляния, нинджата ще ги пусне да се забавляват в ресторанта. Ако се провалят, ще ги отпрати по леглата да спят.
   

Двамата не могат да рискуват и да разчитат на случайността. Те трябва да използват оптималната стратегия, с която да контролират заровете, така че да си гарантират задължителното достигане на PointsToReach. Вашата задача е да помогнете на Пенка и Евлоги като напишете програма, с която да откриете минималния брой хвърляния на заровете, с които те си задължително ще съберат нужните точки по най-оптималния начин, имайки в предвид, че те не знаят точките на някои от стените.

Ако този минимален брой хвърляния надвишава MaxThrows нинджата ги отпраща и вие трябва да отпечатате “Sleep!” на първия ред на конзолата, а на втория - броя хвърляния, с които оптималния брой хвърляния надвишава MaxThrows.

Ако пък минималния брой хвърляния е по-малко от MaxThrows нинджата ги пуска в ресторанта и вие отпечатвате “Party!” на първия ред на конзолата, а на втория – минималния брой хвърляния.

Вход

На първия ред се прочитат числата на първия зар, разделени с интервал. Ако някое от числата е изтрито, ще се прочита “_“ (долна черта без кавичките).

На втория ред се прочитат числата на втория зар, разделени с интервал. Ако някое от числата е изтрито, ще се прочита “_“ (долна черта без кавичките).

На третия ред се прочита числото PointsToReach.

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

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

Изход

На първия ред на конзолата трябва да се отпечати “Sleep!” или “Party!” (без кавичките), в зависимост от крайния резултат.

На втория ред на конзолата трябва да се отпечати едно число - броя хвърляния, с които оптималния брой хвърляния надвишава MaxThrows или минималния брой хвърляния, в зависимост от крайния резултат.

Ограничения

• 
  N е винаги цяло число в интервала от 2 до 50, включително.
  
• 
  Всяка стена на заровете ще съдържа цяло число от 1 до N, включително.
  
• 
  Ако дадено число е изтрито и не се вижда, то ще бъде отбелязано с “_“ (долна черта без кавичките).
  
• 
  Всяко число върху стените може да се срещне само веднъж, без повтаряемост върху който и да е от заровете.
  
• 
  PointsToReach ще бъде число от 1 до 1 000 000 000, включително.
  
• 
  MaxThrows ще бъде число от 1 до 1 000 000 000, включително.
  
• 
  Разрешеното време за изпълнение на програмата е 0.2 секунди. Лимит на паметта: 16 МБ.
  

Примери

Вход	Изход
_ 3 4 _ _ 8 3	Party! 2
Оптималния брой хвърляния тук е 2. Пенка и Евлоги пускат заровете два пъти подред върху числото 4 и изкарват нужните 8 брой точки. Тъй като 2 е по-малко от максималния брой хвърляния, печатим “Party!” и минималния брой хвърляния 2.

Вход	Изход
_ _ _ _ _ 15 4	Sleep! 1
Тук Пенка и Евлоги не знаят нито едно число къде точно се намира, но знаят, че върху стените има 1, 2, 3, 4 и 5 задължително по един път. Затова оптималната стратегия е да хвърлят всяка една стена по веднъж, което гарантира събирането на 15 точки: 1 + 2 + 3 + 4 + 5. Тъй като 5 е по-голямо от максималния брой хвърляния, печатим надвишението 1.

Telerik Algo Academy 2013	of	facebook.com/TelerikAlgoAcademy

Каталог: svn -> algo-academy
algo-academy -> Alexander Malinov
algo-academy -> Alexander Malinov
algo-academy -> Alexander Malinov
algo-academy -> Alexander Malinov
algo-academy -> Alexander Malinov
algo-academy -> Alexander Malinov
algo-academy -> Alexander Malinov
algo-academy -> Alexander Malinov

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

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