Глава 8.1. Подготовка за практически изпит – част I

В настоящата глава ще разгледаме няколко задачи с ниво на трудност, каквото може да очаквате от задачите на практическия изпит по “Основи на програмирането”. Ще преговорим и упражним всички знания, които сме придобили от настоящата книга и през курса "Programing Basics".

Видео

Гледайте видео-урок по тази глава тук: https://www.youtube.com/watch?v=OYuT5_j1OVE.

Практически изпит по “Основи на програмирането”

Курсът "Programing Basics" приключва с практически изпит. Включени са 6 задачи, като ще имате 4 часа, за да ги решите. Всяка от задачите на изпита ще засяга една от изучаваните теми по време на курса. Темите на задачите са както следва:

  • Задача с прости сметки (без проверки)
  • Задача с единична проверка
  • Задача с по-сложни проверки
  • Задача с единичен цикъл
  • Задача с вложени цикли (чертане на фигурка на конзолата)
  • Задача с вложени цикли и по-сложна логика

Система за онлайн оценяване (Judge)

Всички изпити и домашни се тестват автоматизирано през онлайн Judge система: https://judge.softuni.org. За всяка от задачите има открити (нулеви) тестове, които ще ви помогнат да разберете какво се очаква от задачата и да поправите грешките си, както и състезателни тестове, които са скрити и проверяват дали задачата ви работи правилно. В Judge системата се влиза с вашия softuni.bg акаунт.

Как работи тестването в Judge системата? Качвате сорс кода и от менюто под него избирате да се изпълни като Python програма. Програмата бива тествана с поредица от тестове, като за всеки успешен тест получавате точки.

Задачи с прости пресмятания

Първата задача на практическия изпит по “Основи на програмирането” обхваща прости пресмятания без проверки и цикли. Ето няколко примера:

Задача: лице на триъгълник в равнината

Триъгълник в равнината е зададен чрез координатите на трите си върха. Първо е зададен върхът (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 ще е под или над страната на триъгълника, ще използваме абсолютните стойности на разликата, за да получаваме винаги положителни числа, понеже една отсечка не може да има отрицателна дължина:

По познатата ни от училище формула за намиране на лице на триъгълник, ще пресметнем лицето:

Единственото, което остава, е да отпечатаме лицето на конзолата:

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

Тествайте решението си тук: https://judge.softuni.org/Contests/Practice/Index/1059#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(…), за да закръглим получения резултат нагоре. Не забравяме да добавим и import math в началото на работния файл, за да може функцията math.ceil(…) да работи. Когато тухлите могат да се пренесат с точен брой курсове, делението ще връща точно число и няма да има нищо за закръгляне. Съответно, когато не е така, резултатът от делението ще е броя на точните курсове, но с десетична част. Десетичната част ще се закръгли нагоре и така ще се получи нужният 1 курс за оставащите тухлию;

Накрая принтираме резултата на конзолата:

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

Тествайте решението си тук: https://judge.softuni.org/Contests/Practice/Index/1059#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

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

Първо прочитаме входните данни:

Тъй като не знаем коя точка е от ляво и коя е от дясно, ще си направим две променливи, които да ни отбелязват това. Тъй като лявата точка е винаги тази с по-малката х координата, ще ползваме функцията min(…), за да я намерим. Съответно, дясната е винаги тази с по-голяма х координата - за нея ще ползваме max(…). Ще намерим и разстоянието от точката x до двете точки. Понеже не знаем положението им една спрямо друга, ще използваме функцията abs(…), за да получим положителен резултат:

По-малкото от двете разстояния ще намерим ползвайки min(…):

Остава да намерим дали точката е на линията или извън нея. Точката ще се намира на линията винаги, когато тя съвпада с някоя от другите две точки или х координатата ѝ се намира между тях. В противен случай, точката се намира извън линията. След проверката изкарваме едното от двете съобщения ("in" или "out"), спрямо това кое условие е удовлетворено:

Накрая принтираме разстоянието, намерено преди това:

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

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

Задача: точка във фигура

Да се напише програма, която проверява дали дадена точка (с координати x и y) е вътре или извън следната фигура:

Вход

От конзолата се четат две цели числа (по едно на ред): x и y.

Всички входни числа са цели и в диапазона [-1000 … 1000].

Изход

Да се отпечата на конзолата "in" или "out" – дали точката е вътре или извън фигурата (на контура е вътре).

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

Вход Изход Вход Изход
8
-5
in 6
-3
in
Вход Изход Вход Изход
11
-5
out 11
2
out

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

За да разберем дали точката е във фигурата, ще разделим фигурата на 2 четириъгълника:

Достатъчно условие е точката да се намира в един от тях, за да се намира във фигурата.

Четем от конзолата входните данни:

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

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

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

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

Задачи с по-сложни проверки

Третата задача на практическия изпит по “Основи на програмирането” включва няколко вложени проверки съчетани с прости пресмятания. Ето няколко примера:

Задача: дата след 5 дни

Дадени са две числа 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 месеца. Това става, като добавим форматиращ стринг %02d за втория елемент:

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

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

Задача: суми от 3 числа

Дадени са 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":

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

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

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

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

Задачи с единичен цикъл

Четвъртата задача от практическия изпит по “Основи на програмирането” включва единичен цикъл с проста логика в него. Ето няколко примера:

Задача: суми през 3

Дадени са n цели числа a1, a2, …, an. Да се пресметнат сумите:

  • sum1 = a1 + a4 + a7 + … (сумират се числата, започвайки от първото със стъпка 3).
  • sum2 = a2 + a5 + a8 + … (сумират се числата, започвайки от второто със стъпка 3).
  • sum3 = a3 + a6 + a9 + … (сумират се числата, започвайки от третото със стъпка 3).

Вход

Входните данни се четат от конзолата. На първия ред стои цяло число n (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 към третата:

Накрая, ще отпечатаме резултата на конзолата в изисквания от условието формат:

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

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

Задача: поредица от нарастващи елементи

Дадена е редица от n числа: a1, a2, , an. Да се пресметне дължината на най-дългата нарастваща поредица от последователни елементи в редицата от числа.

Вход

Входните данни се четат от конзолата. На първия ред стои цяло число n (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 е броя числа, които ще получим от конзолата. В count_current_longest ще запазваме броя на елементите в нарастващата подредица, която броим в момента. Напр. при редицата: 5, 6, 1, 2, 3 count_current_longest ще бъде 2, когато сме стигнали втория елемент от броенето (5, 6, 1, 2, 3) и ще стане 3, когато стигнем последния елемент (5, 6, 1, 2, 3), понеже нарастващата редица 1, 2, 3 има 3 елемента. Ще използваме count_longest, за да запазим най-дългата нарастваща редица. Останалите променливи, който ще използваме, са a - числото, на което се намираме в момента, и a_prev - предишното число, което ще сравним с a, за да разберем дали редицата расте.

Започваме да обхождаме числата и проверяваме дали настоящото число а е по-голямо от предходното a_prev. Ако това е изпълнено, значи подредицата е нарастваща и трябва да увеличим броя ѝ с 1. Това запазваме в променливата, която следи дължината на редицата, в която се намираме в момента, а именно - count_current_longest. Ако числото а не е по-голямо от предходното, това означава, че започва нова подредица и трябва да стартираме броенето от 1. Накрая, след всички проверки, a_prev става числото, което използваме в момента, и започваме цикъла от начало със следващото въведено а.

Ето и примерна реализация на описания алгоритъм:

Остава да разберем коя от всички редици е най-дълга. Това ще направим с проверка в цикъла дали редицата, в която се намираме в момента, е станала по-дълга от дължината на най-дългата намерена до сега. Целият цикъл ще изглежда така:

Накрая принтираме дължината на най-дългата намерена редица:

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

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

Задачи за чертане на фигурки на конзолата

Петата задача от практическия изпит по “Основи на програмирането” изисква използване на един или няколко вложени цикъла за рисуване на някаква фигурка на конзолата. Може да се изискват логически размишления, извършване на прости пресмятания и проверки. Задачата проверява способността на студентите да мислят логически и да измислят прости алгоритми за решаване на задачи, т.е. да мислят алгоритмично. Ето няколко примера за изпитни задачи:

Задача: перфектен диамант

Да се напише програма, която прочита от конзолата цяло число n и чертае перфектен диамант с размер n като в примерите по-долу.

Вход

Входът е цяло число n в интервала [1 … 1000].

Изход

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

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

Вход Изход Вход Изход
2  * 
*-*
 * 
3   *  
 *-* 
*-*-*
 *-* 
  *  
Вход Изход Вход Изход
4    *   
  *-*  
 *-*-* 
*-*-*-*
 *-*-* 
  *-*  
   *   
5     *    
   *-*   
  *-*-*  
 *-*-*-* 
*-*-*-*-*
 *-*-*-* 
  *-*-*  
   *-*   
    *    

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

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

Първо прочитаме числото n от конзолата:

Започваме да рисуваме горната половина на диаманта. Ясно виждаме, че всеки ред започва с няколко празни места и *. Ако се вгледаме по-внимателно, ще забележим, че празните места са винаги равни на n - броя на реда (на първия ред са n-1, на втория - n-2 и т.н.) Ще започнем с това да нарисуваме броя празни места, както и първата звездичка. Нека не забравяме да използваме print(…, end='') вместо само print(…), за да оставаме на същия ред. На края на реда пишем print(), за да преминем на нов ред. Забележете, че започваме да броим от 1, а не от 0. След това ще остане само да добавим няколко пъти -*, за да довършим реда.

Ето фрагмент от кода за начертаване на горната част на диаманта:

Остава да довършим всеки ред с нужния брой -* елементи. На всеки ред трябва да добавим i - 1 такива елемента (на първия 1-1 -> 0, на втория -> 1 и т.н.)

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

За да изрисуваме долната част на диаманта, трябва да обърнем горната на обратно. Ще броим от n - 1, тъй като ако започнем от n, ще изрисуваме средния ред два пъти. Не забравяйте да добавите reversed(…) на range(…) на главния цикъл.

Ето го и кода за начертаване на долната част на диаманта:

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

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

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

Задача: правоъгълник със звездички в центъра

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

Вход

Входът е цяло число n в интервала [2 … 1000].

Изход

На конзолата трябва да се отпечата правоъгълникът като в примерите.

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

Вход Изход Вход Изход
2 %%%%
%**%
%%%%
3 %%%%%%
%    %
% ** %
%    %
%%%%%%
Вход Изход Вход Изход
4 %%%%%%%%
%      %
%  **  %
%      %
%%%%%%%%
5 %%%%%%%%%%
%        %
%        %
%   **   %
%        %
%        %
%%%%%%%%%%

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

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

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

От дадените примери виждаме, че средата на фигурата винаги има нечетен брой редове. Забелязваме, че когато е зададено четно число, броят на редовете е равен на предишното нечетно (2 -> 1, 4 -> 3 и т.н.). Създаваме променлива, която представлява броя редове, които ще има нашият правоъгълник, и я коригираме, ако числото n е четно. След това ще нарисуваме правоъгълника без звездичките. Всеки ред има за начало и край символа % и между тях 2 * n - 2 празни места (ширината е 2 * n и вадим 2 за двата процента в края). Не забравяйте да преместите кода за последния ред след цикъла:

Можем да стартираме и тестваме кода до тук. Всичко без двете звездички в средата трябва да работи коректно.

Сега остава в тялото на цикъла да добавим и звездичките. Ще направим проверка дали сме на средния ред. Ако сме на средния (това ще проверим като сравним i с floor(num_rows / 2)), ще рисуваме реда заедно със звездичките, ако не - ще рисуваме нормален ред. Не забравяйте да добавите from math import floor в началото на работния файл, за да може да използваме функцията floor(…). Редът със звездичките има n - 2 празни места (n е половината дължина и махаме звездичката и процента), две звезди и отново n - 2 празни места. Двата процента в началото и в края на реда ги оставяме извън проверката:

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

Тествайте решението си тук: https://judge.softuni.org/Contests/Practice/Index/1059#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 са равни), вторият цикъл няма да се изпълни и няма да се разпечата нищо на конзолата.

Аналогично, остава да реализираме по същия начин вложените цикли и за четири числа. Ще добавим и увеличаване на брояча (count), който инициализирахме в началото, за да знаем дали съществува такава редица:

Накрая ще проверим дали броячът е равен на 0 и съответно ще принтираме "No" на конзолата, ако е така:

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

Тествайте решението си тук: https://judge.softuni.org/Contests/Practice/Index/1059#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", ако не съществуват такива правоъгълници:

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

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

results matching ""

    No results matching ""