[te/upp-2023/w12] Added exercises

2 files changed, 110 insertions, 0 deletions

diff --git a/src/teaching/upp-2023/index.md b/src/teaching/upp-2023/index.md
index 459d476..77958b3 100644
--- a/src/teaching/upp-2023/index.md
+++ b/src/teaching/upp-2023/index.md
@@ -30,3 +30,4 @@
 |  |04.12.2023|[Допълнително упражнение 2](./additional2/) \|\| [GitHub classroom](https://classroom.github.com/a/CrerXpf6)|
 |10|15.12.2023|[Задачи](./week10) \|\| [GitHub classroom](https://classroom.github.com/a/EJcTQRz4)|
 |11|22.12.2023|[Задачи](./week11) \|\| [GitHub classroom](https://classroom.github.com/a/cZRnZj9y)|
+|12|05.01.2024|[Задачи](./week12) \|\| [GitHub classroom](https://classroom.github.com/a/KEDSxDjl)|
diff --git a/src/teaching/upp-2023/week12/index.md b/src/teaching/upp-2023/week12/index.md
new file mode 100644
index 0000000..d8f9886
--- /dev/null
+++ b/src/teaching/upp-2023/week12/index.md
@@ -0,0 +1,109 @@
+# Задачи - УПП, Седмица 12, 05.01.2024
+
+GitHub classroom: [classroom.github.com/a/KEDSxDjl](https://classroom.github.com/a/cZRnZj9y)
+
+&&important Във всички задачи **трябва** да използвате рекурсия!
+
+## Алтернативни задачи
+
+Считайте [задачите от семинара](https://github.com/ivanahristova/introduction-to-programming-2023-2024/tree/main/sem12) и [тези от миналия път](../week11/) като част от днешните задачи.
+Тоест, за хората които се затрудняват повечко, решете ги и след това се върнете тук.
+Разбира се, ще помагам и с тях.
+
+## Задача 1
+
+Имате някакъв брой предмети, като всеки предмет има ценност (число) и тежест (число пак).
+Искате в раница да сложите предмети, като целта е ценността да бъде максимална, обаче раницата има капацитет на тежест, тоест тази ценност трябва да бъде спрямо максималната обща тежест.
+
+От входа получавате число N, след това толкова на брой предмета (тоест 2N на брой числа, като броейки от нула, четните са ценностти, а нечетните тежести).
+Накрая получавате максималната обща тежест за раницата.
+Трябва да изкарате на екрана максималната възможна обща ценност.
+
+**Примери:**
+
+|Вход|Изход|
+|----|-----|
+|3<br>1 4<br>2 5<br>3 1<br>4|3|
+|3<br>1 4<br>2 5<br>3 6<br>3|0|
+|6<br>50 56<br>50 59<br>64 80<br>46 64<br>50 75<br>5 17<br>190|190<!-- https://people.sc.fsu.edu/~jburkardt/datasets/knapsack_01/knapsack_01.html -->|
+
+
+## Задача 2
+
+Получавате N и M, съответно броя редове и колони в дъска.
+Всяка клетка от дъската е пълна или празна.
+След това получавате NxM на брой символа за всяка клетка, като `.` означава празна клетка, докато `#` означава пълна.
+Накрая получавате две числа - координати (започващи от нула, като 0,0 е горния-ляв ъгъл) в дъската.
+
+От подадените координати трябва да запълните "фигурата" в която се намира (фигурата която огражда) дадената плочка.
+С други думи, представете си че дъската е изображение, всяка клетка е пиксел, в изображението има бели и черни пиксели, и на дадените координати е кликнато с "Bucket fill" за да се оцвети в черно дадена фигура.
+
+Оцветяването да се случва само в 4те прави посоки (без диагонали).
+
+![](https://upload.wikimedia.org/wikipedia/commons/7/7e/Recursive_Flood_Fill_4_%28aka%29.gif)
+
+**Пример:**
+
+|Вход|Изход|
+|----|-----|
+|5 11<br><pre>- - # # - - - - - - -<br>- # - - # - - - - - -<br># - - - - # # # # # #<br>- # - - # - - - # - #<br>- - # # - - - - - - -</pre>2 2|<pre>- - # # - - - - - - -<br>- # # # # - - - - - -<br># # # # # # # # # # #<br>- # # # # - - - # - #<br>- - # # - - - - - - -</pre>|
+
+## Задача 3
+
+Имате шахматна дъска (8 на 8) и върху нея имате 8 царици.
+Напомням, че царицата в шаха може да се движи вертикално, хоризонтално и диагонално произволен брой клетки в един ход.
+
+Интересуваме се от такова поставяне на всички царици, че нито една няма да вземе никоя друга царица в един ход.
+Пример:
+
+![](https://upload.wikimedia.org/wikipedia/commons/6/69/Solution_A_for_8_Queen_Puzzles.png)
+
+Напишете програма, която намира броя на възможните такива поставяния на цариците.
+От входа не получавате нищо.
+
+**Пример:**
+
+|Вход|Изход|
+|----|-----|
+|    |92   |
+
+**Бонус:** направете програмата да изкарва всяко решение
+
+## Задача 4
+
+<!-- https://mathcenter.oxford.emory.edu/site/cs171/probSetUsingStacks/ -->
+
+Нормално ние представяме математически операции чрез "инфиксен" запис, тоест операторът е по средата, между нещата върху които работи (пример: `1 + 2`).
+Обаче, това не е задължително, по обратната полска нотация винаги слагаме оператът след нещата върху които работи (пример: `1 2 +`).
+
+Бонусът на това, е че не ни трябва скобуване и ред на операциите.
+В инфиксния израз `(2 + 3) * (2 ^^ 2)`, без скобите, сбора ще се извърши след умножението и степенуването ще се извърши след умножението.
+Обаче, ако искаме да изразим това в обратен полски запис, просто правим `2 3 + 2 * ^^ 2`.
+А ако искаме оригиналното действие, без скоби, записваме `2 3 2 * 2 ^^ +`.
+
+Ако изглежда объркващо, идеята е че всеки оператор работи върху предходните две стойности, изчисляваме изразите от ляво надясно и заместваме веднага.
+Тоест, при последния пример, пропускаме първите три числа, стигаме до `*`, умножаваме последните две и заместваме трите неща (`3 2 *`) с резултата, следователно имаме `2 6 2 ^^ +`, пропускаме две, стигаме до `^^` и так.нат.
+
+Направете програма, която чисто рекурсивно изчислиява изрази в обратен полски запис, който поддържа цели числа и операциите събиране, умножение, деление, изваждане и степенуване (за степенуване ще използваме знакът `^`).
+
+&&important Обаче, за едно извикване на рекурсивната функция, може да пазите само един елемент на израза (число или оператор)!
+
+Изразът винаги завършва на знака `$`.
+
+&&warn Относно вход/изход, понеже няма как да знаем дали i-тата стойност е число или знак (операция), трябва да използваме функцията `std::cin.fail()`, която връща булева стойност, която ни казва дали записването на входа е било успешно.<br>  
+       Тоест, може винаги да запазвате входа в целочислен тип, когато стигнете до знак `std::cin.fail()` ще върне `true`.
+       След това трябва да "забравите" за грешката чрез `std::cin.clear()` и може втори път да запазите входа (провалените данни ще се препрочетат) в променлива от знаков тип.<br>  
+       Но това поражда друг проблем, понеже записваме в целочислен тип, когато въведем `+` или `-`, `std::cin` ще очаква това да е водещ знак на число, и ще продължи да чака входа докато не въведем друг знак, тоест `+` и `-` ще бъдат пропуснати.
+       Като компромисен вариант, просто пред тях винаги ще слагаме `'` и в кода ще го пропускаме.
+
+**Примери:**
+
+|Вход|Изход|
+|----|-----|
+|1 2 '+ 3 / $|1|
+|1 4 3 2 ^ * '+ 14 7 / '- $|35|
+
+## Attribution
+
+- Анимация в [Задача 2](#2) от André Karwath (Aka) на [Уикипедия](https://commons.wikimedia.org/w/index.php?curid=481651) под лиценз CC BY-SA 2.5
+- Изображение на шахматна дъска в [Задача 3](#3) от Encik Tekateki в [Уикипедия](https://commons.wikimedia.org/w/index.php?curid=77832290) под лиценз CC BY-SA 4.0