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

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

View on GitHub

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

Задатак A


Марија има једног заиста посебног кућног љубимца - папагаја званог Кића. Кића највише воли да понавља речи које људи изговарају, па често прекида разговоре понављајући оно што је управо чуо. Једног дана је Марији у госте дошла њена добра пријатељица Исидора. У почетку је све текло поприлично уобичајено; међутим, Марија је убрзо приметила да се Кића понаша помало чудно. Кад год би Исидора изговорила неку реч, Кића би је одмах поновио, али не тачно онако како ју је чуо. Нека слова, односно гласове, изговарао је приметно гласније.


Кића је сваку Исидорину реч понављао по истом правилу - прво слово тише, друго гласније, треће поново тише, четврто гласније и тако све до краја речи.


На крају вечери, пријатељице су се поздравиле и Исидора је отишла кући, а Кића се убрзо вратио свом уобичајеном понашању. Ипак, Марију и даље занима како би Кића поновио неку реч да ју је изговорила Исидора. Ваш задатак је да одредите шта би папагај Кића изговорио уместо задате речи коју је изговорила Исидора.


Опис улаза

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


Опис излаза

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


Пример 1

Улаз

neeznammm

Излаз

nEeZnAmMm

Појашњење примера

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


Пример 2

Улаз

dobardanisidora

Излаз

dObArDaNiSiDoRa


Пример 3

Улаз

aaaaa

Излаз

aAaAa


Подзадаци:

Решење
s = list(input())

for i in range(len(s)):
    if i % 2 == 1:
        s[i] = s[i].upper()

print("".join(s))
Текстуално објашњење


Пређите кроз слово по слово и сваки други индекс (1, 3, 5, …) претворите у велико слово, док остале остављате малим. Тако се директно добија тражена реч, уз линеарну сложеност по дужини улаза.


Задатак B


На часу српског језика Ђорђе чита песму која се састоји од $n$ стихова и $n/4$ строфа. Стихови 1, 2, 3 и 4 чине прву строфу, стихови 5, 6, 7 и 8 другу итд. Сваки стих у свакој строфи састоји се од тачно $m$ речи.


За два стиха кажемо да се римују онда када је им је $k$ последњих слова њихових последњих речи идентично. Ако се последња реч у једном од стихова састоји од мање од $k$ слова, тада се стихови сигурно не римују.


У једној строфи разликујемо три различита типа риме:


Наставница је Ђорђу дала задатак да одреди у колико се строфа песме појављује сваки од ова три типа риме. Помозите Ђорђу да тачно одговори наставници и добије петицу из српског!


Опис улаза

У првом реду стандардног улаза налазе се природни бројеви $n$, $m$ и $k$ $(1 \le n \le 500, 1 \le m, k \le 20)$ из текста задатка. За број $n$ важи да мора бити дељив са 4.


У наредних $n$ редова налази се по $m$ речи, које се састоје од по највише 20 малих слова енглеске абецеде.


Опис излаза

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


Пример 1

Улаз

8 2 3
aa bb
cc bb
dd ee
ff ee
auu aaaaaahh
auu wer
asdf power
lol kldahh

Излаз

0 0 1

Појашњење примера

Песма се састоји од укупно 8 стихова, односно 2 строфе од по 4 стиха. У првој строфи се ниједан пар стихова не римује, јер се све последње речи у тој строфи састоје од само 2 слова, а $k = 3$. У другој строфи се ради о обгрљеној рими, јер се римују први и четврти стих (aaaaaahh и kldahh), као и други и трећи (wer и power). Дакле, парна и унакрсна рима појављују се 0 пута, док се обгрљена рима појављује једном.


Пример 2

Улаз

8 2 2
ja programiram
izraziti pad
ponekad kuliram
voda vodopad
banana jabuka
fiziku znam
teska odluka
njam njam

Излаз

0 2 0


Пример 3

Улаз

4 4 2
pas konj zec macka
trougao teziste poluravan tacka
fudbal tenis ragbi odbojka
sir mleko kulen sunka

Излаз

1 1 1

Појашњење примера

У јединој строфи ове песме последња два слова последње речи у сваком стиху су ka, па се сви стихови међусобно римују. Из овога следи да се у овој строфи појављују све три врсте риме.


Подзадаци:

Решење
def suffix_k(word, k):
    if len(word) < k:
        return None
    return word[-k:]

def rhymes(x, y):
    return (x is not None) and (y is not None) and (x == y)

n, m, k = map(int, input().split())

last_words = []
for _ in range(n):
    words = input().split()
    last_words.append(words[-1])

parna = 0
unakrsna = 0
obgrljena = 0

for start in range(0, n, 4):
    w1 = suffix_k(last_words[start], k)
    w2 = suffix_k(last_words[start + 1], k)
    w3 = suffix_k(last_words[start + 2], k)
    w4 = suffix_k(last_words[start + 3], k)

    if rhymes(w1, w2) and rhymes(w3, w4):
        parna += 1
    if rhymes(w1, w3) and rhymes(w2, w4):
        unakrsna += 1
    if rhymes(w1, w4) and rhymes(w2, w3):
        obgrljena += 1

print(parna, unakrsna, obgrljena)
Текстуално објашњење


За сваки стих памтимо последњу реч, а риму проверавамо по њеном суфиксу дужине $k$ (ако је краћа, не римује се). Стихове обрађујемо у групама од 4 и појединачно проверавамо три шаблона риме, бројећи колико строфа задовољава сваки од њих.


Задатак C


Иза седам гора, иза седам мора, у неком свету ко зна кад, живи пчелица звана Маја. Њен живот прожет авантурама непресушан је извор идеја за задатке, па смо одабрали једну.


Наиме, Мајин пријатељ, скакавац Паја, припрема се за престижно такмичење у скоковима по цвећу. Цвеће на ливади можемо представити као низ природних бројева $a$, дужине $N$. Висина $i$-тог цвета представљена је $i$-тим чланом низа $a$ ($a_i$).


Паја увек скаче слева надесно. Такође, будући да је нов у овом спорту, не може да скочи на неки цвет чија се висина превише разликује од онога на којем се тренутно налази. Тачније, са цвета $i$ може скочити на цвет $j$ ако и само ако важи $i < j$, као и $abs(a_i - a_j) \le K$, где је $K$ природан број који се задаје на улазу.


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


Опис улаза

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


У првом реду налазе се природни бројеви $N$ $(1 \le N \le 2 \cdot 10^5)$ и $K$ $(1 \le K \le 10^9)$.


У другом реду налази се низ природних бројева $a$ $(1 \le a_i \le 10^9)$, који представља висине цветова.


Опис излаза

У једином реду излаза неопходно је исписати $N$ цифара, $0$ или $1$, које за сваки цвет осим првог дају одговор може ли се до њега доћи. Цифра $0$ значи да то није могуће учинити, а цифра $1$ да је дати цвет достижан. С обзиром на то да Паја увек креће са првог цвета, подразумева се да је он достижан.


Пример 1

Улаз

5 2
5 4 8 7 2

Излаз

1 1 0 1 1

Појашњење примера

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


Пример 2

Улаз

5 3
10 15 14 8 9

Излаз

1 0 0 1 1


Подзадаци:

Решење

n, k = map(int, input().split())
a = list(map(int, input().split()))

l = r = a[0]
result = ["1"]

for x in a[1:]:
    if l - k <= x <= r + k:
        result.append("1")
        l = min(l, x)
        r = max(r, x)
    else:
        result.append("0")

print(" ".join(result))
Текстуално објашњење


Одржавамо интервал могућих висина $[l, r]$ свих цветова до којих се може доћи. Ако је нова висина унутар $[l-K, r+K]$, цвет је достижан и проширујемо интервал; иначе је недостижан. Тако у једном пролазу добијамо низ 0/1.


Задатак D


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


У својој верзији Minesweeper-а, Урош на почетку игре сазна позиције свих $k$ бомби на табли од $n$ редова и $m$ колона. На сваком пољу табле може се налазити највише једна бомба.


Његов задатак је да свако поље на табли на којем се не налази бомба означи бројем бомби које се налазе на суседним пољима (у свих 8 смерова) тог поља. Поља на којима се налазе бомбе означиће знаком $”B”$.


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


Опис улаза

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


У наредних $k$ редова налазе се бројеви $r_i$ и $s_i$ ($1 \le r_i \le n$, $1 \le s_i \le m$), ред и колона у којој се налази једна од бомби.


Опис излаза

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


Пример 1

Улаз

1 6 1
1 3

Излаз

0 1 B 1 0 0


Пример 2

Улаз

3 3 3
1 1
2 3
1 3

Излаз

B 3 B
1 3 B
0 1 1


Објашњење првог тест примера

На пољу матрице у 3. колони налази се бомба (слово $”B”$). Поља матрице у 2. и 4. колони (означена бројем 1) суседна су пољу на којем се налази бомба.

Ограничења


Решење
n, m, k = map(int, input().split())
px = [-1, -1, 0, 1, 1, 1, 0, -1]
py = [0, 1, 1, 1, 0, -1, -1, -1]
mat = []

for i in range(n):
    mat.append([0] * m)
    
for i in range(k):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    mat[x][y] = -1
    for j in range(8):
        nx = x + px[j]
        ny = y + py[j]
        if (nx >= 0 and ny >= 0 and nx < n and ny < m):
            if (mat[nx][ny] != -1):
                mat[nx][ny] += 1

for i in range(n):
    for j in range(m):
        if (mat[i][j] == -1):
            print("B", end = " ")
        else:
            print(mat[i][j], end = " ")
    print()
Текстуално објашњење


Матрицу иницијално попунимо нулама, а за сваку бомбу означимо поље са $-1$ и инкрементирамо све важеће суседе у 8 смерова. На крају исписујемо $B$ за бомбе, иначе број суседних бомби.


Задатак E


Архитекта Жика добио је задатак да нацрта велики неправилан зид састављен од усправних стубића.


Зид се састоји од $n$ стубића поређаних један до другог, при чему је $i$-ти стубић висине $a_i$ и ширине $1$. Како би цртеж био што компликованији, $i$-ти стубић је подељен на $b_i$ делова једнаке висине.


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


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


За задати зид потребно је исписати најмањи број дужи које је потребно нацртати како би зид био у потпуности нацртан.


Опис улаза

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


У другом реду налази се низ од $n$ бројева $1 \le a_i \le 10^9$, из текста задатка.


У трећем реду налази се низ од $n$ бројева $1 \le b_i \le 10^9$, из текста задатка.


Опис излаза

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


Пример 1

Улаз

3
4 6 4
2 3 4

Излаз

10


Пример 2

Улаз

3
4 6 3
3 3 2

Излаз

12


Објашњење другог тест примера

Жика ће дуж на врху првог стубића продужити у други стубић, па ће тако две дужи „спојити“ у једну. Исту ствар ће урадити са три дужи које су на дну зида. Тако ће укупно нацртати 12 дужи, а може се показати да је то најмањи број дужи које Жика треба да нацрта.


Ограничења


Решење
import math


def deli(visina, br, naz):
    return visina * naz // br


def presek(l, r, a, b, g):
    if l < 0:
        return 0

    br = math.lcm(a[l] // g[l], a[r] // g[r])
    naz = math.gcd(b[l] // g[l], b[r] // g[r])

    return deli(min(a[l], a[r]), br, naz) + 1


def solve():
    n = int(input())

    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    g = [0] * n
    for i in range(n):
        g[i] = math.gcd(a[i], b[i])

    ans = n + 1
    for i in range(n):
        ans += b[i] + 1
        ans -= presek(i - 1, i, a, b, g)

    print(ans)

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


Број линија је збир свих хоризонталних дељења и вертикалних ивица, али се суседни стубићи могу спојити ако им се поделе поклапају. Уз помоћ $gcd/lcm$ израчунавамо колико се хоризонталних линија поклапа између два суседа и тај број одбијамо од укупног збирa.