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

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

View on GitHub

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

Задатак A

Група пријатеља игра једну познату математичку игру. На почетку игре пријатељи бирају два природна броја $a$ и $b$ насумичним одабиром. Победник је особа која ће успети да претвори број $a$ у број $b$ користећи најмањи број операција.

Свима је познато да су допуштене следеће две операције:

Време пролази. Влада напета тишина, сви су удубљени у размишљање, покушавајући да пронађу најбоље решење. Минути се претварају у сате.

Одједном, прекидате тишину и самоуверено узвикујете: „Могу претворити $a$ у $b$ у само _ корака!”

Погледи се окрећу према Вама. Нико не може да верује. Али, неколико тренутака касније свима постаје јасно - готово је, нико неће успети да надмаши Ваше решење. Победили сте.

Опис улаза

У првом и једином реду стандардног улаза налазе се два природна броја $a$ и $b$ ($1 \le a$, $b \le 100$), бројеви које су пријатељи одабрали пре почетка игре.

Опис излаза

У првом и једином реду стандардног излаза испишите један број - најмањи број операција потребних да се број $a$ претвори у број $b$.


Решење
a, b = list(map(int, input().split()))

if a == b:
    print(0)
elif a < b or a % b == 0:
    print(1)
else:
    print(2)
Текстуално објашњење


Решење се заснива на разматрању свих могућих случајева. Ако су бројеви $a$ и $b$ једнаки, није потребно извршити ниједну операцију, па је одговор $0$. Ако је $a<b$, број $a$ се може претворити у $b$ једном операцијом увећавања, тако што му се дода $b-a$. Такође, ако је $a>b$, али је $a$ дељиво са $b$, довољна је једна операција дељења: број $a$ се дели са $a/b$ и директно се добија $b$. Зато услов a < b or a % b == 0 означава све случајеве у којима је довољна једна операција. У свим преосталим случајевима важи $a>b$, а $a$ није дељиво са $b$, па није могуће доћи до $b$ једном операцијом: увећавањем би се добио број већи од $a$, док се дељењем не може директно добити $b$. Ипак, увек су довољне две операције. На пример, $a$ се најпре може увећати до неког његовог умношка који је дељив са $b$, а затим поделити одговарајућим бројем тако да се добије $b$. Због тога је у овом случају одговор $2$. Пошто се врши само неколико поређења и аритметичких операција, временска и просторна сложеност решења су $\mathcal{O}(1)$.


Задатак B

Након серије (не)успеха на претходним такмичењима, Владимир је одлучио да се пријави на чувени квиз „Најслабија карика”. У овој напетој емисији учествује $n$ такмичара поређаних у низ с лева на десно, а међу њима је и Владимир.

Правила квиза су сурова. Након сваког од $n - 1$ кругова, праћених оштрим питањима водитељa, Николе Које, попут: „Ко ће пету рунду гледати од куће, ако му укућани већ нису разбили телевизор од нервозе?”, „Ко неће скакати у вис од среће?” и „Како се пише име такмичара који следећи излази из овог квиза?”, један такмичар испада. Игра се немилосрдно наставља све док на сцени не остане само један, последњи такмичар - победник квиза.

Емисија је давно завршена, а Ви нисте стигли да је гледате уживо. Међутим, у рукама држите тајанствени запис од $n - 1$ бројева који до детаља описује ко је испао у ком кругу. Број $a_i$ Вам открива који је по реду такмичар с лева испао у $i$-том кругу.

Такмичари су на почетку означени бројевима од 1 до $n$ с лева на десно. Ваш задатак је да одредите ко је победник.

Опис улаза

У првом реду налази се природан број $n$ ($2 \le n \le 100$), који представља почетни број такмичара. Тамичари су на почетку означени бројевима од $1$ до $n$ с лева на десно.

У другом реду налази се $n - 1$ природних бројева $a_i$ ($1 \le a_i \le n + 1 - i$) који описују позицију такмичара с лева који испада у сваком кругу.

Опис излаза

У првом и једином реду испишите један број - почетну ознаку такмичара који је победио у квизу.


Решење
n = int(input())
takmicari = []
for i in range(1, n + 1):
  takmicari.append(i)

p = list(map(int, str(input()).split()))
for x in p:
  del takmicari[x - 1]

print(takmicari[0])
Текстуално објашњење


Решење симулира редослед испадања такмичара. На почетку се формира листа takmicari која садржи бројеве од $1$ до $n$, односно почетне ознаке свих такмичара поређаних с лева на десно. Затим се редом обрађују бројеви из низа p. Сваки број $x$ означава да у текућем кругу испада $x$-ти такмичар с лева међу онима који су још увек у игри. Пошто се позиције у задатку броје почевши од $1$, а индекси листе у Пајтону почевши од $0$, одговарајући такмичар се уклања наредбом del takmicari[x - 1]. Након уклањања, преостали такмичари аутоматски задржавају исправан међусобни редослед, па се следећи податак о испадању може применити на тако измењену листу. Након $n-1$ кругова у листи остаје тачно један такмичар, па се његова почетна ознака, која се налази на позицији takmicari[0], исписује као победник квиза. Пошто брисање елемента из Пајтон листе може захтевати померање преосталих елемената, временска сложеност овакве симулације је $\mathcal{O}(n^2)$, док је просторна сложеност $\mathcal{O}(n)$.


Задатак C

Ђоле је током лета добио праксу у једној великој ИТ компанији. Та компанија се бави огромном базом података која се састоји од $N$ редова и $M$ колона.

Свог првог радног дана Ђоле је добио укупно $Q$ упита. Сваки упит састоји се од $M$ бројева. Међутим, неки бројеви су били изгубљени током преноса, па су означени бројем -1. Ђолета сада занима колико редова базе података одговара упиту, тј. колико редова базе података има исте бројеве као и упит, искључујући -1.

На пример, ако је упит облика -1 3 2, тада је потребно пребројати редове базе података који имају било који број у 1. колони, број 3 у 2. колони и број 2 у 3. колони.

Будући да је тек почео с праксом, Ђоле вас моли за помоћ. Помозите му и одговорите на упите!

Опис улаза

У првом реду стандардног улаза налазе се бројеви $N$ ($1 \le N \le 10^3$) и $M$ ($1 \le M \le 10^3$), величина базе података.

У следећих $N$ редова налази се по $M$ бројева $A_{ij}$ ($1 \le A_{ij} \le 10^6$), садржај базе података.

У следећем реду налази се $Q$ ($1 \le Q \le 50$), број упита.

У следећих $Q$ редова налази се по $M$ бројева $B_{kj}$ ($B_{kj} = -1$ или $1 \le B_{kj} \le 10^6$), опис $k$-тог упита.

Опис излаза

У $Q$ редова налази се $X_k$, одговор на $k$-ти упит из текста задатака.


Решење
N, M = map(int, input().split())

baza = []
for _ in range(N):
    red = list(map(int, input().split()))
    baza.append(red)

Q = int(input())

for _ in range(Q):
    upit = list(map(int, input().split()))
    
    brojac_poklapanja = 0
    
    for red in baza:
        odgovara = True
        
        for j in range(M):
            if upit[j] != -1 and upit[j] != red[j]:
                odgovara = False
                break
                
        if odgovara:
            brojac_poklapanja += 1
            
    print(brojac_poklapanja)
Текстуално објашњење


Најпре се чита и чува цела база података као матрица од $N$ редова и $M$ колона. Затим се сваки упит обрађује посебно тако што се проверава сваки ред базе и утврђује да ли он одговара задатом упиту. За сваки ред променљива odgovara се поставља на True, а затим се редом пореде вредности у свим колонама. Ако је вредност упита у некој колони једнака -1, вредност у тој колони није битна и поређење се наставља. У супротном, вредност из упита мора бити једнака одговарајућој вредности из посматраног реда базе. Чим се пронађе колона у којој се ове вредности разликују, знамо да тај ред не одговара упиту, па се odgovara поставља на False и прекида се даља провера тог реда. Ако након провере свих потребних колона odgovara остане True, бројач одговарајућих редова се увећава за један. Након што се провере сви редови базе, добијени број се исписује као одговор на тренутни упит.

За сваки од $Q$ упита у најгорем случају проверава се свих $N$ редова и свих $M$ колона, па је временска сложеност $\mathcal{O}(Q \cdot N \cdot M)$. База садржи $N \cdot M$ бројева и цела се чува у меморији, па је просторна сложеност $\mathcal{O}(N \cdot M)$.


Задатак D

Лаза је одлучио да ће бити вредан током лета и вежбати математику, како би је већ у августовском року коначно положио! Како би се загрејао и припремио за мукотрпно вежбање задатака, задао је себи задатак да заокругљује природне бројеве на степене броја десет.

Да би заокруглио природни број $a$ на најближи степен броја десет (означимо га са $10^b$, где је $b$ такође природан број), Лаза прво пронађе $b$-ту цифру са десне стране броја $a$. Означимо ту цифру са $x$.

Ако је $x \ge 5$, Лаза дода $10^b$ броју $a$.

Затим, Лаза постави $b$-ту и све цифре десно од $b$-те добијеног броја на $0$.

На пример, рецимо да Лаза жели да заокругли број $a = 456$ на најближу стотину $(10^b = 10^2)$. Он би прво пронашао другу цифру здесна, што је $x = 5$. Како је $x \ge 5$, Лаза додаје $10^2 = 100$ на број $456$ и добија број $556$. На крају, другу ($b$-ту) и прву цифру добијеног броја поставља на нулу и добија $500$.

Са друге стране, да је Лаза иницијално одабрао да заокругли број $a = 446$ на најближу стотину $(10^b = 10^2)$, резултат би био $400$.

Након што је погледао шта је Лаза вежбао, Фића је помислио да је изумео нови начин заокругљивања — ланчано заокругљивање. Да би ланчано заокруглио број на најближи степен броја десет, Фића ће прво заокруглити број на најближу десетицу, затим стотину итд. све до најближег степена броја десет, $10^b$.

Лаза мисли да Фићин поступак заокругљивања није добар, али је превише заокупљен вежбањем математике да би проверио, па је замолио вас да избројите колико је укупног природних бројева $y$, $2 \le y \le N$ $(1 \le N \le 10^9)$, таквих да заокругљивање броја $y$ на најближи степен броја десет, $10^P$, даје различит резултат у односу на ланчано заокругљивање овог броја на најближи степен броја десет, $10^P$. Подразумева се да је $P$ најмањи могући природан број за који важи да је $10^P \ge y$.

Опис улаза

Сваки тест пример састоји се из више примера.

У првом реду стандардног улаза налази се број $T$ $(1 \le T \le 10^5)$, број примера у оквиру једног тест примера.

У првом и једином реду сваког примера у оквиру једног тест примера налази се број $N$, број из текста задатка. Подразумева се да су бројеви $N$ у свим примерима у оквиру једног тест примера различити.

Опис излаза

У $T$ редова на стандардном излазу исписати одговор на сваки од $T$ примера у оквиру датог тест примера.


Решење
def alg(N):
    digits = 0
    while 10**digits < N:
        digits += 1
    
    answer = 0
    for curdigits in range(1, digits+1):
        upper = int('5'+'0'*(curdigits-1))-1
        upper = min(N, upper)  
        lower = int('4'*curdigits)
        answer += max(0, upper - lower)
    return answer
 
T = int(input().strip())
for _ in range(T):
    N = int(input().strip())
    print(alg(N))
Текстуално објашњење


Није потребно посебно симулирати оба начина заокругљивања за сваки број до $N$. Кључно је уочити да се резултати разликују само за одређене интервале бројева. За број са $d$ цифара, обично заокругљивање на $10^d$ даће $0$ ако је број мањи од $5\cdot10^{d-1}$. Код ланчаног заокругљивања, међутим, цифра $5$ може настати постепеним заокругљивањем нижих цифара. Најмањи број код којег се то дешава има све цифре једнаке $4$. На пример, број $44$ се обично заокругљује на $0$, али се ланчано најпре заокругљује на $40$, затим на $0$, па ту још нема разлике; прва разлика за двоцифрене бројеве настаје код $45$: ланчано даје $45\rightarrow50\rightarrow100$, док директно заокругљивање на $100$ даје $0$. Зато су за $d$ цифара интересантни бројеви строго већи од броја састављеног од $d$ четворки, а мањи од $5\cdot10^{d-1}$. На пример, за три цифре то су бројеви од $445$ до $499$.

Програм зато за сваки могући број цифара curdigits формира доњу границу lower као број састављен искључиво од цифара $4$, док је upper највећи број мањи од $5\cdot10^{curdigits-1}$, односно број облика $499…9$. Горња граница се додатно ограничава са $N$, јер се броје само бројеви који нису већи од задате вредности. Број одговарајућих вредности у том интервалу добија се као upper - lower, пошто се сама доња граница не рачуна. Функција овај број додаје одговору за сваку могућу дужину броја.

Пошто је $N\le10^9$, постоји свега десетак могућих бројева цифара, па алгоритам за сваки тест пример извршава веома мали број корака. Уопштено, временска сложеност је $\mathcal{O}(\log N)$, док је просторна сложеност $\mathcal{O}(1)$.


Задатак E

Опште је познато да је Гоца највећи љубитељ биљака, а нарочито цветница. Ове године је одлучила да обогати свој врт цвећем које многи сматрају најлепшим — ружама. Засадила је $N$ ружа у једном реду $(1 \le N \le 3 \cdot 10^5)$. Нажалост, није приметила да су неке од ружа још пре сађења биле заражене биљним вашима.

Дакле, иницијално су поједине од $N$ ружа засађених у реду инфициране. Сваке ноћи, биљне ваши нападају по једну ружу са леве и десне стране (уколико постоје), у непосредној близини заражених ружа. Једном када се ружа зарази, остаје инфицирана.

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

Опис улаза

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

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

Опис излаза

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


Решење
n = int(input())
s = input().strip()

segments = []
region = 0

for ch in s:
    if ch == '1':
        region += 1
    else:
        if region > 0:
            segments.append(region)
        region = 0

if region > 0:
    segments.append(region)

answer = s.count("1")

for window in range(1, n + 1, 2):
    infected = 0
    possible = True

    for i, block in enumerate(segments):
        is_left_end = (i == 0 and s[0] == '1')
        is_right_end = (i == len(segments) - 1 and s[-1] == '1')

        if is_left_end or is_right_end:
            if window > 2 * block - 1:
                possible = False
                break
        else:
            if window > block:
                possible = False
                break

        infected += (block + window - 1) // window

    if not possible:
        break

    answer = min(answer, infected)

print(answer)
Текстуално објашњење


Најпре се ниска дели на непрекидне блокове заражених ружа, односно узастопних јединица. Дужине ових блокова чувају се у листи segments. Пошто је посматрано стање настало након истог броја ноћи за све руже, свака ружа која је била заражена на почетку могла је до тренутка посматрања да зарази исти број ружа са обе своје стране. Зато се испробавају различите могуће величине области коју је могла да зарази једна почетно заражена ружа. Та величина је означена променљивом window и увек је непарна: $1,3,5,\ldots$. На пример, window = 1 одговара стању без ширења заразе, window = 3 једној протеклој ноћи, а window = 5 двема протеклим ноћима.

За сваку вредност window проверава се да ли је могуће добити све уочене блокове заражених ружа. Ако се блок налази у унутрашњости реда, окружен је незараженим ружама, па зараза није смела да стигне изван његових граница. Зато window не сме бити већи од дужине тог блока. Са друге стране, ако блок додирује леви или десни крај реда, ширење заразе са те стране није ограничено незараженом ружом, па је дозвољена већа вредност window. За блок дужине block на крају реда услов је window <= 2 * block - 1.

Када је нека вредност window могућа, израчунава се најмањи број почетно заражених ружа потребних за сваки блок. Једна почетно заражена ружа може да покрије највише window узастопних заражених позиција, па је за блок дужине block потребно $\lceil block/window\rceil$ почетно заражених ружа. У коду се ово целобројно израчунава изразом (block + window - 1) // window. Сабирањем ових вредности за све блокове добија се укупан број почетно заражених ружа за посматрани број протеклих ноћи, а у answer се чува најмања добијена вредност. Почетно се поставља answer = s.count("1"), што одговара случају у којем није протекла ниједна ноћ и све тренутно заражене руже су биле заражене од почетка.

Испробавају се непарне вредности window све док се не пронађе она за коју бар један блок више не може да задовољи услове. Како се даљим повећавањем window ситуација не може поново поправити, претрага се тада прекида. Иако постоји петља кроз могуће вредности window, она се зауставља чим window постане превелик за најограниченији блок. У најгорем случају, када постоји само један велики блок, листа segments има један елемент, док код великог броја малих блокова постоји веома мало могућих вредности window. Због тога је укупна временска сложеност $\mathcal{O}(N)$, а просторна сложеност $\mathcal{O}(N)$ због чувања дужина блокова.