Основи програмирања: јун 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$. У једној операцији можете урадити једно од следећег:
-
Изаберите $2$ узастопна елемента низа $a$ и замените их њиховим минимумом (тј. нека буде $a:=[a_1,a_2,\ldots,a_{i-1},\min(a_i,a_{i+1}),a_{i+2},\ldots,a_n]$ за неки $1\leq i\leq n-1$). Ова операција смањује величину низа $a$ за $1$.
-
Изаберите $k$ узастопних елемената низа $a$ и замените их њиховим максимумом (тј. неки буде $a:=[a_1,a_2,\ldots,a_{i-1},\max(a_i,a_{i+1},\ldots,a_{i+k-1}),a_{i+k},\ldots,a_n]$ за неки $1\leq i\leq n-k+1$). Ова операција смањује величину низа $a$ за $k-1$.
Одредите да ли је могуће претворити низ 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$.