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

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

View on GitHub

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

Задатак A

Живојин је искусан туристички водич који већ годинама доводи туристе из разних крајева света и упознаје их са лепотама Србије. Један од дражих му делова јесте вожња чувеном Шарганском осмицом, којом поново одјекује клапарање вагона и писак парњаче музејског воза Носталгија (пре реконструкције железнице је преко мостова и кроз планинске усеке саобраћао чувени воз Ћира).

Сутра ће Живојин водити групу од $N$ људи. Музејски воз Носталгија има два вагона – у први вагон може да стане $A$ људи, а у други $B$ људи. Сваки туриста из групе мора барем једном да се провоза возом. На располагању је само један воз, тако да док су неки туристи на тури, остали морају да чекају.

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

Опис улаза

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

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

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

Опис излаза

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


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

print((N + A + B - 1) // (A + B))
Текстуално објашњење


Решење се заснива на томе да се најпре одреди укупан број туриста који могу да се провозају током једне туре. Пошто први вагон има капацитет $A$, а други $B$ места, у једној тури може да се превезе највише $A+B$ туриста. Зато је потребно поделити укупан број туриста $N$ са укупним капацитетом воза и резултат заокруглити навише, јер је потребно организовати још једну туру чак и ако након потпуно попуњених тура остане само један туриста.

Пошто оператор // у Пајтону представља целобројно дељење и резултат заокругљује наниже, за позитивне целе бројеве заокругљивање количника $N/(A+B)$ навише можемо реализовати изразом (N + A + B - 1)//(A + B). Додавањем $A+B-1$ пре целобројног дељења обезбеђујемо да сваки остатак при дељењу доведе до једне додатне туре, док у случају када је $N$ тачно дељиво са $A+B$ број тура остаје непромењен. На тај начин директно добијамо најмањи број тура потребан да се превезу сви туристи.


Задатак B

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

Бела, црвена и плава боја су редом означене бројевима $0$, $1$ и $2$.

Опис улаза

У једином реду стандардног улаза налази се низ са вредностима $0$, $1$ и $2$, дужине $n$.

Опис излаза

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


Решење
niz = [int(i) for i in input().split()]
num0 = 0
num1 = 0
num2 = 0
for i in niz:
    if i == 0:
        num0 += 1
    elif i == 1:
        num1 += 1
    elif i == 2:
        num2 += 1
for i in range(num1):
    niz[i] = 1
for i in range(num1, num1+num2):
    niz[i] = 2
for i in range(num1+num2, num1+num2+num0):
    niz[i] = 0
        
print(*niz)
Текстуално објашњење


Дато решење користи чињеницу да се у улазном низу могу појавити само вредности $0$, $1$ и $2$, па није потребно примењивати неки од општих алгоритама за сортирање. Најпре се једним проласком кроз низ пребројава колико има елемената сваке од три вредности. Пошто је потребно да се у резултујућем низу прво налазе предмети црвене боје, затим плаве, а на крају беле, низ се потом попуњава са num1 јединица, затим са num2 двојки и на крају са num0 нула. На тај начин добија се тражени распоред без међусобног поређења елемената.

Ако је дужина низа $n$, први пролаз обрађује свих $n$ елемената, док се приликом поновног попуњавања низа укупно такође уписује тачно $n$ елемената. Због тога је временска сложеност алгоритма $\mathcal{O}(n)$, што је ефикасније од уобичајених алгоритама за сортирање заснованих на поређењу, чија је сложеност најчешће $\mathcal{O}(n\log n)$. Поред самог улазног низа користе се само три променљиве за бројање елемената, па је додатна просторна сложеност $\mathcal{O}(1)$.


Задатак C

Година је 2023, април је први, Sony-ев дуго очекивани филм Morbius стиже у биоскопе, и на тадашњем Твитеру @Rank10YGO објављује: „најбољи део Morbius-а је кад је рекао ‘IT’S MORBIN’ TIME’ и поморбио све оне ликове.“ А пошто смо у Србији, филм стиже тек када пола света већ заборави за њега. Стога смо питали Бамбулу да нам преко везе набави титл (subtitle-ове) да проверимо да ли је ова реплика стварно изречена у филму. Бамбула нам је послао енкриптовану датотеку унутар које се налази низ $N (1 \leq N \leq 10^6 )$ целобројних вредности $a_1, a_2, …, a_N~(1 \leq a_i \leq 10^6 )$.

Нисмо залазили у детаље енкрипције, али је Бамбула нагласио: Морб се дефинише као низ од три цела броја где је други број једнак трећем, али различит од првог, тј. облик $(x, y, y)$ где је $x \neq y$. Морб се појављује у датотеци ако је могуће уклонити неке вредности из оригиналног низа тако да преостале вредности формирају управо морб.

Ваш задатак је да на основу Бамбулиног описа пребројите колико независних морбова се појављује унутар самог низа (морбови су независни уколико се не састоје од истих вредности у истом поретку).

Опис улаза

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

У другом реду стандардног улаза се налази $N$ целобројних вредности, где $i$-та вредност одговара $i$-том члану низа — $a_i$.

Опис излаза

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


Решење
N = int(input())
A = list(map(int, input().split()))
 
cnt_left = [0] * (N + 1)
cnt_right = [0] * (N + 1)
for x in A:
	cnt_right[x] += 1
 
ans = 0
distinct_left = 0
 
for i in range(N):
	if cnt_right[A[i]] == 2:
		ans += distinct_left - (cnt_left[A[i]] > 0)
	cnt_right[A[i]] -= 1
	distinct_left += cnt_left[A[i]] == 0
	cnt_left[A[i]] += 1
 
print(ans)
Текстуално објашњење


Решење пролази кроз низ слева надесно и за сваку вредност води евиденцију о броју њених појављивања лево и десно од тренутне позиције. Низ cnt_right на почетку садржи укупан број појављивања сваке вредности, док cnt_left бележи колико пута се свака вредност већ појавила у обрађеном делу низа. Променљива distinct_left представља број различитих вредности које се налазе лево од тренутне позиције.

За формирање морба $(x, y, y)$ потребно је да се нека вредност $x$ појави пре две појаве исте вредности $y$, при чему мора да важи $x \neq y$. Када за тренутни елемент важи cnt_right[A[i]] == 2, то значи да су у још необрађеном делу низа остале тачно две појаве те вредности — тренутна и још једна после ње. Зато свака различита вредност која се већ појавила лево може да представља $x$ и формира један различит морб са том вредношћу $y$. Ако се и сама вредност $y$ већ појавила лево, она се одузима из броја могућности, јер по дефиницији морба мора да важи $x \neq y$. Након тога се тренутни елемент пребацује из „десног“ у „леви“ део низа и поступак се наставља.

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


Задатак D

Учитељица Милена је донела коцкице са циљем да научи ђаке једну једноставну игру, али занимљиву игру, познату као “нетранзитивне коцкице”. У игри се користе две коцкице, $X$ и $Y$. Обе се бацају истовремено, и побеђује она коцкица на којој се појавио већи број. Ако се појавио исти број на обе коцкице, коцкице се поново бацају (могуће је да се то понови више пута, докле год је нерешено). Кажемо да коцкица $X$ „добија” коцкицу $Y$ ако је вероватније да ће $X$ победити $Y$ у овој игри, него обрнуто.

Размотрите следеће коцкице са по 4 стране:

Ове коцкице имају занимљиво својство: $A$ добија $B$, $B$ добија $C$, а $C$ добија $A$! Дакле, ниједна од три коцкице није „најбоља” – свака побеђује једну, а губи од друге. Када се ово деси (да нема нерешених међусобних дуела, и да ниједна коцкица не побеђује обе остале), кажемо да је скуп коцкица „нетранзитиван”. У нетранзитивном скупу од три коцкице, свака коцкица побеђује једну од преостале две, а губи од последње преостале.

Пред вама је следећи задатак: дати су бројеви на странама две коцкице $A$ и $B$. Помозите Милени и ђацима да утврде да ли је могуће одабрати бројеве на странама треће коцкице $C$ (између 1 и 10, укључујући оба), тако да скуп коцкица буде нетранзитиван. Бројеви на коцкицама могу да се понављају.

Опис улаза

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

У сваком од наредних $T$ редова стандардног улаза налази се по 8 бројева који дефинишу тест случај: прва четири су бројеви на коцкици $A$, наредна четири бројеви на коцкици $B$. Сви бројеви су између 1 и 10 (могуће је да се један број вишеструко појављује на истој коцкици).

Опис излаза

У $T$ редова исписати одговор за сваки од тест случајева: da ако је могуће направити коцкицу $C$ тако да се оформи скуп нетранзитивних коцкица, односно ne ако није могуће.


Решење
def win(a, b):
    return sum([x > y for x in a for y in b]) > sum([y > x for x in a for y in b])

def solve():
    l = [int(x) for x in input().split()]
    a_die = l[0:4]
    b_die = l[4:8]
    for a in range(1, 11):
        for b in range(1, 11):
            for c in range(1, 11):
                for d in range(1, 11):
                    c_die = [a, b, c, d]
                    if win(a_die, b_die) and win(b_die, c_die) and win(c_die, a_die):
                        print("da")
                        return
                    if win(b_die, a_die) and win(c_die, b_die) and win(a_die, c_die):
                        print("da")
                        return
    print("ne")

t = int(input())
for _ in range(t):
    solve()
Текстуално објашњење


Функција win(a, b) одређује да ли коцкица a добија коцкицу b. Пошто свака коцкица има по четири стране, разматра се свих $4 \cdot 4 = 16$ могућих парова исхода. Броји се у колико случајева је вредност са прве коцкице већа, а у колико случајева је већа вредност са друге коцкице. Ако прва коцкица има више победничких исхода, функција враћа да она добија другу. Нерешени исходи не утичу на поређење, јер се у том случају коцкице поново бацају.

За трећу коцкицу $C$ свака од четири стране може имати вредност од 1 до 10, па постоји укупно $10^4 = 10000$ могућих избора. Програм пролази кроз све такве коцкице и за сваку проверава два могућа нетранзитивна циклуса: $A$ добија $B$, $B$ добија $C$, а $C$ добија $A$, или обрнути циклус, у ком $B$ добија $A$, $C$ добија $B$, а $A$ добија $C$. Чим се пронађе бар једна коцкица $C$ која задовољава један од ових услова, исписује се da и претрага се прекида. Ако ниједан од свих могућих избора не одговара, исписује се ne.

Пошто се испитује највише $10^4$ могућих коцкица $C$, а свако поређење две коцкице обрађује само 16 парова страна, временска сложеност по тест примеру је $\mathcal{O}(10^4)$, односно практично константна у односу на улаз, јер су број страна и опсег вредности унапред ограничени. Додатна просторна сложеност је $\mathcal{O}(1)$, јер се користи само неколико низова фиксне величине и помоћних променљивих.


Задатак E

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

Хијерархија је дефинисана као структура са $N$ запослених и $N−1$ везом надређени–подређени, то јест везом у којој је један запослени директно надређен другом запосленом. Такође, у хијерархији мора постојати једна особа која је директно или индиректно (неколико узастопних директних надређености) надређена свим осталим запосленима.

Радиша посматра фирму са $N$ запослених и $N − 1$ таквом везом, али није сигуран да ли структура заиста представља исправну хијерархију. Ваш задатак је да му помогнете да одговори на то питање. Све податке записао је у своју свеску.

Поред тога, Радиша ће у својој свесци направити $Q$ трајних измена, где ће преокренути једну надређени–подређени везу тако да подређени постаје директно надређен свом бившем надређеном из те везе. После сваке такве измене потребно је поново одговорити на исто питање: да ли је тренутна структура валидна хијерархија?

Опис улаза

У првом реду стандардног улаза налази се природан број $N (2 \le N \le 3 \times 10^5)$.

У сваком од наредних $N-1$ редова стандардног улаза, за свако $ i = 1, 2, …, N − 1 $, налази се пар бројева $p_i$ и $e_i$ $(1 \le p_i, e_i \le N, p_i \ne e_i)$, који означавају да је особа идентификована као $p_i$ директно надређена особи идентификованој као $e_i$.

У наредном реду стандардног улаза налази се ненегативан цео број $Q (0 \le Q \le 3 \times 10^5)$.

У сваком од наредних $Q$ редова стандардног улаза налазе се парови $a_i, b_i (1 \le a_i, b_i \le N, a_i \ne b_i)$. Загарантовано је да ће у $i$-том тренутку $a_i$ бити директно надређен $b_i$ или обратно.

Загарантовано је да се у сваком од тест примера неким низом преокрета може постићи макар једна исправна хијерархија.

Опис излаза

У $Q+1$ редова за сваки од наведених сценарија исписати одговор на упит о валидности тренутне хијерархије: DA ако јесте, или NE ако није.


Решење
n = int(input())
s = set()
in_degree = [0] * (3 * 10**5 + 10)
cnt0 = 0
cnt1 = 0

for _ in range(n - 1):
    a, b = map(int, input().split())
    in_degree[b] += 1
    s.add((a, b))

def print_result():
    if cnt0 == 1 and cnt1 == n - 1:
        print("DA")
    else:
        print("NE")

for i in range(1, n + 1):
    if in_degree[i] == 0:
        cnt0 += 1
    elif in_degree[i] == 1:
        cnt1 += 1

print_result()
q = int(input())
for _ in range(q):
    a, b = map(int, input().split())

    if (a, b) not in s:
        a, b = b, a

    s.remove((a, b))
    s.add((b, a))

    if in_degree[b] == 2:
        cnt1 += 1
    elif in_degree[b] == 1:
        cnt1 -= 1
        cnt0 += 1

    if in_degree[a] == 0:
        cnt0 -= 1
        cnt1 += 1
    elif in_degree[a] == 1:
        cnt1 -= 1

    in_degree[b] -= 1
    in_degree[a] += 1
    print_result()
Текстуално објашњење


За сваког запосленог посматрамо његов улазни степен, односно број особа које су му директно надређене. Исправна хијерархија мора да има тачно једну особу без надређеног, док свака од преосталих $N-1$ особа мора да има тачно једног директно надређеног. Зато се у програму помоћу cnt0 прати број запослених чији је улазни степен 0, а помоћу cnt1 број оних чији је улазни степен 1. Структура је исправна ако и само ако важи cnt0 == 1 и cnt1 == n - 1.

Скуп s чува све тренутно усмерене везе надређени–подређени. При свакој измени најпре се утврђује у ком смеру је задата веза тренутно усмерена. Ако је веза $(a,b)$, након преокрета она постаје $(b,a)$. Тиме се улазни степен запосленог $b$ смањује за 1, а улазни степен запосленог $a$ повећава за 1. Пошто се мењају само ова два запослена, није потребно поново анализирати целу структуру, већ се само ажурирају cnt0, cnt1 и одговарајући улазни степени. Након сваке измене поново се проверавају услови за исправну хијерархију.

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