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

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

View on GitHub

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

Задатак A

Млади медведићи данас иду на путовање које је тата медвед организовао за њих! Путују аутобусом, а аутобус којим путују полази у $x$ сати и $y$ минута.

Због несрећних околности медведићи су кренули према аутобуској станици прекасно. Ако медведићи стигну на аутобуску станицу у $a$ сати и $b$ минута, да ли ће стићи на аутобус или ће морати да остану код куће? Можемо претпоставити да су медведићи стигли на станицу на дан када аутобус креће.

Опис улаза

У првом реду су два природна броја $x$ и $y$ ($0 \le x \le 23, 0 \le y \le 59$), време поласка аутобуса.

У другом реду су два природна броја $a$ и $b$ ($0 \le a \le 23, 0 \le b \le 59$), време када су медведићи дошли на аутобуску станицу.

Опис излаза

У првом и једином реду испишите DA ако су медведићи стигли на аутобус или NE ако нису.


Решење
x, y = list(map(int, input().split()))
a, b = list(map(int, input().split()))
    
bus_time = x * 60 + y
bears_time = a * 60 + b
    
if bears_time <= bus_time:
    print("DA")
else:
    print("NE")
Текстуално објашњење


Решење се заснива на томе да се времена поласка аутобуса и доласка медведића претворе у укупан број минута, како би се лакше упоредила. Конкретно, сат се множи са 60 и додају се минути, чиме се добија време изражено у минутима од поноћи. Након тога се упоређују добијене вредности: ако су медведићи стигли раније или тачно у време поласка аутобуса, исписује се DA, а у супротном NE.


Задатак B

Док се припремао за свој први бадминтонски турнир, Никола је приметио да му је трчање по тлу прелако, па је одлучио да отежа тренинг. Почео је да трчи по крововима зграда!

У улици се налази $n$ зграда и познате су нам њихове висине, при чему је $i$-та зграда висока $h_i$ метара. Никола се на почетку налази на крову прве зграде и жели да стигне до крова $n$-те зграде крећући се по суседним зградама.

Ако се Никола налази на крову $i$-те зграде, може скочити на кров следеће зграде (са индексом $i + 1$) ако важи једно од следећих правила:

Када се Никола налази на крову неке зграде и не може скочити на следећи кров, зауставља се и тамо завршава свој тренинг. На основу задатог изгледа улице, одредите на којој згради је Никола завршио свој тренинг.

Опис улаза

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

У другом реду налази се $n$ целих бројева, где $i$-ти број представља висину $i$-те зграде $h_i$ ($1 \le h_i \le 1000$).

Опис излаза

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


Решење
n = int(input())
h = list(map(int, input().split()))

j = n
for i in range(n - 1):
    if h[i + 1] - h[i] > 1:
        j = i + 1
        break
            
print(j)
Текстуално објашњење


Кроз учитани низ који представља висине зграда пролази се редом, почевши од прве зграде, и за сваку зграду се проверава да ли Никола може да пређе на следећу. Према услову задатка, прелаз је могућ ако је следећа зграда нижа или једнака тренутној, или ако је виша за тачно један метар. Зато је једина ситуација у којој Никола не може да настави она када је следећа зграда виша за више од једног метра, односно када важи $h[i+1] - h[i] > 1$. Чим се такав случај пронађе, памти се редни број тренутне зграде као место на коме се Никола зауставио и прекида се даље проверавање. Ако се током проласка ниједном не појави недозвољен прелаз, то значи да Никола може да стигне све до последње зграде, па се исписује број $n$.


Задатак C

Док је Лаза путовао комбијем за Београд, приметио је да су му остали путници гледали у екран мобилног телефона и читали поруке које је слао свом пријатељу Фићи, те је одлучио да стане на пут шпијунажи. Стога је заједно са Фићом развио нови начин шифровања порука. Назвали су га VolksWagen шифром (пошто је и комби био те марке).

Поруку коју Лаза добија од Фиће можемо замислити као таблицу знакова, која се састоји од $2$ врсте и $N$ колона. Свако слово се простире кроз обе врсте и неколико колона. Слова су међусобно раздвојена размацима. Изглед слова у поруци можете пронаћи у тестним примерима.

Слово v приказује се на следећи начин:

\../
.\/.

Слово w приказује се на следећи начин:

\../\../
.\/..\/.

Фића и Лаза ће од сада па надаље комуницирати искључиво словима v и w. Међутим, Лаза има потешкоћа са читањем тих порука. Замолио је Вас да му помогнете да прочита поруку коју је добио од Фиће. Само Вам, наравно, неће открити како да дешифрујете њихову шифру (зашто би је иначе и правили?).

Опис улаза

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

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

Опис излаза

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


Решење
n = int(input())
a = input()
b = input()

i = 0

while i < n:
    if i == n - 4 or a[i + 4] == '.':
        print('v', end='')
        i += 5
    else:
        print('w', end='')
        i += 9
Текстуално објашњење


За решавање овог проблема може се искористити чињеница да се сва слова у поруци појављују у унапред познатом облику, а да се између суседних слова увек налази тачно једна празна колона. Зато се порука може читати слева надесно, тако што се у сваком кораку посматра почетак наредног слова. Ако је у питању слово v, оно заузима 4 колоне, па са једном празном колоном после њега прелазимо укупно 5 места удесно. Ако је у питању слово w, оно заузима 8 колона, па са празном колоном после њега прелазимо 9 места удесно.

У програму променљива i означава тренутну колону са које почиње наредно слово. Проверава се да ли после 4 колоне долази крај поруке или празна колона, јер то значи да се ту завршава слово v. У супротном, реч је о слову w, пошто оно има дужи запис и после четврте колоне се још увек наставља. На тај начин програм редом препознаје свако слово и одмах га исписује, све док не стигне до краја поруке.


Задатак D

Пеђа се налази у квадратној матрици од $n$ редова и $n$ колона, где је $n$ непаран број, те држи магичну четкицу дебљине $k$. Сва поља матрице означена су знаком ., а Пеђа се налази на средишњем пољу матрице.

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

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

Удаљеност нека два поља матрице јесте најмањи број корака потребних да се са једног поља дође до другог, при чему је дозвољено померање у 4 смера (горе, доле, лево, десно).

Опис улаза

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

У другом реду налази се реч која се састоји од великих слова енглеског алфабета, чија је дужина мања или једнака $50$.

Опис излаза

У $n$ редова, испишите по $n$ знакова, изглед матрице након што Пеђа изврши сва упутства.


Решење
n, k = map(int, input().split())
s = input().strip()

a = [['.'] * n for _ in range(n)]
x = y = n // 2

for ch in s:
    if ch == 'L':
        if y > 0:
            y -= 1
    elif ch == 'R':
        if y + 1 < n:
            y += 1
    elif ch == 'U':
        if x > 0:
            x -= 1
    elif ch == 'D':
        if x + 1 < n:
            x += 1
    else:
        for i in range(n):
            for j in range(n):
                if abs(i - x) + abs(j - y) < k:
                    a[i][j] = ch

for row in a:
    print(''.join(row))
Текстуално објашњење


На почетку се формира матрица димензија $n \times n$ попуњена знаковима . и Пеђа се поставља у њено средиште. Затим се редом обрађује сваки карактер из задате речи: ако је у питању L, R, U или D, Пеђа покушава да се помери у одговарајућем смеру, али само ако тиме не излази ван граница матрице; у супротном се тај корак прескаче. Ако је текући карактер неко друго велико слово, Пеђа остаје на истом месту и боји сва поља чија је Менхетн удаљеност од његове тренутне позиције мања од $k$, односно сва поља за која важи $ i-x + j-y < k$. Таква поља се преписују тренутним словом без обзира на то да ли су већ раније била обојена. На крају се исписује коначан изглед матрице.


Задатак E

Милица има $A$ жетона типа A и $B$ жетона типа B ($0 \le A, B \le 10^9$). Она може да направи следећу размену колико год пута жели:

Одредите најмањи ненегативан цео број $x$ такав да важи следеће: након што добије $x$ додатних насумичних жетона, гарантовано је да Милица може да заврши са најмање $f_A$ жетона типа А ($0 \le f_A \le 10^9$).

Опис улаза

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

Затим следи $T$ тестова, од којих се сваки састоји од пет целих бројева $A$, $B$, $c_A$, $c_B$ и $f_A$.

Опис излаза

Испишите одговор за сваки тест у посебном реду.


Решење
def solve(A, B, cA, cB, fA):
    init = B // cB * cA + A
    if init >= fA:
        return 0
    nA0 = fA - 1 - init
    y = cB - 1 - B % cB 
    if cA >= cB:
        y += nA0
    else:
        y += nA0 // cA * cB + nA0 % cA
    return y + 1


T = int(input())
for _ in range(T):
    A, B, cA, cB, fA = map(int, input().split())
    print(solve(A, B, cA, cB, fA))
Текстуално објашњење


Најпре се израчунава колико жетона типа A Милица може да има већ на почетку, ако одмах изврши све могуће размене жетона типа B у жетоне типа A. То је вредност init = A + (B // cB) * cA. Ако је тај број већ најмање $f_A$, онда додатни жетони нису потребни и одговор је 0.

У супротном, тражи се најмањи број додатних насумичних жетона који гарантује да ће, без обзира на то да ли ти жетони буду типа A или типа B, Милица сигурно моћи да стигне до бар $f_A$ жетона типа A. Зато се посматра најгори случај. Прво се рачуна колико јој још недостаје до циља, а затим колико „неповољних“ жетона типа B може да добије пре него што се сакупи довољно B жетона за једну нову размену. После тога се, у зависности од тога да ли је размена повољнија или неповољнија (cA >= cB или cA < cB), одређује колико је још жетона потребно да би се циљ сигурно достигао. На крају се додаје још 1, јер се тражи најмањи број жетона после ког гаранција почиње да важи.