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

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

View on GitHub

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

Задатак A

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

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

Опис улаза

У првом реду се налазе четири цела броја одвојена размацима - $x_1\ y_1\ x_2\ y_2$, за које важи: $0 \le x_1,\ y_1,\ x_2,\ y_2 \le 10$. Први пар бројева $(x_1,\ y_1)$ представља координате доњег левог угла првог правоугаоног пашњака, док други пар бројева $(x_2,\ y_2)$ представља координате његовог горњег десног угла, при чему важи да је $x_2 \gt x_1$ и $y_2 \gt y_1$.

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

Подразумева се да се правоугаони пашњаци међусобно не преклапају.

Опис излаза

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

Решење
x1,y1,x2,y2 = map(int, input().split())
x3,y3,x4,y4 = map(int, input().split())

xLow = min(x1,x3)
yLow = min(y1,y3)
xHigh = max(x2,x4)
yHigh = max(y2,y4)

a = pow(max((xHigh-xLow),(yHigh-yLow)),2)

print(a)

Текстуално објашњење Потребно је пронаћи најмањи могући квадрат (тачније његову површину) који може да обухвати оба правоугаона пашњака, односно, потребно је пронаћи најмању могућу страницу квадрата који има тражено својство. Могуће је наћи екстремне вредности координата (највеће и најмање $x$ и $y$), а затим њиховом разликом одредити кандидате за дужину странице квадрата. Ово се слаже са захтевом да странице квадрата буду паралелне осама $x$ и $y$. Потребна је страница квадрата таква да он обухвати оба задата правоугаоника, тако да треба одабрати већу од претходно израчунатих разлика. Када је страница квадрата одређена, потребно је само квадрирати је како би се дошло до површине траженог квадрата.

Задатак B

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

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

Конкретно, Спиридон би на дан $d_i$ кући донео $b_i$ паковања чоко плазме.

Спасенија би сваки дан појела једно паковање чоко плазме (уколико их има у кући).

Ваш задатак је да одредите колико пута ће Спасенија уживати у свом омиљеном слаткишу током првих $T$ дана.

Улазни подаци

У првом реду стандардног улаза налазе се бројеви $N$ и $T$. Број $N$ означава број дана за које важи да је Спиридон купио чоко плазму. Број $T$ се односи на број дана који се посматра при израчунавању.

У наредних $N$ линија стандардног улаза налазе се $d_i$ и $b_i$, где $d_i$ означава о ком је дану реч (по реду), а $b_i$ означава број паковања који је Спиридон купио у дану $d_i$.

Излазни подаци

У првом и једином реду излаза исписати колико пута ће Спасенија јести чоко плазму у првих $T$ дана.

Решење
N, T = map(int, input().split())
kupovine = [tuple(map(int, input().split())) for _ in range(N)] + [(T+1, 0)]
 
preostalo, sveukupno, dan_poslednji = 0, 0, 0
for d, b in kupovine:
    sveukupno += b
    preostalo -= d - dan_poslednji
    dan_poslednji = d
    preostalo = max(preostalo, 0) + b
 
print(sveukupno - preostalo)

Текстуално објашњење Потребно је пратити (по данима) када се догодила куповина, односно процесуирати куповину по куповину. У сваком тренутку водити рачуна о томе када се десила последња куповина, броју преосталих слаткиша у кући, као и броју слаткиша које је Спиридон до датог тренутка купио. При обради сваке следеће куповине, ажурирати свеукупну количину купљених слаткиша. Такође, ажурирати број слаткиша који је преостао у кући након последње куповине. Куповина у дану $T+1$ количине $0$ је додата како би се могли адекватно обрадити случајеви у којима се десила куповина последњег дана (односно како би се урачунали случајеви у којима $T$-ог дана долази до куповине, и да свакако Миа може појести слаткиш тог дана). На крају, тражени број добијен је као разлика између броја купљених и преосталих слаткиша.

Задатак C

Низ b дужине k назива се аритметичким низом ако је аритметичка средина његових чланова једнака јединици. Дакле, тада важи:

\[\frac{b_1+...+b_k}{k}=1\ .\]

Посматрајмо, на пример, низ $[1,\ 1,\ 1,\ 2]$. Његова аритметичка средина се рачуна као $\frac{1+1+1+2}{4}=1,25$, што је различито од $1$, па се овај низ не сматра аритметичким.

Нека је дат низ целих бројева $a$ дужине $n$. Одредити минималан број ненегативних целих бројева које је потребно додати у овај низ, тако да он постане аритметички.

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

Улазни подаци

У првој линији се налази један цео број t $(1 \le t \le 1000)$, који означава број различитих тестних случајева који ће бити прослеђени на стандардни улаз.
У осталим линијама налазе се тестни случајеви, и то у следећем формату:

Излазни подаци

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

Решење
N=int(input())
for _ in range(N):
    n=int(input())
    suma=sum(list(map(int,input().split())))
    if suma<n:
        print(1)
    else:
        print(suma-n)

Текстуално објашњење Да би аритметичка средина низа била тачно $1$, потребно је да сума (чланова) низа одговара броју чланова низа ($n$). Постоје дакле $3$ могућа случаја за дати проблем: * Сума низа је једнака $n$ : Решење је $0$, обзиром да је аритметичка средина низа једнака $1$. * Сума низа је мања од $n$ : Решење ће засигурно бити $1$, пошто је могуће додати један цео број $k$ у низ, тако да важи $suma + k = n + 1$, конкретно $k = n - suma + 1$ * Сума низа је већа од $n$ : Потребно је спустити аритметичку средину низа, што се може постићи додавањем $0$ у низ (смањење аритметичке средине се постиже повећањем броја чланова самог низа, без утицаја на њихову суму). Број $0$ које је потребно додати ће увек износити $suma - n$, што је уједно и решење овог подслучаја.

Задатак D

Од 3 дата штапа, на једном је $n$ дискова различитих величина, а остала два су празна. Дискови на првом штапу су поређани по величини, то јест тако да је на дну диск величине $n$, на њему диск величине $n-1$ итд. све до диска величине $1$, који се налази на врху.

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

Ваш задатак је да одредите минимални број премештања за дати број дискова $n$.

Опис улаза

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

Опис излаза

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

Решење
def potez(sa, na):
    #print('premestiti disk sa ' + str(sa) + ' na ' + str(na))
    return 1

def kula(n, sa, na, slobodan):
    if n == 1:
        return potez(sa, na)
    else:
        return kula(n-1, sa, slobodan, na) + kula(1, sa, na, slobodan) + kula(n-1, slobodan, na, sa)

n=int(input())
print(kula(n,"A","C","B"))

Текстуално објашњење Код, односно алгоритам за решавање проблема Ханојске куле је показан на предавањима. У овом случају, потребно је извршити мању модификацију, и то: Обзиром да није од интереса сам потез/корак, може се занемарити део који га штампањем текстуално описује; тражи се конкретно **број** корака, стога су рекурзивни позиви функције модификовани тако да за повратну вредност имају **број** $1$. Позив овако дефинисане функције враћа укупан број корак за који је проблем решен, што се иницијално и тражило.

Задатак E

Када не снима видео-записе у којима решава задатке са разних такмичења, велики програмерски инфлуенсер и јутјубер Крокод проводи време играјући друштвене игре са својом пријатељицом Миом. Крокод жели да игра игрицу 7Крокодс, али Миа не воли компликоване игре са пуно правила. Зато је Крокод одлучио да ће играти само са зеленим и крокодилским картама.
Миа има n зелених карата, а на свакој се налази једно од $4$ могућих слова: d, k, o или r. Укупан број поена одређује се као збир освојених бодова према следећим правилима:

Поред тога, Миа има и m крокодилских карата. Свака крокодилска карта може заменити једну зелену карту са било којим од слова (d, k, o или r), по Мијиној жељи. Циљ је да их искористи тако да освоји што више бодова.

Помозите Мији да одреди максималан број бодова које може да оствари са картама које има.

Опис улаза

У првом реду се налазе природни бројеви n и m $(1 \le n \le 100,\ 0 \le m \le 10)$. Представљају број зелених и крокодилских карата које Миа има, респективно.

У другом реду је ниска која садржи n карактера, где i-ти карактер представља слово на i-тој зеленој карти. Ниска се састоји искључиво од карактера d, k, o и r.

Опис излаза

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

Решење
def izracunaj(d, k, o, r):
    x = d * d + k * k + o * o + r * r
    x += 7 * min(k//2, r, o//2, d)
    return x

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

d = s.count("d")
k = s.count("k")
o = s.count("o")
r = s.count("r")



bodovi = izracunaj(d, k, o, r)

for D in range (m + 1):
    for K in range (m + 1):
        for O in range (m + 1):
            for R in range (m + 1):
                if D + K + O + R <= m:
                    bodovi2 = izracunaj(d + D, k + K, o + O, r + R)
                    bodovi = max(bodovi, bodovi2)

print(bodovi)
Текстуално објашњење Потребно је уочити пар ствари: * Крокодилске карте које замене специфичну карту се укључују у рачун броја поена на основу квадрата броја карата са истим словом. * Крокодилске карте се могу употребити као *џокери* који дозвољавају Мији да склопи реч **крокод** и освоји 7 додатних поена. * Постоје случајеви када Мији крокодилске карте доносе више поена уколико се користе у својству повећања броја карата са истим словом, а не за допуњавање речи **крокод**. Ово је могуће јер број карата истог слова утиче на број поена, и то квадрат овог броја (примера ради, разлика између квадрата броја $4$ i квадрата броја $5$ износи $9$, што је више поена него $7$, колико доноси склопљена реч крокод). Најједноставније, а у овом случају и довољно ефикасно решење, јесте израчунати број бодова за сваку могућу расподелу крокодилских карата, и на крају вратити највећи добијени број.