Глава 9.2. Задачи за шампиони – част II

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

По-сложни задачи върху изучавания материал

Преди да преминем към конкретните задачи, трябва да поясним, че те могат да се решат по-лесно с допълнителни знания за програмирането и езика JavaScript (функции, масиви, колекции, рекурсия и т.н.), но всяко едно решение, което ще дадем сега, ще използва единствено материал, покрит в тази книга. Целта е да се научите да съставяте по-сложни алгоритми на базата на сегашните си знания.

Задача: дни за страстно пазаруване

Лина има истинска страст за пазаруване. Когато тя има малко пари, веднага отива в първия голям търговски център (мол) и се опитва да изхарчи възможно най-много за дрехи, чанти и обувки. Но любимото ѝ нещо са зимните намаления. Нашата задача е да анализираме странното ѝ поведение и да изчислим покупките, които Лина прави, когато влезе в мола, както и парите, които ѝ остават, когато приключи с пазаруването си.

Първият аргумент на функцията ще бъде сумата, която Лина има преди да започне да пазарува. Вторият аргумент ще бъде списък от команди(стрингове), които Лина ще изпълни. При получаване на командата "mall.Enter", Лина влиза в мола и започва да пазарува, докато не получи командата "mall.Exit". След като Лина започне да пазарува, всеки следващ елемент от масива, ще представлява действия, които Лина изпълнява. Всеки символ в стринга представлява покупка или друго действие. Стринговите команди могат да съдържат само символи от ASCII таблицата. ASCII кода на всеки знак има връзка с това колко Лина трябва да плати за всяка стока. Интерпретирайте символите по следния начин:

• Ако символът е главна буква, Лина получава 50% намаление, което означава, че трябва да намалите парите, които тя има, с 50% от цифровата репрезентация на символа от ASCII таблицата.
• Ако символът е малка буква, Лина получава 70% намаление, което означава, че трябва да намалите парите, които тя има, с 30% от цифровата репрезентация на символа от ASCII таблицата.
• Ако символът е "%", Лина прави покупка, която намалява парите ѝ на половина.
• Ако символът е "*", Лина изтегля пари от дебитната си карта и добавя към наличните си средства 10 лева.
• Ако символът е различен от упоменатите горе, Лина просто прави покупка без намаления и в такъв случай просто извадете стойността на символа от ASCII таблицата от наличните ѝ средства.

Ако някоя от стойностите на покупките е по-голяма от текущите налични средства, Лина НЕ прави покупката. Парите на Лина не могат да бъдат по-малко от 0.

Пазаруването завършва, когато се получи командата "mall.Exit". Когато това стане, трябва да принтирате броя на извършени покупки и парите, които са останали на Лина.

Входни данни

Входните данни се подават в два аргумента. Първият ще бъде сумата, която Лина има преди да започне да пазарува. Вторият аргумент ще бъде масив от команди, който се обработва последователно. Когато получите командата "mall.Enter", всеки следващ елемент ще бъде стринг, съдържащи информация относно покупките / действията, които Лина иска да направи. В масива ще има команди, които трябва да се изпълнят, докато не се получи командата "mall.Exit".

Винаги ще се подава само една команда "mall.Enter" и само една команда "mall.Exit".

Изходни данни

Изходните данни трябва да се принтират на конзолата. Когато пазаруването приключи, на конзолата трябва да се принтира определен изход в зависимост от това какви покупки са били направени.

• Ако не са били направени някакви покупки – "No purchases. Money left: {останали пари} lv."
• Ако е направена поне една покупка - "{брой покупки} purchases. Money left: {останали пари} lv."

Парите трябва да се принтират с точност от 2 символа след десетичния знак.

Ограничения

• Парите са число с плаваща запетая в интервала: [0 - 7.9 x 10²⁸].
• Броят стрингове между "mall.Enter" и "mall.Exit" ще в интервала: [1-20].
• Броят символи във всеки стринг, който представлява команда, ще е в интервала: [1-20].
• Позволено време за изпълнение: 0.1 секунди.
• Позволена памет: 16 MB.

Примерен вход и изход

Насоки и подсказки

Ще разделим решението на задачата на три основни части:

• Обработка на входа.
• Алгоритъм на решаване.
• Форматиране на изхода.

Нека разгледаме всяка една част в детайли.

Обработване на входа

Входът за нашата задача се състои от няколко компонента:

• В първия аргумент имаме всички пари, с които Лина ще разполага за пазаруването.
• Във втория - масив ще имаме поредица от команди.

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

Вторият аргумент ще бъде масив от команди, който се обработва последователно. Когато получите командата "mall.Enter", всеки следващ елемент ще бъде стринг, съдържащи информация относно покупките / действията, които Лина иска да направи.

Тук е моментът, в който трябва да се съобразим, че в масива трябва да започнем да обработваме команди, но едва след като получим командата "mall.Enter". Как можем да направим това? Използването на while или do-while цикъл e добър избор. Ето примерно решение как можем да пропуснем всички команди преди получаване на командата "mall.Enter":

Може да замените този while с for цикъл използвайки само условието и стъпката на for.

Тук е мястото да отбележим, че извикването на i++ след края на цикъла се използва за преминаване към първата команда за обработване, защото в края на цикъла command[i] сочи точно към "mall.Enter", което не трябва да се обработва като действие в мола.

Алгоритъм за решаване на задачата

Алгоритъмът за решаването на самата задача е праволинеен - продължаваме да обработваме команди, докато не бъде подадена командата "mall.Exit". През това време разглеждаме всеки един знак (char) от всяка една команда спрямо правилата, указани в условието, и едновременно с това модифицираме парите, които Лина има, и съхраняваме броя на покупките.

Нека разгледаме първите два проблема пред нашия алгоритъм. Първият проблем засяга начина, по който можем да четем командите, докато не срещнем "mall.Exit". Решението, както видяхме по-горе, е да се използва while цикъл. Вторият проблем е задачата да достъпим всеки един знак от подадената команда. Имайки предвид, че входните данни с командите са от тип string, то най-лесният начин да достъпим всеки знак в тях е чрез for цикъл.

Ето как би изглеждало използване на два такива цикъла:

Следващата част от алгоритъма ни е да обработим символите от командите, спрямо следните правила от условието:

• Ако символът е главна буква, Лина получава 50% намаление, което означава, че трябва да намалите парите, които тя има, с 50% от цифровата репрезентация ASCII символа.
• Ако символът е малка буква, Лина получава 70% намаление, което означава, че трябва да намалите парите, които тя има, с 30% от цифровата репрезентация ASCII символа.
• Ако символът е "%", Лина прави покупка, която намалява парите ѝ на половина.
• Ако символът е "*", Лина изтегля пари от дебитната си карта и добавя към наличните си средства 10 лева.
• Ако символът е различен от упоменатите горе, Лина просто прави покупка без намаления и в такъв случай просто извадете стойността на ASCII символа от наличните ѝ средства.

Нека разгледаме проблемите от първото условие, които стоят пред нас. Единият е как можем да разберем дали даден символ представлява главна буква. Можем да използваме един от двата начина:

• Имайки предвид, факта, че буквите в азбуката имат ред, можем да използваме следната проверка action >= 'A' && action <= 'Z', за да проверим дали нашият символ се намира в интервала от големи букви.

• Можем да използваме метода str.toUpperCase() и да сравним дали символът е същия, като този, който ще получим от str.toUpperCase().

Другият проблем е как можем да пропуснем даден символ, ако той представлява операция, която изисква повече пари, отколкото Лина има? Това е възможно да бъде направено с използване на continue конструкцията.

Примерната проверка за първата част от условието изглежда по следния начин:

Забележка: purchases е променлива от тип int , в която държим броя на всички покупки.

Смятаме, че читателят не би трябвало да изпита проблем при имплементацията на всички други проверки, защото са много сходни с първата.

Форматиране на изхода

В края на задачата трябва да принтираме определен изход, в зависимост от следното условие:

• Ако не са били направени никакви покупки – "No purchases. Money left: {останали пари} lv."
• Ако е направена поне една покупка - "{брой покупки} purchases. Money left: {останали пари} lv."

Операциите по принтиране са тривиални. На база променливата за брой покупки можем да определим кой вариант на изхода ни трябва. Единственото нещо, с което трябва да се съобразим е, че парите трябва да се принтират с точност от 2 символа след десетичния знак.

Как можем да направим това? Ще оставим отговора на този въпрос на читателя.

Тестване в Judge системата

Тествайте решението си тук: https://judge.softuni.org/Contests/Practice/Index/942#0.

Задача: числен израз

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

За използване на "Израз заклинание", вещицата трябва да знае резултата от математическия израз предварително. Израз заклинанието се състои от няколко прости математически израза. Всеки математически израз може да съдържа оператори за събиране, изваждане, умножение и/или деление.

Изразът се решава без да се вземат под внимание математическите правила при пресмятане на числови изрази. Това означава, че приоритет има последователността на операторите, а не това какъв вид изчисление правят. Израза може да съдържа скоби, като всичко в скобите се пресмята първо. Всеки израз може да съдържа множество скоби, но не може да съдържа вложени скоби:

• Израз съдържащ (…(…)…) е невалиден.
• Израз съдържащ (…)…(…) е валиден.

Пример

Изразът

бива решен по следния начин:

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

Входни данни

Входните данни се състоят от един аргумент. Той съдържа математическият израз за пресмятане. Аргументът винаги завършва със символа "=". Символът "=" означава край на математическия израз.

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

Изходни данни

Изходните данни трябва да се принтират на конзолата. Изходът се състои от един ред – резултата от пресметнатия математически израз.

Резултатът трябва да бъде закръглен до втората цифра след десетичния знак.

Ограничения

• Изразите ще състоят от максимум 2500 символа.
• Числата от всеки математически израз ще са в интервала [1 … 9].
• Операторите в математическите изрази винаги ще бъдат измежду + (събиране), - (изваждане), / (деление) или * (умножение).
• Резултатът от математическия израз ще е в интервала [-100000.00 … 100000.00].
• Позволено време за изпълнение: 0.1 секунди.
• Позволена памет: 16 MB.

Примерен вход и изход

Насоки и подсказки

Обикновено, първо ще прочетем и обработим входа, след това решаваме задачата и накрая отпечатаме резултата, форматиран, според условието. В случая входът се състои от 1 аргумент, който няма нужда да бъде обработван допълнително. Затова директно преминаваме към решаването на задачата.

Алгоритъм за решаване на задачата

За целите на нашата задача ще имаме нужда от няколко променливи:

• Една променлива, в която ще пазим текущия резултат.
• Една променлива, в която ще пазим до кой индекс сме стигнали в обхождането на нашия израз.
• Една променлива, в която ще пази текущия символ, който обработваме.
• И последна променлива, в която ще пазим текущия оператор от нашия израз.

След като вече имаме началните си променливи, трябва да помислим върху това каква ще е основната структура на нашата програма. От условието разбираме, че всеки израз завършва с =, т.е. ще трябва да обработваме символи, докато не срещнем =. Следва точното изписване на while цикъл.

Следващата стъпка е обработването на нашата symbol променлива. За нея имаме 3 възможни случая:

• Ако символът е начало на подизраз, заграден в скоби, т.е. срещнатият символ е (.
• Ако символът е цифра между 0 и 9. Но как можем да проверим това? Как можем да проверим дали символът ни е цифра? Тук идва на помощ ASCII кодът на символа, чрез който можем да използваме следната формула: [ASCII кода на нашия символ] - [ASCII кода на символа 0] = [цифрата, която репрезентира символа]. Ако резултатът от тази проверка е между 0 и 9, то тогава нашият символ наистина е число. (Алтернативно можем да използваме директно символите '0' и '9' или техните ASCII кодове.)
• Ако символът е оператор, т.е. е +, -, * или /.

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

• Ако нашият символ е оператор, то тогава единственото, което трябва да направим, е да зададем нова стойност на променливата expressionOperator.
• Ако нашият символ е цифра, тогава трябва да променим текущия резултат от израза в зависимост от текущия оператор, т.е. ако expressionOperator е -, тогава трябва да намалим резултата с цифровата репрезентация на текущия символ. Можем да вземем цифровата репрезентация на текущия символ, чрез формулата, която използвахме при проверката на този случай ([ASCII кода на нашия символ] - [ASCII кода на символа0] = [цифрата, която репрезентира символа])

• Ако нашият символ е (, това индикира началото на подизраз (израз в скоби). По дефиниция подизразът трябва да се калкулира преди да се модифицира резултата от целия израз (действията в скобите се извършват първи). Това означава, че ще имаме локален резултат за подизраза ни и локален оператор.

След това, за пресмятане стойността на подизраза използваме същите методи, които използвахме за пресмятане на главния израз - използваме while цикъл, за да обработваме символи (докато не срещнем символа )). В зависимост от това дали прочетения символ е цифра или оператор, модифицираме резултата на подизраза. Имплементацията на тези операции е аналогична на имплементацията за пресмятане на изрази, описана по-горе, затова смятаме, че читателят не би трябвало да има проблем с нея.

След като приключим калкулацията на резултата от подизраза ни, модифицираме резултата на целия израз в зависимост от стойността на expressionOperator.

Форматиране на изхода

Единствения изход, който програмата трябва да принтира на конзолата, е резултатът от решаването на израза, с точност два символа след десетичния знак. Как можем да форматираме изхода по този начин? Отговора на този въпрос оставяме на читателя.

Тестване в Judge системата

Тествайте решението си тук: https://judge.softuni.org/Contests/Practice/Index/942#1.

Задача: бикове и крави

Всички знаем играта „Бикове и крави“ (https://en.wikipedia.org/wiki/Bulls_and_cows). При дадено 4-цифрено тайно число и 4-цифрено предполагаемо число, използваме следните правила:

• Ако имаме цифра от предполагаемото число, която съвпада с цифра от тайното число и е на същата позиция, имаме бик.
• Ако имаме цифра от предполагаемото число, която съвпада с цифра от тайното число, но е на различна позиция, имаме крава.

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

Ако не съществуват предполагаеми числа, които да отговарят на зададените критерии на конзолата, трябва да се отпечата "No".

Входни данни

Входните данни се състоят от 3 аргумента:

• Първият съдържа секретното число.
• Вторият съдържа броя бикове.
• Третият съдържа броя крави.

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

Изходни данни

Изходните данни трябва да се принтират на конзолата. Изходът трябва да се състои от един единствен ред – всички предполагаеми числа, разделени с единично празно място. Ако не съществуват предполагаеми числа, които да отговарят на зададените критерии на конзолата, трябва да се изпише “No”.

Ограничения

• Тайното число винаги ще се състои от 4 цифри в интервала [1..9]. [TODO: Цифрите е хубаво/трябва да са уникални. Ако имам тайно число 2132 и предположение 8762 имам 1 бик и 1 крава за 1 число. ]
• Броят на кравите и биковете винаги ще е в интервала [0..9]. [TODO: Има ли смисъл да имаме крави и бикове от 0..9? Кога ще имам 5 бика и 7 крави? Входът трябва да е валиден.]
• Позволено време за изпълнение: 0.15 секунди.
• Позволена памет: 16 MB.

Примерен вход и изход

Насоки и подсказки

Тъй като входът пристига директно, като аргументи на функцията ни остават следните стъпки от решението:

• Ще генерираме всички възможни четирицифрени комбинации (кандидати за проверка).
• За всяка генерирана комбинация ще изчислим колко бика и колко крави има в нея спрямо секретното число. При съвпадение с търсените бикове и крави, ще отпечатаме комбинацията.

Алгоритъм за решаване на задачата

Преди да започнем писането на алгоритъма за решаване на нашия проблем, трябва да декларираме флаг, който да указва дали е намерено решение:

Ако след приключването на нашия алгоритъм, този флаг все още е false, тогава ще принтираме No на конзолата, както е указано в условието.

Нека започнем да размишляваме над нашия проблем. Това, което трябва да направим, е да анализираме всички числа от 1111 до 9999 без тези, които съдържат в себе си нули (напр. 9011, 3401 и т.н. са невалидни). Какъв е най-лесният начин за генериране на всички тези числа? С вложени цикли. Тъй като имаме 4-цифрено число, ще имаме 4 вложени цикъла, като всеки един от тях ще генерира отделна цифра от нашето число за тестване.

Алтернативен подход е да обиколите с един цикъл числата от 1111 до 9999 и да прескачате всички числа с '0' в себе си, но това би променило малко решението, което ще изпълним по-долу.

Благодарение на тези цикли, имаме достъп до всяка една цифра на всички числа, които трябва да проверим. Следващата ни стъпка е да разделим секретното число на цифри. Това може да се постигне много лесно чрез комбинация от целочислено и модулно деление.

Как? При деление получаваме дробно число. Или трябва да премахнем дробната част преди да разделим модулно на 10 чрез Math.floor(…) или чрез кастване към цяло число чрез parseInt(…). В примера по-горе премахваме дробната част.

Остават ни последните две стъпки преди да започнем да анализираме колко крави и бикове има в дадено число. Съответно, първата е декларацията на counter променливи във вложените ни цикли, за да броим кравите и биковете за текущото число. Втората стъпка е да направим копия на цифрите на текущото число, което ще анализираме, за да предотвратим проблеми с работата на вложите цикли, ако правим промени по тях.

Вече сме готови да започнем анализирането на генерираните числа. Каква логика можем да използваме? Най-елементарният начин да проверим колко крави и бикове има в едно число е чрез поредица от if-else проверки. Да, не е най-оптималния начин, но с цел да не използваме знания извън пределите на тази книга, ще изберем този подход.

От какви проверки имаме нужда?

Проверката за бикове е елементарна - проверяваме дали първата цифра от генерираното число е еднаква със същата цифра от секретното число. Премахваме проверените цифри с цел да избегнем повторения на бикове и крави.

Повтаряме действието за втората, третата и четвърта цифра.

Проверката за крави можем да направи по следния начин - първо проверяваме дали първата цифра от генерираното число съвпада с втората, третата или четвъртата цифра на секретното число. Можем да обединим всички проверки в едно условие, знаейки, че и в трите случая имаме крава, но няма да знаем коя цифра да премахнем, затова ги изписваме едно по едно:

След това последователно проверяваме дали втората цифра от генерираното число съвпада с първата, третата или четвъртата цифра на секретното число, дали третата цифра от генерираното число съвпада с първата, втората или четвъртата цифра на секретното число и накрая проверяваме дали четвъртата цифра от генерираното число съвпада с първата, втората или третата цифра на секретното число.

Отпечатване на изхода

След като приключим всички проверки, ни остава единствено да проверим дали биковете и кравите в текущото генерирано число съвпадат с желаните бикове и крави, прочетени от конзолата. Ако това е така, принтираме текущото число на конзолата.

Тестване в Judge системата

Тествайте решението си тук: https://judge.softuni.org/Contests/Practice/Index/942#2.