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

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

View on GitHub

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

Задатак A

Дат је низ транскација Вашег банковног рачуна у току 2022. године. Рачун је био празан на почетку те године, односно биланс је био једнак нули. Свака транскација је дефинисана количином новца и датумом када је извршена. Ако је количина новца негативна изврешено је плаћање, у супротном новац је примљен. То значи да се и трансакција у вредности од $0$ динара сматра примњеним новцем. Сваки датум је у формату YYYY-MM-DD: нпр. 2022-05-20 представља 20. мај 2022. године. Додатно, постоји накнада за поседовање картице (изостављена у датој листи трансакција), која износи $5$ динара месечно. Ова накнада се одбија од стања на рачуну на крају сваког месеца осим ако су извршене најмање три уплате картицом за укупан трошак од најмање $100$ динара у току месеца.

Ваш задатак је да израчунате коначни биланс рачуна на крају 2022. године.

Опис улаза

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

Опис излаза

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

Решење
A = list(map(int,input().split()))
D = list(input().split())

def transakcije(A,D):
    table = dict()
    for i in range(len(D)):
        if A[i] <0:
            if D[i][:7] in table:
            
                table[D[i][:7]][0]+=1
                table[D[i][:7]][1]+=A[i]
            else:
                table[D[i][:7]]=[1,A[i]]

    times_five = 12
    for key,val in table.items():
        if val[0] >=3 and val[1]<=-100:
            times_five-=1
    
    return sum(A)-5*times_five

print(transakcije(A,D))

Задатак B

Дат Вам је низ која садржи само бројеве $0$, $1$ и $2$. Ви на сте на позицији $1$, а Ваши непријатељи су на позицијама $2$. Потребно је израчунати растојање до Вашег најближег непријатеља како бисте дошли до њега. Можете ићи лево и десно. Такође, уколико се налазите на ивици низа, и уколико се померите у правцу те ивице, појавићете се на пољу на супротној страни тог низа.

Низ садржи произвољан број $0$ и $2$, али је само једна $1$ у њему, такође и не мора садржати број $2$, тада би требало вратити $0$.

Oпис улаза

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

Опис излаза

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

Решење
n = int(input())
array = [int(num) for num in input()]

def ClosestEnemyI(array):
    enemies = []
    for i in range(len(array)):
            if array[i] == 1: me = i
            if array[i] == 2: enemies.append(i)
    moves = []
    for x in enemies:
        no_wrap = abs(me - x)
        wrap = n - abs(me - x)
        moves.append(min(no_wrap, wrap))
    return min(moves) if moves else 0

print(ClosestEnemyI(array))

Задатак C

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

Одредите да ли је могуће претворити низ a у низ $[1]$ након неколико (евентуално нула) операција.

Опис улаза

Сваки тест пример састоји се од више тест случајева. Прва линија сваког тест случаја садржи број тест случајева t $(1 \leq t \leq 1000)$. Опис тест случајева следи.

Прва линија сваког тест случаја садржи два цела броја $n$ и $k$ $(2 \leq k \leq n \leq 50)$, величину низа $a$ и дужину сегмената на којима можете извршити другу врсту операције.

Друга линија садржи n целих бројева $a_1,a_2,\ldots,a_n$ ($a_i$ је $0$ или $1$) раздвојених размаком, елементе низа $a$.

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

За сваки тест случај, ако је могуће претворити низ a у низ $[1]$, исписати “YES”, инако исписати “NO”.

Решење
n = int(input())
 
for _ in range(n):
    m, k = map(int, input().split())
    a = list(map(int, input().split()))
    if 1 in a:
        print("YES")
    else:
        print("NO")

Задатак D

Након што су ти прсти, масни од Смокија, склизнули са управљача и нехотице притиснули дугме на коме је писало “ворп-спид”, твој свемирски брод, Миленијумски Соко Штарк, нашао се изгубљен у ворп-спејсу. Љуљање брода узроковано јаким гравитационим таласима убрзо је учинило да добијеш морску болест. Не желећи да полусварени Смоки заврши на командама твог брода, притискаш дугме са натписом “Тутањ!”, које те у најкраћем могућем времену одводи до излаза из ворп-спејса, а то је ворм-хол чији се други крај налази у твом wc-у на планети Земљи.

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

Ворп-спејс има облик табеле димензија $D_x \times D_y$ ($D_x$ је број колона, а $D_y$ је број врста). На једном од поља ворп-спејса се налази твој брод, и на једном од поља се налази излаз (брод и излаз могу бити и на истом пољу). У једној јединици времена твој брод може да пређе на неко од суседна четири поља ворп-спејса (горе, доле, лево или десно). Међутим, ворп-спејс је уврнут, па ако се нађеш на пољу уз његову ивицу и покушаш да се помериш у правцу те ивице, осванућеш на пољу које се налази на супротној страни ворп-спејса. Прецизније, ако се налазиш у првој врсти и покушаш да идеш горе, појавићеш се у истој колони, али у последњој врсти; и обрнуто, ако се налазиш у последњој врсти и покушаш да идеш доле, појавићеш се у истој колони, али у првој врсти. Слично важи и за лево и десно - померањем у лево у првој колони, завршићеш у последњој колони исте врсте; и обрнуто, померањем у десно у последњој колони, завршићеш у првој колони исте врсте.

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

Опис улаза

У првој линији налазе се цели бројеви $D_x$ и $D_y$, који представљају број колона и број врста ворп-спејса. У другој линији налазе се цели бројеви $A_x$ и $A_y$, који представљају колону и врсту у којој се налази твој брод. У трећој линији се налазе цели бројеви $B_x$ и $B_y$, који представљају колону и врсту у којој се налази излаз. Бројеви врста и колона почињу од $0$.

Опис излаза

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

Решење
m, n = map(int, input().split())
a, b = map(int, input().split())
c, d = map(int, input().split())
print(min(abs(c-a),m-abs(c-a))+min(abs(d-b),n-abs(d-b)))
Текстуално објашњење
Приметимо да координате можемо да посматрамо независно. Најлакши начин да решимо задатак је анализом случајева. За обе координате разматрамо два случаја, да ли смо прешли преко ивице или не. Посматрајмо $x$ координату почетног и крајњег поља. Уколико нисмо прешли ивицу од поља $A_{x}$ до поља $B_{x}$, растојање је $ A_{x}-B_{x} $. Уколико јесмо и дужина ворп-спејса је $D_{x}$, растојање је $D_{x}- A_{x}-B_{x} $. Дакле, минималан број корака да би смо се нашли на $x$ координати на којој је крајње поље је $\min( A_{x}-B_{x} ,D_{x}- A_{x}-B_{x} )$. Сличан резултат добијамо за $y$ координату, $\min( A_{y}-B_{y} ,D_{y}- A_{y}-B_{y} )$. Укупан број корака је $\min( A_{x}-B_{x} ,D_{x}- A_{x}-B_{x} ) + \min( A_{y}-B_{y} ,D_{y}- A_{y}-B_{y} )$.

Задатак E

Познати ТВ кувар Епирка планира следећу сезону своје емисије, у којој ће снимити $N$ емисија о јелима $X_1,X_2,\ldots,X_N$ (не неопходно различитим – могуће је да снима више емисија о истом јелу). Ради једноставности, представићемо ова јела бројевима (исто од $1$ до $N$): ако $X_i=x$, $i$-та емисија ће бити о јелу $x$.

На располагању му је $N$ рецепата $Y_1,Y_2,\ldots,Y_N$, исто представљени бројевима. Пошто емисија мора бити занимљива, нису довољни рецепти, већ и сценарио: смислио је (исто) $N$ сценарија $Z_1,Z_2,\ldots,Z_K$, где $Z_i=z$ значи да се $i$-ти сценарио може користити за емисију у којој ће правити јело $Y_z$.

Након што је пописао емисије, јела и рецепте, интересује га на колико начина може да почне снимање, односно на колико начина може да изабере емисију $i$ и сценарио $j$ о рецепту за одговарајуће јело. Другим речима, интересује га број уређених парова $(i,j)$, за које важи $X_i=Y_{Z_j}$.

Опис улаза

Први ред стандардног улаза садржи један природан број $N$: број емисија, рецепата и сценарија.

Други ред садржи $N$ бројева $X_1,X_2,\ldots,X_N$, где је $X_i$ јело о ком ће снимити $i$-ту емисију.

Трећи ред садржи $N$ бројева $Y_1,Y_2,\ldots,Y_N$, где је $Y_j$ јело које се прави по $j$-том рецепту.

Четврти ред садржи $N$ бројева $Z_1,Z_2,\ldots,Z_N$, где је $Z_k$ рецепт који се користи у $k$-том сценарију. Сценарији су индексирани почев од 1.

Опис излаза

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

Kвадратно решење(за 50% поена)
n = int(input())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
z = list(map(int, input().split()))

count = 0
for i in range(n):
    for j in range(n):
        if x[i] == y[z[j] - 1]:
            count += 1
print(count)
Решење
n = int(input())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
z = list(map(int, input().split()))

count = {}
for j in range(n):
    count[y[z[j]-1]] = count.get(y[z[j]-1], 0) + 1

result = 0
for i in range(n):
    result += count.get(x[i], 0)

print(result)

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

Прва два подзадатка можемо једноставно решити са две угњеждене петље које испробавају сваки пар $(i, j)$ и броје за колико таквих парова је $X_i = Z_{Y_j}$. Временска сложеност овог алгоритма је $\mathcal{O}(N^2)$, што неће бити довољно за преостале подзадатке.

Алгоритам можемо побољшати тако што раздвојимо ове две петље: прво ћемо пребројати колико постоји епизода за свако могуће јело, односно израчунати низ $C$, где је $C_i$ број индекса $j$ где $X_j = i$. Пошто су све вредности $X_i$ највише $N$, овај низ стаје у меморију и можемо га попунити једним пролазом кроз $X$.

Сада је довољно да прођемо кроз $Z$, и за свако $Z_i$ укупном броју додамо $C_{Z_i}$ (број елемената у $X$ који би били одговарајући пар). Временска сложеност је сада $\mathcal{O}(N)$, сасвим довољно за $N \leq 10^5$.