Основи програмирања

БРТСИ1300 / ОЕ1-ОП

View on GitHub

Основи програмирања: колоквијум 2025.

Задатак A

Дефинисати функцију proizvod2 која враћа производ два цела броја прослеђена у виду формалних параметара функције.

Опис улаза

Цели бројеви које треба помножити прослеђују се као аргументи функције.

Опис излаза

Вратити један цео број који представља производ улазних целих бројева.


Решење
def proizvod2(x, y):
    return x*y


Задатак B

Сунце кружи око центра Млечног пута, Земља кружи око Сунца, Месец кружи око Земље, вода кружи у природи, казаљка на сату се креће у круг, бубањ веш машине има кружни пресек и електрони у најпростијем моделу круже око центра атома. Тако је и најпростије решење свих саобраћајних проблема кружни ток.

Соћко се, низом несрећних околности, управо нашао у једном кружном току. Њега можемо посматрати као кружницу подељену на $N$ једнаких делова при чему је сваки део или заузет неким достављачем хране на бициклу (то ћемо означавати са “#”) или се баш Соћко налази у њему (то ћемо означавати са “+”) или се у њему не налази нико (то ћемо означавати са “.”).

Удаљеност Соћка до било ког достављача се дефинише као дужина мањег од два кружна лука између Соћка и достављача, изражена у броју једнаких делова.

Како је Соћко одговоран возач, жели да држи одређену удаљеност од достављача хране. Интересује га у датом тренутку који је описан, која је минимална удаљеност њега до неког достављача хране. Соћко је фокусиран на вожњу, тако да треба да му помогнете око рачунања ове минималне удаљености.

Опис улаза

У првој линији стандардног улаза се налази број $N$ који представља број једнаких делова на који је подељен кружни ток. У другој, и последњој, линији улаза налази се ниска дужине $N$ састављена од тачно једног карактера “+”, барем једног карактера “#” и произвољно много карактера “.”.

Опис излаза

На прву и једину линију стандардног излаза исписати један број који представља удаљеност Соћка до најближег достављача хране.


Решење
N = int(input())
s = input().strip()
p = s.index('+')
ans = N
for i in range(N):
    if s[i] == '#':
        d = abs(i - p)
        ans = min(ans, min(d, N - d))
print(ans)
Текстуално објашњење

Решење када се сви достављачи у ниској налазе десно од Соћка

Приметимо да ће достављач најближи Соћку бити први када се крећемо по кругу у једном од два различита смера, почевши од позиције на којој се Соћко налази ($s$). Најближи достављачи за два смера се могу поклапати, тј. уколико постоји само један достављач он ће бити најближи за оба смера кретања. У овом подзадатку један од та два достављача ће у ниској бити први са десне стране Соћка, који се налази на позицији $d_1$, а други ће бити последњи достављач у ниској, на позицији $d_2$. Све позиције можемо наћи једним проласком кроз дату ниску. Растојање између позиција $s$ и $d_1$ у једном смеру једнако је $d_1-s$ и представља најмање растојање између неког достављача и Соћка, када се у кругу крећемо у том смеру. За други смер је најмање растојање између $s$ и $d_2$, које се за тај смер рачуна по формули $N-d_2+s$. Решење задатка је мање од два израчуната растојања.

Решење када постоји само један достављач

Како постоји само један достављач, он ће уједно бити и најближи. Проласком кроз ниску налазимо и чувамо позицију на којој се налази Соћко ($s$), као и позицију достављача ($d$). Дужина једног кружног лука између Соћка и достављача једнака је $\lvert s-d\rvert$, а другог $N-\lvert s-d\rvert$. Решење задатка је мања од дужина та два лука.

Главно решење

Слично првом подзадатку, потребно је наћи најближег достављача Соћку за сваки од два смера кретања по кругу посебно. Проласком кроз ниску налазимо позицију $s$. За један смер се крећемо од позиције $s$ улево кроз ниску, до прве позиције на којој се налази достављач ($d_1$). Уколико при тражењу дођемо до почетка ниске, а нисмо одредили $d_1$, претрагу настављамо од позиције $N-1$ улево, пошто се позиције налазе на кругу (карактери у ниској су индексирани од $0$). Слично, за позицију најближег достављача при кретању у другом смеру ($d_2$) претрага се обавља од позиције $s$ удесно. Уколико се налазимо на позицији $N-1$, а нисмо пронашли позицију $d_2$, претрагу настављамо од позиције $0$ удесно. Растојање између $s$ и $d_1$ при кретању у одговарајућем смеру у кругу можемо добити бројањем позиција за које смо се померили при тражењу позиције $d_1$. Слично налазимо и растојање између $s$ и $d_2$ у одговарајућем смеру. Решење задатка је мање од та два растојања.

Други начин за решавање задатка је да се, након одређивања позиције Соћка у ниској, за сваког достављача израчуна растојање као у претходном подзадатку. Решење задатка је најмање од свих израчунатих растојања.

Временска сложеност: $O(N)$


Задатак C

Старогрчки математичар Никомах из Гераса дефинисао је следећу поделу природних бројева:

За делилац неког природног броја се каже да је прави ако су мањи од тог броја, а при његовом дељењу дају остатак нула.

Написати функцију classify која као аргумент прима један природан број, а враћа ниску idealan, ако је број савршен, obilan, ако је број обилан, односно oskudan, ако је број оскудан.

Опис улаза

Природан, односно ненегативан цео број који треба класификовати прослеђује се као аргумент функције.

Опис излаза

Вратити ниску idealan, obilan, или oskudan, у зависности од збира делилаца.


Решење
def classify(num):
    total, count = 0, 1
    while count < num:
        if num % count == 0:
            total += count
        count += 1
    if total == num:
        return "idealan"
    if total < num:
        return "oskudan"
    if total > num:
        return "obilan"

Текстуално објашњење

У суштини, неопходно је за сваки број од 1 до num (може и до (num/2)+1, јер након тога сигурно нећемо наћи делилац) проверити да ли је он делилац броја num и ако јесте додати га у променљиву total која је на почетку 0. На крају се само провери однос променљиве total са бројем num и на основу тога се врати одређено решење.


Задатак D

Три пријатеља – Дон Хуан, Селектор и Варијације – донели су на излет одређен број јабука. Дон Хуан има $a$ јабука, Селектор $b$, а Варијације $c$.

Током излета играју једноставну игру: кад год неко од њих подигне руку, то значи да жели јабуку, и друга двојица морају да му дају по једну јабуку. Све радње обављају тимски и нико се не буни — правила су јасна. Пазите да је могуће да неки од пријатеља има негативан број јабука након што је дао јабуку.

После било ког броја потеза, занима их следеће: Да ли је могуће да, уз паметно бирање ко диже руку у којим тренуцима, сва тројица на крају заврше са истим бројем јабука?

Уколико им помогнеш да одговоре на то питање, можда ти дају пар јабука које подстичу специјалне вештине за решавање задатака.

Опис улаза

У првој и јединој линији стандардног улаза дата су три природна броја $a$, $b$ и $c$ - број јабука сваког од другара.

Опис излаза

Потребно је исписати једну линију стандардног излаза. Уколико је одговор на њихово питање могуће исписати DA, у супротном исписати NE.


Решење
a,b,c=map(int,input().split())
if (a-b)%3==0 and (b-c)%3==0:
    print("DA")
else:
    print("NE")

Текстуално објашњење

Решење када $a,b,c \le 200$.

На почетку, Дон Хуан има $a$ јабука, Селектор има $b$ јабука, а Варијације има $c$ јабука.

Назовимо процес у ком један пријатељ подигне руку и добије јабуке његовом операцијом.

Приметимо да редослед операција није битан, јер ће сваки пријатељ након неких операција имати $k = x + 2 \cdot y - z$, где је:

$k$: број јабука које неки пријатељ има након неких операција,

$x$: број јабука које је имао пре операција,

$y$: број сопствених операција,

$z$: број туђих операција.

$k$ очигледно не зависи од редоследа операција, јер ништа у једначини не зависи од редоследа операција.

Још једна ствар коју можемо приметити јесте да ако сваки пријатељ сазове по једну операцију, то је исто као да је нико није сазвао. Ово значи да ако постоји начин да сва тројица имају једнак број јабука на крају, могуће је то одрадити тако да само двојица раде операције. Пошто је сопствена операција једини начин да се сопствени број јабука повећа, очигледно је да ће два пријатеља са најмањим бројем јабука једини извршавати операције.

Претпоставимо да $a \le b \le c$, ако није можемо их само заменити тако да ова неједнакост важи.

Сад, ако прво радимо операције да повећамо $b$, па онда да повећамо $a$, очигледно након операција на $b$, $b$ и $c$ морају да буду једнаки, јер ће након тога операције на $a$ смањивати оба броја подједнако.

Можемо симулирати операције на $b$ све док не буде важило $b \ge c$. Ако $b > c$ очигледно је одговор НЕ, јер ће операцијама на $a$ оба подједнако да се смање, па никад неће бити једнаки. Ако $b = c$, симулирамо операције на $a$, све док не буде важило $a \ge b$, то јест $a \ge c$. Сад, из истог разлога, ако је $a > b$ одговор је НЕ, а ако је $a = b = c$, одговор је очигледно ДА.

Једном операцијом, смањићемо разлику између бројева за $3$, па је највећи могући број операција $a+b$.

Временска сложеност: $O(a+b)$. Просторна сложеност: $O(1)$.

Главно решење

Приметимо да процес који смо раније радили не морамо да симулирамо, већ можемо брже да израчунамо.

Наиме, изједначавање $b$ и $c$ ће се десити ако и само ако је $c - b$ дељиво са $3$, јер једна операција повећава $b$ за $2$, а смањује $c$ за $1$.

Ако није дељиво са $3$, очигледно ће одговор бити НЕ. Ако јесте, можемо закључити да ћемо урадити $(c-b)/3$ операција на $b$. Њих можемо све одједном применити тако што одузмемо $(c-b)/3$ од $a$ и $c$, а додамо $2 \cdot (c-b)/3$ на $b$.

Сад важи $b = c$, и свака операција на $a$ ће смањити $b$ и $c$ подједнако. Исто као за $b$ и $c$, морамо да проверимо да ли је $b-a$ дељиво са $3$. Ако јесте, не морамо ни да радимо операције, јер знамо да ће их оне изједначити, па да је одговор ДА, ако није, одговор је НЕ.

Ово решење је довољно да код прође, али можемо га учинити још једноставнијим.

Наиме, резултат операције на $a$ је: $a$ постаје $a+2$, $b$ постаје $b-1$, $c$ постаје $c-1$. Приметимо да се међусобне разлике између свака два елемента остале исте по модулу $3$. Такође приметимо из претходно наведеног процеса, да нам је одговор НЕ, само ако у неком тренутку разлика између нека два елемента није дељива са $3$.

Ово нас доводи до закључка да разлика свака два елемента мора бити дељива са $3$ на почетку јер се то операцијама не мења. Ако јесте, показали смо како се решење добија, али довољно је само исписати ДА. Ако није, показали смо да је немогуће добити решење, тако да се исписује НЕ.

Временска и просторна сложеност: $O(1)$.


Задатак E

На неком паркингу дужине n појединачних паркинг места могу се паркирати аутомобили са ознаком <>, који заузимају по два паркинг места, и мотоцикли са ознаком %, који заузимају по једно паркинг место.

Написати функцију parkiranje која као аргумент прима један природан број n, који представља број места за паркирање, а враћа број могућих начина упаркиравања.

Опис улаза

Природан, односно ненегативан цео број који представља број суседних паркинг места.

Опис излаза

Природан, односно ненегативан цео број који представља број начина да се аутомобили и мотоцикли упаркирају.


Решење
def count_park(n):
    if n < 0:
        return 0
    if n == 0:
        return 1
    return 2 * count_park(n-1) + count_park(n-2)
Текстуално објашњење

Функција count_park(n) рачуна број могућих начина паркирања на паркингу са n узастопних паркинг места. Решење је рекурзивно и заснива се на анализи шта се може догодити на првом паркинг месту.

Постоје три могућности:

  1. Прво место остане празно (.).
    У том случају преостаје n - 1 место, које се може попунити на count_park(n-1) начина.

  2. На првом месту се паркира мотоцикл (%), који заузима једно паркинг место.
    И у овом случају остаје n - 1 место, које се може попунити на count_park(n-1) начина.

  3. На прва два места се паркира аутомобил (<>), који заузима два паркинг места.
    Тада остаје n - 2 места, која се могу попунити на count_park(n-2) начина.

Прве две могућности дају укупно 2 · count_park(n-1) начина, а трећа додаје још count_park(n-2) начина. Због тога важи рекурзивна формула:

count_park(n) = 2 · count_park(n-1) + count_park(n-2)

Основни случајеви су:

  • count_park(0) = 1, јер постоји тачно један начин да се распореди паркинг са нула места (празан распоред),
  • count_park(n) = 0 за n < 0, јер не постоји важећи распоред са негативним бројем места.