В настоящата глава ще разгледаме няколко задачи с ниво на трудност, каквото може да очаквате от задачите на практическия изпит по “Основи на програмирането”. Ще преговорим и упражним всички знания, които сте придобили от настоящата книга и през курса "Programing Basics".
Курсът "Programing Basics" приключва с практически изпит. Включени са 6 задачи, като ще имате 4 часа, за да ги решите. Всяка от задачите на изпита ще засяга една от изучаваните теми по време на курса. Темите на задачите са както следва:
- Задача с прости сметки (без проверки)
- Задача с единична проверка
- Задача с по-сложни проверки
- Задача с единичен цикъл
- Задача с вложени цикли (чертане на фигурка на конзолата)
- Задача с вложени цикли и по-сложна логика
Всички изпити и домашни се тестват автоматизирано през онлайн Judge система: https://judge.softuni.org. За всяка от задачите има открити (нулеви) тестове, които ще ви помогнат да разберете какво се очаква от задачата и да поправите грешките си, както и състезателни тестове, които са скрити и проверяват дали задачата ви работи правилно. В Judge системата се влиза с вашия softuni.bg акаунт.
Как работи тестването в Judge системата? Качвате сорс кода и от менюто под него избирате да се изпълни с JavaScript. Програмата бива тествана с поредица от тестове, като за всеки успешен тест получавате точки.
Първата задача на практическия изпит по “Основи на програмирането” обхваща прости пресмятания без проверки и цикли. Ето няколко примера:
| Триъгълник в равнината е зададен чрез координатите на трите си върха. Първо е зададен върхът (x1, y1). След това са зададени останалите два върха: (x2, y2) и (x3, y3), които лежат на обща хоризонтална права (т.е. имат еднакви Y координати). Напишете програма, която пресмята лицето на триъгълника по координатите на трите му върха. |
|
Като параметри на функцията подаваме 6 цели числа: x1, y1, x2, y2, x3, y3.
- Всички числа са в диапазона [-1000 … 1000].
- Гарантирано е, че y2 = y3.
Да се отпечата на конзолата лицето на триъгълника.
| Вход | Изход | Чертеж | Обяснения |
|---|---|---|---|
| 5 -2 6 1 1 1 |
7.5 | |
Страната на триъгълника а = 6 - 1 = 5 Височината на триъгълника h = 1 - (-2) = 3 Лицето на триъгълника S = a * h / 2 = 5 * 3 / 2 = 7.5 |
| Вход | Изход | Чертеж | Обяснения |
|---|---|---|---|
| 4 1 -1 -3 3 -3 |
8 |  |
Страната на триъгълника а = 3 - (-1) = 4 Височината на триъгълника h = 1 - (-3) = 4 Лицето на триъгълника S = a * h / 2 = 4 * 4 / 2 = 8 |
Изключително важно при подобен тип задачи, при които се подават някакви координати, е да обърнем внимание на реда, в който се подават, както и правилно да осмислим кои от координатите ще използваме и по какъв начин. В случая, на входа се подават x1, y1, x2, y2, x3, y3 в този си ред. Ако не спазваме тази последователност, решението става грешно. Първо пишем кода, който чете подадените данни:
Трябва да пресметнем страната и височината на триъгълника. От примерите, както и от условието y2 = y3 забелязваме, че едната страна винаги е успоредна на хоризонталната ос. Това означава, че нейната дължина е равна на дължината на отсечката между нейните координати x2 и x3, която е равна на разликата между по-голямата и по-малката координата. Аналогично можем да изчислим и височината. Тя винаги ще е равна на разликата между y1 и y2(или y3, тъй като са равни). Тъй като не знаем дали винаги x2 ще е по-голям от x3, или y1 ще е под или над страната на триъгълника, ще използваме абсолютните стойности на разликата, за да получаваме винаги положителни числа, понеже една отсечка не може да има отрицателна дължина.
По познатата ни от училище формула за намиране на лице на триъгълник ще пресметнем лицето.
Единственото, което остава, е да отпечатаме лицето на конзолата.
Тествайте решението си тук: https://judge.softuni.org/Contests/Practice/Index/939#0.
Строителни работници трябва да пренесат общо x тухли. Работниците са w на брой и работят едновременно. Те превозват тухлите в колички, всяка с вместимост m тухли. Напишете програма, която прочита целите числа x, w и m и пресмята колко най-малко курса трябва да направят работниците, за да превозят тухлите.
Като параметри на функцията подаваме 3 цели числа:
- Броят тухли x
- Броят работници w
- Вместимостта на количката m
Всички входни числа са цели и в диапазона [1 … 1000].
Да се отпечата на конзолата минималният брой курсове, необходими за превозване на тухлите.
| Вход | Изход | Обяснения |
|---|---|---|
| 120 2 30 |
2 | Имаме 2 работника, всеки вози по 30 тухли на курс. Общо работниците возят по 60 тухли на курс. За да превозят 120 тухли, са необходими точно 2 курса. |
| Вход | Изход | Обяснения |
|---|---|---|
| 355 3 10 |
12 | Имаме 3 работника, всеки вози по 10 тухли на курс. Общо работниците возят по 30 тухли на курс. За да превозят 355 тухли, са необходими точно 12 курса: 11 пълни курса превозват 330 тухли и последният 12-ти курс пренася последните 25 тухли. |
| Вход | Изход | Обяснения |
|---|---|---|
| 5 12 30 |
1 | Имаме 5 работника, всеки вози по 30 тухли на курс. Общо работниците возят по 150 тухли на курс. За да превозят 5 тухли, е достатъчен само 1 курс (макар и непълен, само с 5 тухли). |
Входът е стандартен, като единствено трябва да внимаваме за последователността, в която прочитаме данните.
Пресмятаме колко тухли носят работниците на един курс.
Като разделим общия брой на тухлите, пренесени за 1 курс, ще получим броя курсове, необходими за пренасянето им. Ще използваме метода**Math.ceil(…)**, за да закръглим получения резултат винаги нагоре. Когато тухлите могат да се пренесат с точен брой курсове, делението ще връща точно число и няма да има нищо за закръгляне. Съответно, когато не е така, резултатът от делението ще е броя на точните курсове, но с десетична част. Десетичната част ще се закръгли нагоре и така ще се получи нужният 1 курс за оставащите тухли.
Накрая принтираме резултата на конзолата.
Тествайте решението си тук: https://judge.softuni.org/Contests/Practice/Index/939#1.
Втората задача на практическия изпит по “Основи на програмирането” обхваща условна конструкция и прости премятания. Ето няколко примера:
Върху хоризонтална права е разположена хоризонтална отсечка, зададена с x координатите на двата си края: first и second. Точка е разположена върху същата хоризонтална права и е зададена с x координатата си. Напишете програма, която проверява дали точката е вътре или вън от отсечката и изчислява разстоянието до по-близкия край на отсечката.
Като параметри на функцията подаваме 3 цели числа:
- Числото first – единия край на отсечката.
- Числото second – другия край на отсечката.
- Числото point – местоположението на точката.
Всички входни числа са цели и в диапазона [-1000 … 1000].
Резултатът да се отпечата на конзолата:
- На първия ред да се отпечата "in" или "out" – дали точката е върху отсечката или извън нея.
- На втория ред да се отпечата разстоянието от точката до най-близкия край на отсечката.
| Вход | Изход | Визуализация |
|---|---|---|
| 10 5 7 |
in 2 |
 |
| Вход | Изход | Визуализация |
|---|---|---|
| 8 10 5 |
out 3 |
 |
| Вход | Изход | Визуализация |
|---|---|---|
| 1 -2 3 |
out 2 |
 |
Четем входа от конзолата.
Тъй като не знаем коя точка е от ляво и коя е от дясно, ще си направим две променливи, които да ни отбелязват това. Тъй като лявата точка е винаги тази с по-малката х координата, ще ползваме Math.min(…), за да я намерим. Съответно, дясната е винаги тази с по-голяма х координата и ползваме Math.max(…). Ще намерим и разстоянието от точката x до двете точки. Понеже не знаем положението им една спрямо друга, ще използваме Math.abs(…), за да получим положителен резултат.
По-малкото от двете разстояния ще намерим ползвайки Math.min(…).
Остава да намерим дали точката е на линията или извън нея. Точката ще се намира на линията винаги, когато тя съвпада с някоя от другите две точки или х координатата ѝ се намира между тях. В противен случай, точката се намира извън линията. След проверката изкарваме едното от двете съобщения, спрямо това коя проверка е удовлетворена.
Накрая принтираме разстоянието, намерено преди това.
Тествайте решението си тук: https://judge.softuni.org/Contests/Practice/Index/939#2.
Да се напише програма, която проверява дали дадена точка (с координати x и y) е вътре или извън следната фигура:
Като параметри на функцията подаваме две цели числа: x и y.
Всички входни числа са цели и в диапазона [-1000 … 1000].
Да се отпечата на конзолата "in" или "out" – дали точката е вътре или извън фигурата (на контура е вътре).
| Вход | Изход | Вход | Изход |
|---|---|---|---|
| 8 -5 |
in | 6 -3 |
in |
| Вход | Изход | Вход | Изход |
|---|---|---|---|
| 11 -5 |
out | 11 2 |
out |
За да разберем дали точката е във фигурата, ще разделим фигурата на 2 четириъгълника:
Достатъчно условие е точката да се намира в един от тях, за да се намира във фигурата.
Четем от конзолата входните данни:
Ще създадем две променливи, които ще отбелязват дали точката се намира в някой от правоъгълниците.
При отпечатването на съобщението ще проверим дали някоя от променливите е приела стойност true. Достатъчно е само една от тях да е true, за да се намира точката във фигурата.
Тествайте решението си тук: https://judge.softuni.org/Contests/Practice/Index/939#3.
Третата задача на практическия изпит по “Основи на програмирането” включва няколко вложени проверки съчетани с прости пресмятания. Ето няколко примера:
Дадени са две числа d (ден) и m (месец), които формират дата. Да се напише програма, която отпечатва датата, която ще бъде след 5 дни. Например 5 дни след 28.03 е датата 2.04. Приемаме, че месеците: април, юни, септември и ноември имат по 30 дни, февруари има 28 дни, а останалите имат по 31 дни. Месеците да се отпечатат с водеща нула, когато са едноцифрени (например 01, 08).
Като параметри на функцията подаваме две цели числа:
- Цяло число d в интервала [1 … 31] – ден. Номерът на деня не надвишава броя дни в съответния месец (напр. 28 за февруари).
- Цяло число m в интервала [1 … 12] – месец. Месец 1 е януари, месец 2 е февруари, …, месец 12 е декември. Месецът може да съдържа водеща нула (напр. април може да бъде изписан като 4 или 04).
Отпечатайте на конзолата един единствен ред, съдържащ дата след 5 дни във формат ден.месец. Месецът трябва да бъде двуцифрено число с водеща нула, ако е необходимо. Денят трябва да е без водеща нула.
| Вход | Изход | Вход | Изход |
|---|---|---|---|
| 28 03 |
2.04 | 27 12 |
1.01 |
| Вход | Изход | Вход | Изход |
|---|---|---|---|
| 25 1 |
30.01 | 26 02 |
3.03 |
Приемаме си входа от конзолата.
За да си направим по-лесно проверките, ще си създадем една променлива, която ще съдържа броя дни, които има в месеца, който сме задали.
Увеличаваме деня с 5.
Проверяваме дали денят не е станал по-голям от броя дни, които има в съответния месец. Ако това е така, трябва да извадим дните от месеца от получения ден, за да получим нашият ден на кой ден от следващия месец съответства.
След като сме минали в следващия месец, това трябва да се отбележи, като увеличим първоначално зададения с 1. Трябва да проверим, дали той не е станал по-голям от 12 и ако е така, да коригираме. Тъй като няма как да прескочим повече от един месец, когато увеличаваме с 5 дни, долната проверка е достатъчна.
Остава само да принтираме резултата на конзолата. Важно е да форматираме изхода правилно, за да се появява водещата нула в първите 9 месеца. Това става, като създадем допълнителна променлива за месеца, към която да прибавим 0 при необходимост. Накрая принтираме деня и новата променлива за месеца.
Тествайте решението си тук: https://judge.softuni.org/Contests/Practice/Index/939#4.
Дадени са 3 цели числа. Да се напише програма, която проверява дали сумата на две от числата е равна на третото. Например, ако числата са 3, 5 и 2, сумата на две от числата е равна на третото: 2 + 3 = 5.
Като параметри на функцията подаваме три цели числа. Числата са в диапазона [1 … 1000].
- Да се отпечата на конзолата един ред, съдържащ решението на задачата във формат "a + b = c", където a, b и c са измежду входните три числа и a ≤ b.
- Ако задачата няма решение, да се отпечата “No” на конзолата.
| Вход | Изход | Вход | Изход |
|---|---|---|---|
| 3 5 2 |
2 + 3 = 5 | 2 2 4 |
2 + 2 = 4 |
| Вход | Изход | Вход | Изход |
|---|---|---|---|
| 1 1 5 |
No | 2 6 3 |
No |
Приемаме си входа от конзолата.
Трябва да проверим дали сумата на някоя двойка числа е равна на третото. Имаме три възможни случая:
- a + b = c
- a + c = b
- b + c = a
Ще си напишем рамка, която после ще допълним с нужния код. Ако никое от горните три условия не е изпълнено, ще зададем на програмата да принтира "No".
Сега остава да разберем реда, в който ще се изписват двете събираеми на изхода на програмата. За целта ще направим вложено условие, което проверява кое от двете числа е по-голямото. При първия случай, ще стане по този начин:
Аналогично, ще допълним и другите два случая. Пълният код на проверките и изходът на програмата ще изглеждат така:
Тествайте решението си тук: https://judge.softuni.org/Contests/Practice/Index/939#5.
Четвъртата задача на практическия изпит по “Основи на програмирането” включва единичен цикъл с проста логика в него. Ето няколко примера:
Дадени са n цели числа a1, a2, …, an. Да се пресметнат сумите:
- sum1 = a1 + a4 + a7 + … (сумират се числата, започвайки от първото със стъпка 3).
- sum2 = a2 + a5 + a8 + … (сумират се числата, започвайки от второто със стъпка 3).
- sum3 = a3 + a6 + a9 + … (сумират се числата, започвайки от третото със стъпка 3).
Като параметър на функцията подаваме масив с големина n+1 (0 ≤ n ≤ 1000). Масивът ще съдържа броя на числата n и n цели числа в интервала [-1000 … 1000]: a1, a2, …, an.
На конзолата трябва да се отпечатат 3 реда, съдържащи търсените 3 суми, във формат като в примерите.
| Вход | Изход | Вход | Изход | Вход | Изход |
|---|---|---|---|---|---|
| 2 3 5 |
sum1 = 3 sum2 = 5 sum3 = 0 |
4 7 -2 6 12 |
sum1 = 19 sum2 = -2 sum3 = 6 |
5 3 5 2 7 8 |
sum1 = 10 sum2 = 13 sum3 = 2 |
Ще вземем броя на числата (големината на входния масив) и ще декларираме начални стойности на трите суми.
Тъй като не знаем предварително колко числа ще обработваме, ще си ги взимаме едно по едно в цикъл, който ще се повтори n на брой пъти и ще ги обработваме в тялото на цикъла.
За да разберем в коя от трите суми трябва да добавим числото, ще разделим поредния му номер на три и ще използваме остатъка. Ще използваме променливата i, която следи броя завъртания на цикъла, за да разберем на кое поред число сме. Когато остатъкът от i/3 е нула, това означава, че ще добавяме това число към първата сума, когато е 1 към втората и когато е 2 към третата.
Накрая, ще отпечатаме резултата на конзолата в изисквания формат.
Тествайте решението си тук: https://judge.softuni.org/Contests/Practice/Index/939#6.
Дадена е редица от n числа: a1, a2, …, an. Да се пресметне дължината на най-дългата нарастваща поредица от последователни елементи в редицата от числа.
Като параметър на функцията подаваме масив с големина n+1 (0 ≤ n ≤ 1000). Масивът ще съдържа броя на числата n и n цели числа в интервала [-1000 … 1000]: a1, a2, …, an.
На конзолата трябва да се отпечата едно число – дължината на най-дългата нарастваща редица.
| Вход | Изход | Вход | Изход | Вход | Изход | Вход | Изход |
|---|---|---|---|---|---|---|---|
| 3 5 2 4 |
2 | 4 2 8 7 6 |
2 | 4 1 2 4 4 |
3 | 4 5 6 7 8 |
4 |
За решението на тази задача трябва да помислим малко по-алгоритмично. Дадена ни е редица от числа и трябва да проверяваме дали всяко следващо, ще бъде по-голямо от предното и ако е така да броим колко дълга е редицата, в която това условие е изпълнено. След това трябва да намерим коя редица от всички такива е най-дълга. За целта, нека да си направим няколко променливи, които ще ползваме през хода на задачата.
Променливата n е броя числа, които ще получим от конзолата. В countCurrentLongest ще запазваме броя на елементите в нарастващата редица, която броим в момента. Напр. при редицата: 5, 6, 1, 2, 3 countCurrentLongest ще бъде 2, когато сме стигнали втория елемент от броенето (5, 6, 1, 2, 3) и ще стане 3, когато стигнем последния елемент (5, 6, 1, 2, 3), понеже нарастващата редица 1, 2, 3 има 3 елемента. Ще използваме countLongest, за да запазим най-дългата нарастваща редица. Останалите променливи са num - числото, на което се намираме в момента, и numPrev - предишното число, което ще сравним с num, за да разберем дали редицата расте.
Започваме да въртим числата и проверяваме дали настоящото число а е по-голямо от предходното numPrev. Ако това е изпълнено, значи редицата е нарастваща и трябва да увеличим броя ѝ с 1. Това запазваме в променливата, която следи дължината на редицата, в която се намираме в момента, а именно - countCurrentLongest. Ако числото num не е по-голямо от предходното, това означава, че започва нова редица и трябва да стартираме броенето от 1. Накрая, след всички проверки, numPrev става числото, което използваме в момента, и започваме цикъла от начало със следващото въведено num.
Ето и примерна реализация на описания алгоритъм:
Остава да разберем коя от всички редици е най-дълга. Това ще направим с проверка в цикъла дали редицата, в която се намираме в момента, е станала по-дълга от дължината на най-дългата намерена до сега. Целият цикъл ще изглежда така:
Накрая принтираме дължината на най-дългата намерена редица.
Тествайте решението си тук: https://judge.softuni.org/Contests/Practice/Index/939#7.
Петата задача на практическия изпит по “Основи на програмирането” изисква използване на един или няколко вложени цикъла за рисуване на някаква фигурка на конзолата. Може да се изискват логически размишления, извършване на прости пресмятания и проверки. Задачата проверява способността на студентите да мислят логически и да измислят прости алгоритми за решаване на задачи, т.е. да мислят алгоритмично. Ето няколко примера за изпитни задачи:
Да се напише функция, която приема като параметър цяло число n и чертае перфектен диамант с размер n като в примерите по-долу.
Параметър цяло число n в интервала [1 … 1000].
На конзолата трябва да се отпечата диамантът като в примерите.
| Вход | Изход | Вход | Изход |
|---|---|---|---|
| 2 | * *-* * |
3 | * *-* *-*-* *-* * |
| Вход | Изход | Вход | Изход |
|---|---|---|---|
| 4 | * *-* *-*-* *-*-*-* *-*-* *-* * |
5 | * *-* *-*-* *-*-*-* *-*-*-*-* *-*-*-* *-*-* *-* * |
В задачите с чертане на фигурки най-важното, което трябва да преценим е последователността, в която ще рисуваме. Кои елементи се повтарят и с какви стъпки. Ясно може да забележим, че горната и долната част на диаманта са еднакви. Най-лесно ще решим задачата, като направим един цикъл, който чертае горната част, и след това още един, който чертае долната (обратно на горната).
Ще си прочетем числото n от параметрите на функцията.
Започваме да рисуваме горната половина на диаманта. Ясно виждаме, че всеки ред започва с няколко празни места и *. Ако се вгледаме по-внимателно, ще забележим, че празните места са винаги равни на n - индекса на реда - 1 (на първия ред са n-1, на втория - n-2 и т.н.) Ще започнем с това да нарисуваме броя празни места, както и първата звездичка. Забележете, че започваме да броим от 0, а не от 1. След това ще остане само да добавим няколко пъти -*, за да довършим реда.
Ето фрагмент от кода за начертаване на горната част на диаманта:
Остава да довършим всеки ред с нужния брой -* елементи. На всеки ред трябва да добавим i такива елемента (на първия -> 0, на втория -> 1 и т.н.)
Ето и пълния код за начертаване на горната част на диаманта:
За да изрисуваме долната част на диаманта, трябва да обърнем горната на обратно. Ще броим от n - 2, тъй като ако започнем от n - 1, ще изрисуваме средния ред два пъти. Не забравяйте да смените стъпката от ++ на --.
Ето го и кода за начертаване на долната част на диаманта:
Остава да си сглобим цялата програма като първо четем параметъра на функцията, печатаме горната част на диаманта и след него и долната част на диаманта.
Тествайте решението си тук: https://judge.softuni.org/Contests/Practice/Index/939#8.
Да се напише функция, която приема като параметър цяло число n и чертае правоъгълник с размер n с две звездички в центъра, като в примерите по-долу.
Параметърът е цяло число n в интервала [2 … 1000].
На конзолата трябва да се отпечата правоъгълникът като в примерите.
| Вход | Изход | Вход | Изход |
|---|---|---|---|
| 2 | %%%%%**%%%%% |
3 | %%%%%%% %% ** %% %%%%%%% |
| Вход | Изход | Вход | Изход |
|---|---|---|---|
| 4 | %%%%%%%%% %% ** %% %%%%%%%%% |
5 | %%%%%%%%%%% %% %% ** %% %% %%%%%%%%%%% |
Прочитаме входния параметър на функцията.
Първото нещо, което лесно забелязваме, е че първият и последният ред съдържат 2 * n символа %. Ще започнем с това и после ще нарисуваме средата на четириъгълника.
От дадените примери виждаме, че средата на фигурата винаги има нечетен брой редове. Забелязваме, че когато е зададено четно число, броят на редовете е равен на предишното нечетно (2 -> 1, 4 -> 3 и т.н.). Създаваме си променлива, която представлява броя редове, които ще има нашият правоъгълник, и я коригираме, ако числото n е четно. След това ще нарисуваме правоъгълника без звездичките. Всеки ред има за начало и край символа % и между тях 2 * n - 2 празни места (ширината е 2 * n и вадим 2 за двата процента в края). Не забравяйте да преместите кода за последния ред след цикъла.
Можем да стартираме и тестваме кода до тук. Всичко без двете звездички в средата трябва да работи коректно.
Сега остава в тялото на цикъла да добавим и звездичките. Ще направим проверка дали сме на средния ред. Ако сме на средния, ще рисуваме реда заедно със звездичките, ако не - ще рисуваме нормален ред. Редът със звездичките има n - 2 празни места (n е половината дължина и махаме звездичката и процента), две звезди и отново n - 2 празни места. Двата процента в началото и в края на реда си ги оставяме извън проверката.
Тествайте решението си тук: https://judge.softuni.org/Contests/Practice/Index/939#9.
Последната (шеста) задача от практическия изпит по “Основи на програмирането” изисква използване на няколко вложени цикъла и по-сложна логика в тях. Задачата проверява способността на студентите да мислят алгоритмично и да решават нетривиални задачи, изискващи съставянето на цикли. Следват няколко примера за изпитни задачи.
По дадена двойка числа a и b да се генерират всички четворки n1, n2, n3, n4, за които a ≤ n1 < n2 < n3 < n4 ≤ b.
Като параметри на функцията получаваме две цели числа a и b в интервала [0 … 1000].
Изходът съдържа всички търсени четворки числа, в нарастващ ред, по една на ред.
| Вход | Изход | Вход | Изход |
|---|---|---|---|
| 3 7 |
3 4 5 6 3 4 5 7 3 4 6 7 3 5 6 7 4 5 6 7 |
15 20 |
15 16 17 18 15 16 17 19 15 16 17 20 15 16 18 19 15 16 18 20 15 16 19 20 15 17 18 19 15 17 18 20 15 17 19 20 15 18 19 20 16 17 18 19 16 17 18 20 16 17 19 20 16 18 19 20 17 18 19 20 |
| Вход | Изход | Вход | Изход |
|---|---|---|---|
| 5 7 |
No | 10 13 |
10 11 12 13 |
Прочитаме входните параметри на функцията. Създаваме и допълнителната променлива count, която ще следи дали има съществуваща редица числа.
Най-лесно ще решим задачата, ако логически я разделим на части. Ако се изисква да изведем всички редици от едно число между a и b, ще го направим с един цикъл, който изкарва всички числа от а до b. Нека помислим как ще стане това с редици от две числа. Отговорът е лесен - ще ползваме вложени цикли.
Можем да тестваме недописаната програма, за да проверим дали е вярна до този момент. Тя трябва да отпечата всички двойки числа i, j, за които i ≤ j.
Тъй като всяко следващо число от редицата трябва да е по-голямо от предишното, вторият цикъл ще се върти от i + 1 (следващото по-голямо число). Съответно, ако не съществува редица от две нарастващи числа (a и b са равни), вторият цикъл няма да се изпълни и няма да се разпечата нищо на конзолата.
Аналогично, остава да реализираме по същия начин вложените цикли и за четири числа. Ще добавим и увеличаване на брояча, който инициализирахме в началото, за да знаем дали съществува такава редица.
Накрая ще проверим дали броячът е равен на 0 и съответно ще принтираме “No” на конзолата, ако е така.
Тествайте решението си тук: https://judge.softuni.org/Contests/Practice/Index/939#10.
По дадено число n и минимална площ m да се генерират всички правоъгълници с цели координати в интервала [-n…n] с площ поне m. Генерираните правоъгълници да се отпечатат в следния формат:
(left, top) (right, bottom) -> area
Правоъгълниците се задават чрез горния си ляв и долния си десен ъгъл. В сила са следните неравенства:
- -n ≤ left < right ≤ n
- -n ≤ top < bottom ≤ n
Като параметри на функцията получаваме две числа:
- Цяло число n в интервала [1 … 100] – задава минималната и максималната координата на връх.
- Цяло число m в интервала [0 … 50 000] – задава минималната площ на генерираните правоъгълници.
- На конзолата трябва да се отпечатат описаните правоъгълници във формат като в примерите по-долу.
- Ако за числата n и m няма нито един правоъгълник, да се изведе “No”.
- Редът на извеждане на правоъгълниците е без значение.
| Вход | Изход | Вход | Изход |
|---|---|---|---|
| 1 2 |
(-1, -1) (0, 1) -> 2 (-1, -1) (1, 0) -> 2 (-1, -1) (1, 1) -> 4 (-1, 0) (1, 1) -> 2 (0, -1) (1, 1) -> 2 |
2 17 |
No |
| Вход | Изход |
|---|---|
| 3 36 |
(-3, -3) (3, 3) -> 36 |
Прочитаме входните параметри на функцията. Ще създадем и един брояч, в който ще пазим броя на намерените правоъгълници.
Изключително важно е да успеем да си представим задачата, преди да започнем да я решаваме. В нашия случай се изисква да търсим правоъгълници в координатна система. Нещото, което знаем е, че лявата точка винаги ще има координата х, по-малка от дясната. Съответно горната винаги ще има по-малка координата у от долната. За да намерим всички правоъгълници, ще трябва да направим цикъл, подобен на този от предходната задача, но този път не всеки следващ цикъл ще започва от следващото число, защото някои от координатите може да са равни (например left и top).
С променливите left и right ще следим координатите по хоризонталата, а с top и bottom - по вертикалата. Важното тук е да знаем кои координати кои са, за да можем да изчислим правилно страните на правоъгълника. Сега трябва да намерим лицето на правоъгълника и да направим проверка дали то е по-голямо или равно на m. Едната страна ще е разликата между left и right, а другата - между top и bottom. Тъй като координатите евентуално може да са разменени, ще ползваме абсолютни стойности. Отново добавяме и брояча в цикъла, като броим само четириъгълниците, които изписваме. Важно е да забележим, че поредността на изписване е left, top, right, bottom, тъй като така е зададено в условието.
Накрая принтираме “No”, ако не съществуват такива правоъгълници.
Тествайте решението си тук: https://judge.softuni.org/Contests/Practice/Index/939#11.