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

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

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

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

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

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

На първия ред от входа ще бъде подадена сумата, която Лина има преди да започне да пазарува. След това при получаване командата "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.

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

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

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

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

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

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

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

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

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

Но във втората има детайл, с който трябва да се съобразим. Условието гласи следното:

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

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

Тук е мястото да отбележим, че извикването на scanner.nextLine() след края на цикъла се използва за преминаване към първата команда за обработване.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример

Изразът

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

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

Входни данни

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

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

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

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

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

Ограничения

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

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

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

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

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

Входните данни се състоят от точно един ред от конзолата. Тук имаме два начина, по които можем да обработим входа. Първият е чрез прочитането на целия ред с командата bufferReader.readLine()(където bufferReader е променлива от тип BufferedReader) и достъпването на всеки един символ (char) от реда чрез foreach цикъл. Вторият е чрез прочитане на входа символ по символ чрез командата bufferReader.read() и обработване на всеки символ.

За решаване на задачата ще използваме втория вариант.

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

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

• Една променлива, в която ще пазим текущия резултат.
• Още една променлива, в която ще пазим текущия оператор от нашия израз.

Относно кода по-горе трябва да поясним следния детайл. Стойността по подразбиране на оператора е +, за да може още първото срещнато число да бъде събрано с резултата ни.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Входни данни

Входните данни се четат от конзолата. Входът се състои от 3 реда:

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

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

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

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

Ограничения

• Тайното число винаги ще се състои от 4 цифри в интервала [1..9].
• Броят на кравите и биковете винаги ще е в интервала [0..9].
• Позволено време за изпълнение: 0.15 секунди.
• Позволена памет: 16 MB.

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

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

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

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

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

За входа на нашата задача имаме 3 реда:

• Секретното число.
• Броят желани бикове.
• Броят желани крави.

Прочитането на тези входни данни е тривиално:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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