Alexander Malinov



Дата16.08.2017
Размер42.38 Kb.
ТипЗадача



bul.“Alexander Malinov“ №33., Sofia, 1729, Bulgaria

academy.telerik.com







Задача 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






Поделитесь с Вашими друзьями:




База данных защищена авторским правом ©obuch.info 2020
отнасят до администрацията

    Начална страница