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

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

View on GitHub

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

Задатак A

Сваке године, последњег викенда у октобру, прелазимо са такозваног летњег на зимско рачунање времена. У ноћи између суботе и недеље, у 3 часа, часовнике „померамо“ за један час „уназад“.

Мали Лаза је те ноћи отишао на спавање пре поноћи, носећи на руци сат који приказује време по летњем рачунању времена. Током ноћи, Лаза се пробудио и видео да сат на његовој руци показује да је $S$ сати и $M$ минута.

Напишите програм који ће исписати колико је заправо било сати и минута у тренутку када се Лаза пробудио.

Опис улаза

У првом реду стандардног улаза налази се природни број $S$ $(0 \le S \le 8)$ из текста задатка.

У другом реду стандардног улаза налази се природни број $M$ $(0 \le M \le 59)$ из текста задатка.

Опис излаза

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


Решење
S = int(input())
M = int(input())

if S >= 3:
    S -= 1

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


Сат који Лаза носи није подешен приликом преласка са летњег на зимско рачунање времена, па након $3$ часа показује време које је за један сат испред стварног времена. Зато, ако сат показује мање од $3$ часа, промена времена се још није догодила и приказано време је тачно. Ако сат показује $3$ часа или више, прелазак на зимско рачунање времена се већ догодио, па је од приказаног броја сати потребно одузети $1$. Број минута се приликом промене времена не мења, па вредност M остаје иста. На крају се исписују тако добијени број сати и непромењени број минута. Временска и просторна сложеност решења су $\mathcal{O}(1)$.


Задатак B

На тренинг фудбалског клуба Слобода из Доњег Товарника дошло је $N$ играча. Жика је тренер овог фудбалског клуба и осмислио је посебан тренинг, који ће његове момке адекватно припремити за предстојећи дерби против фудбалског клуба Хајдук из Дивоша.

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

Напишите програм који ће, за задато $N$, исписати најмањи могући број играча по групама.

Опис улаза

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

Опис излаза

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


Решење
N = int(input())

for broj in range(2, N + 1):
    if N % broj == 0:
        print(broj)
        break
Текстуално објашњење


Пошто сви играчи морају бити распоређени у групе са једнаким бројем чланова, број играча у једној групи мора бити делилац укупног броја играча $N$. Такође, свака група мора имати бар два играча, а тражи се најмањи могући број играча по групи. Због тога се редом проверавају сви бројеви почевши од $2$ и тражи се први број који дели $N$ без остатка. Чим се пронађе такав број, он се исписује и петља се прекида наредбом break, јер је због редоследа провере то сигурно најмањи могући број играча по групи. Решење увек постоји, јер је и сам број $N$ његов делилац, што одговара случају у којем сви играчи чине једну групу. У најгорем случају, када је $N$ прост број, проверавају се сви бројеви од $2$ до $N$, па је временска сложеност $\mathcal{O}(N)$, док је просторна сложеност $\mathcal{O}(1)$.


Задатак C

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

Шаблон је ниска знакова која се састоји од малих слова енглеске абецеде и тачно једне звездице. Кажемо да назив датотеке одговара шаблону ако можемо изједначити шаблон са називом датотеке мењајући звездицу произвољном ниском малих слова енглеске абецеде, при чему је валидна и замена звездице празном ниском. На пример, речи abcd, ad и anestonestod одговарају шаблону a*d, док реч bcd не одговара овом шаблону.

Напишите програм који ће, за задати шаблон и називе датотека, одредити који називи одговарају шаблону, а који не.

Опис улаза

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

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

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

Опис излаза

У $N$ редова стандардног излаза исписати да ли назив $i$-те датотеке $(0 \le i \le N)$ одговара датом шаблону (исписати DA ако одговара, односно NE ако не одговара).


Решење
n = int(input())
pattern = input()

left, right = pattern.split('*')

for _ in range(n):
    filename = input()

    if (len(filename) >= len(left) + len(right)
            and filename.startswith(left)
            and filename.endswith(right)):
        print("DA")
    else:
        print("NE")
Текстуално објашњење


Пошто шаблон садржи тачно једну звездицу, он се помоћу split('*') дели на два дела: left, који се налази пре звездице, и right, који се налази после ње. Звездица може да представља произвољну ниску, укључујући и празну, па назив датотеке одговара шаблону ако почиње ниском left и завршава се ниском right. То се проверава помоћу функција startswith и endswith. Поред тога, назив датотеке мора имати бар len(left) + len(right) знакова, како се делови који одговарају почетку и крају шаблона не би преклапали. Ако су сва три услова испуњена, звездица може да представља све знакове који се налазе између делова left и right, па се исписује DA. У супротном се исписује NE. Пошто се сваки од $N$ назива датотека проверава једном, а његова дужина је највише $100$ знакова, решење је веома ефикасно. Ако максималну дужину ниске означимо са $L$, временска сложеност је $\mathcal{O}(N \cdot L)$, док је додатна просторна сложеност $\mathcal{O}(L)$.


Задатак 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)$ због чувања дужина блокова.