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

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

View on GitHub

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

Задатак A

Написати програм који, за задато $n$, на стандардном излазу исписује све целе бројеве од $1$ до $n$, раздвојене размацима, укључујући и број $n$.

Али:

Опис улаза

У првом и једином реду стандардног улаза налази се број $n$.

Опис излаза

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


Решење
n = int(input())
result = ""

for i in range(1, n + 1):
    if i % 3 == 0 and i % 5 == 0:
        result += "FizzBuzz"
    elif i % 3 == 0:
        result += "Fizz"
    elif i % 5 == 0:
        result += "Buzz"
    else:
        result += str(i) 
    
    if i != n:
        result += " "
        
print(result)
Текстуално објашњење


Решење пролази кроз све целе бројеве од $1$ до $n$ и за сваки од њих проверава дељивост са 3 и 5. Најпре се проверава да ли је број дељив и са 3 и са 5, и у том случају се резултату додаје FizzBuzz. Ову проверу је важно извршити пре појединачних провера дељивости, јер би у супротном број дељив са оба броја био препознат већ као Fizz или Buzz. Ако број није дељив са оба, проверава се да ли је дељив само са 3, када се додаје Fizz, односно са 5, када се додаје Buzz. Уколико ниједан од ових услова није испуњен, резултату се додаје сам број претворен у текст. Након сваке вредности, осим последње, додаје се и размак како би елементи у излазу били правилно раздвојени. На крају се формирана ниска result исписује на стандардни излаз.


Задатак B

Првог дана на факултету Лука је на часу математике добио следећи задатак - задат му је природни број $x$ и две могуће операције:

Од понуђене две операције неопходно је одабрати једну и применити је тачно $k$ пута на задату вредност $x$. Задатак је да се пронађе највећи могући број који се може добити након $k$ узастопних примена одабране операције.

Помозите Луки да први реши задатак и остави што бољи утисак првог дана на факултету.

Опис улаза

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

Опис излаза

У првом и једином реду стандардног излаза потребно је исписати највећи број који се може добити након $k$ узастопних примена одабране операције.


Решење
x, k = map(int, input().split())

y1 = x
for i in range(k):
    y1 = y1 * y1
    zbir = 0
    while y1 > 0:
        zbir = zbir + y1 % 10
        y1 = y1 // 10
    y1 = zbir

y2 = x
for i in range(k):
    y2 = y2 * y2
    y2 = y2 % 100

if y1 > y2:
    print(y1)
else:
    print(y2)
Текстуално објашњење


Пошто је потребно изабрати једну од две понуђене операције и затим је применити тачно $k$ пута, решење независно симулира оба могућа избора. Променљива y1 представља резултат примене прве операције. У сваком кораку број се најпре квадрира, а затим се помоћу операција % 10 и // 10 издвајају његове цифре и рачуна њихов збир, који постаје нова вредност y1. Овај поступак се понавља тачно $k$ пута.

На исти начин, променљива y2 представља резултат примене друге операције. После сваког квадрирања задржавају се само последње две цифре добијеног броја. То се једноставно реализује операцијом y2 % 100, јер остатак при дељењу са 100 управо представља последње две цифре броја. И ова операција се примењује тачно $k$ пута. На крају се упоређују вредности добијене применом прве и друге операције и исписује се већа од њих, јер она представља највећи број који је могуће добити након $k$ узастопних примена једне изабране операције.


Задатак C

Ђоле много воли да једе слаткише, а од свих слаткиша омиљена му је чоколада. Данас је посебно срећан зато што ће појести велику чоколаду, састављену од $n$ редова и $m$ колона, коју је добио за рођендан. Када је отворио чоколаду, видео је да се она састоји од црних и белих коцкица, што га је мало разочарало; наиме, Ђоле не воли белу чоколаду и жели да поједе само црне коцкице.

Пре него што се заслади, Ђоле прво мора да исече чоколаду. Може да направи произвољан број вертикалних и/или хоризонталних резова између колона, односно редова чоколаде. Вертикални рез прави од горње до доње ивице, док хоризонтални рез прави од леве до десне ивице чоколаде. Након што је исече, Ђоле ће добити неколико правоугаоних комада чоколаде.

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

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

Опис улаза

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

У сваком од следећих $n$ редова стандардног улаза налази се $m$ цифара које имају вредност или $0$ или $1$. Цифра $0$ означава да је дата коцкица бела, а $1$ да је коцкица црна.

Опис излаза

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


Решење
n, m = map(int, input().split())
a = [input().strip() for _ in range(n)]

rezovi = 0

# водоравни резови између редова
for i in range(n - 1):
    treba_rez = False
    for j in range(m):
        if a[i][j] != a[i + 1][j]:
            treba_rez = True
            break
    if treba_rez:
        rezovi += 1

# усправни резови између колона
for j in range(m - 1):
    treba_rez = False
    for i in range(n):
        if a[i][j] != a[i][j + 1]:
            treba_rez = True
            break
    if treba_rez:
        rezovi += 1

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


Решење засебно одређује неопходне хоризонталне и вертикалне резове. За свака два суседна реда проверавају се коцкице у свим колонама. Ако постоји бар једна колона у којој су две суседне коцкице различите боје, између та два реда мора се направити хоризонтални рез, како се црна и бела коцкица не би нашле у истом комаду чоколаде. Чим се пронађе један такав пар, није потребно проверавати остале колоне, јер је већ сигурно да је рез неопходан. На исти начин се за сваке две суседне колоне проверава да ли постоји бар један ред у којем су суседне коцкице различите боје. Ако постоји, неопходно је направити вертикални рез између тих колона.

На крају, збир свих неопходних хоризонталних и вертикалних резова представља најмањи број резова којим се обезбеђује да сваки добијени правоугаони комад садржи коцкице само једне боје. При провери хоризонталних резова у најгорем случају посматра се $(n-1) \cdot m$ парова коцкица, а при провери вертикалних $n \cdot (m-1)$, па је временска сложеност алгоритма $\mathcal{O}(n \cdot m)$. Матрица чоколаде се чува у меморији, због чега је просторна сложеност $\mathcal{O}(n \cdot m)$.


Задатак D

Дат је низ целих бројева $a_1…a_N$ са члановима низа иницијално у опсегу $[1, N]$ $(1 \le N \le 2 \cdot 10^5)$, као и цели број $K$ који је различит од нуле $(-N \le K \le N, K \neq 0)$.

Можете да извршите следећу операцију произвољан број пута (или ниједном): изаберите индекс $i$ и промените вредност $i$-тог члана низа тако да је његова нова вредност $a_i = a_i + K$.

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

Опис улаза

Улаз се састоји од $T$ $(1 \le T \le 10)$ засебних тест примера. Сваки тест пример се састоји од следећег:

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

У другом реду тест примера дат је низ $a_1 … a_N$.

Загарантовано је да збир свих вредности $N$ у оквиру групе од $T$ тест примера није већи од $10^6$.

Опис излаза

За сваки од $T$ тест примера у засебном реду исписати минималан број операција које је неопходно извршити.


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

for _ in range(T):
    N, K = map(int, input().split())

    cnt = [0] * N
    values = list(map(int, input().split()))

    for x in values:
        cnt[x - 1] += 1

    if K < 0:
        cnt.reverse()
        K = -K

    ans = 0

    for i in range(K):
        cur = i
        cnt_min = 0

        while cur < N or cnt_min > 0:
            if cur < N:
                cnt_min += cnt[cur]

            if cnt_min > 0:
                ans += cnt_min - 1
                cnt_min -= 1

            cur += K

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


Најпре се помоћу низа cnt пребројава колико пута се свака вредност појављује у почетном низу. Ако је $K>0$, сваки број може да се повећава само за $K$, па вредности које имају различите остатке при дељењу са $K$ никада не могу прећи једна у другу. Због тога се свака таква група обрађује независно, проласком кроз вредности облика $i, i+K, i+2K,\ldots$. Ако је $K<0$, низ који представља број појављивања појединих вредности се најпре обрће, а $K$ се замењује са $-K$, чиме се проблем своди на исти случај кретања ка већим индексима.

Променљива cnt_min представља број елемената које у једној итерацији треба распоредити на различите вредности. Када стигнемо до неке вредности, cnt_min се најпре увећава за број елемената који су првобитно имали ту вредност. Од свих елемената који се тада налазе на истој вредности, само један може да остане на њој, јер све вредности у коначном низу морају бити различите. Сви остали морају да се помере на следећу могућу вредност, односно да се над њима још једном примени операција додавања $K$. Ако у том тренутку имамо cnt_min елемената, један остаје, а преосталих cnt_min - 1 се помера, па се управо толико додаје на ans. Након тога се cnt_min умањује за један, јер је један елемент успешно смештен на тренутну вредност. На пример, ако се на некој позицији нађу три елемента, један задржава ту вредност, а друга два морају да се помере за $K$, што захтева две операције. Та два елемента затим настављамо да разматрамо на следећој позицији. Поступак се понавља све док сви елементи не добију међусобно различите вредности.

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


Задатак E

За све позитивне целе бројеве $x$, функција $f(x)$ дефинисана је на следећи начин:

За задати број $x$ $(1 \le x \le 10^{2 \cdot 10^5})$ пронаћи колико пута је неопходно применити функцију $f$ тако да $x$ постане једнако $0$. Имајући у виду да овај број може да буде јако велики, програм треба да враћа остатак при дељењу добијеног броја са $10^9 + 7$.

Опис улаза

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

У наредних $T$ редова налазе се позитивни цели бројеви $x$, који се састоје од цифара од $0$ до $9$, при чему се подразумева да прва цифра броја не може да буде $0$.

Загарантовано је да укупан број цифара свих целих бројева $x$ из дате групе тест примера није већи од $10^6$.

Опис излаза

За сваки од $T$ тест примера у засебном реду исписати остатак који се добије када се укупан број примена функције $f$ подели са $10^9 + 7$.


Решење
MOD=1000000007
 
cost=[1]
sum=1
for i in range(1,200003):
    cost.append(sum+2)
    sum+=cost[i]
    sum%=MOD
 
t=int(input())
for _ in range(t):
    x=input()
    if x=='0':
        continue
    x=x[::-1]
    ans=0
    cnt=0
    for i in range(len(x)):
        v=int(x[i])
        if v%2==1:
            ans+=cost[i]
            ans%=MOD
        if v!=0 and v!=1:
            cnt+=1
    if cnt>0:
        ans+=1
        ans%=MOD
    print(ans)
Текстуално објашњење


Пошто број $x$ може имати чак $2 \cdot 10^5$ цифара, није могуће директно симулирати примене функције све док $x$ не постане 0. Кључно је приметити да, чим број $x$ садржи неку цифру различиту од 0 и 1, једна примена функције претвара сваку његову цифру у 0 или 1: парне цифре постају 0, а непарне 1. То значи да се, након највише једног корака, увек добија број који се састоји искључиво од цифара 0 и 1.

За такве бројеве унапред се одређује низ cost, при чему cost[i] представља број примена функције потребних да се уклони јединица која се налази на $i$-тој позицији, рачунајући позиције здесна и почевши од индекса $0$. На пример, за број $1$ потребан је један корак, па је cost[0] = 1. Ако посматрамо број $10^i$, првом применом функције одузима се $1$ и добија број састављен од $i$ деветки. Следећом применом све те деветке постају јединице, па се добија број са јединицама на свим нижим индексима цифара. Зато за цифру $1$ са $i$-тим индексом важи да се функција мора применити два пута како би се претворила у $0$, након чега је потребно уклонити све јединице са индексима цифара од $0$ до $i-1$. Отуд се вредности рачунају као cost[i] = cost[0] + cost[1] + ... + cost[i-1] + 2. Променљива sum чува управо овај збир претходно израчунатих вредности, па се цео низ cost може унапред одредити у линеарном времену.

За сваки задати број цифре се посматрају здесна налево, како би индекс цифре одговарао њеној позицији. Свака непарна цифра ће, након претварања, постати $1$, па се за њену позицију у резултат додаје одговарајућа вредност cost[i]. Парне цифре постају $0$ и зато не доприносе резултату. Ако је почетни број садржао бар једну цифру различиту од $0$ или $1$, потребно је урачунати и ону прву примену функције којом се све цифре претварају у $0$ и $1$, па се резултат додатно увећава за $1$. Ако се број већ састојао само од нула и јединица, овај додатни корак није потребан.

Пошто се низ cost унапред одређује до максималног броја цифара, а затим се за сваки тест пример свака цифра обрађује само једном, временска сложеност је $\mathcal{O}(L)$, где је $L$ укупан број цифара свих улазних бројева. Просторна сложеност је $\mathcal{O}(M)$, где је $M=2 \cdot 10^5$, због чувања низа cost. Сви резултати се рачунају по модулу $10^9+7$.