Основи програмирања: фебруар 2023.
Задатак A
Мала Даница, потпуно револтирана одлуком Комисије да ове године укине један круг квалификација, кренула је да разбија све око себе, укључујући и бројеве који јој падну под руку. Наиме, када угледа два природна броја она баци један број на други тако да се бројеви сударе. Сударом два броја, настаје нов природан број.
Приликом судара два природна броја $X$ и $Y$, свака цифра једног броја упоређује се с одговарајућом цифром другог броја, то јест, јединица се упореди с јединицом, десетица с десетицом, стотина са стотином, итд. Мања од две цифре у том поређењу испадне, док већа улази у састав новоформираног броја. Уколико су одговарајуће цифре једнаке, приликом судара обе улазе у новостворени број те ће стога он имати више цифара од $X$ и $Y$. Уколико у неком од два природна броја која се сударају нема одговарајуће цифре, сматра се да та цифра не постоји те се без поређења увек узима цифра другог броја, па макар она била и нула.
Пошто је бројева превише, мала Даница не може сама да се избори с њима, па вас је замолила да јој помогнете тако што ћете сударати бројеве заједно с њом. Да бисте то учинили морате одговорити на питање који ће се број створити приликом судара два природна броја?
Опис улаза
У првом реду стандардног улаза се налазе први природан број $X$, док се у другом реду стандардног улаза налази други природан број $Y$. Ова два природна броја треба сударити на начин описан у тексту задатка.
Опис излаза
У једином реду стандардног излаза исписати новостворени број који се добија приликом судара два броја са улаза.
Решење
def sudar(x, y):
xrev, yrev = x[::-1], y[::-1]
lenx, leny = len(x), len(y)
lenmx = max(lenx, leny)
rrev = ''
try:
for i in range(lenmx):
if xrev[i] > yrev[i]:
rrev += xrev[i]
elif yrev[i] > xrev[i]:
rrev += yrev[i]
else:
rrev += xrev[i] + yrev[i]
except IndexError:
if lenx > leny:
rrev += x[:lenx-leny][::-1]
elif leny > lenx:
rrev += y[:leny-lenx][::-1]
return rrev[::-1]
print(sudar(input(), input()))
Текстуално објашњење
Судар бројева
Главно решење
Задатак је најлакше решити посматрајући дате природне бројеве $X$ и $Y$ као ниске. Наиме, у једној петљи треба поредити знакове (карактере) ниски $X$ и $Y$, који заправо представљају цифре бројева на одговарајућим индексима. Крећући се уназад, почевши од цифара најмање тежине и идући ка цифрма највеће тежине, идеја је додавати већу од њих у неку новостворену ниску. Уколико се пак деси да су цифре одговарајуће тежине једнаке, неопходно их је обе додати у поменуту новоформирану ниску, то јест ту једну цифру два пута. Ниску направљену у претходном поступку на крају задатка потребно је исписати. Случајеви када су задати улазни бројеви различитих дужина решава се тако да када се током проласка кроз описану петљу број цифара једног од бројева исцрпи, резултујућу ниску само треба допунити преосталим цифрама већег броја које нису биле искоришћене у поређењу.
Под претпоставком да се задат број $X$ састоји из $M$ цифара, док задати број $Y$ садржи $N$ цифара, сложеност описаног алгоритма је $\mathcal{O}(M+N)$, односно линеарна по броју цифара.
Задатак B
Ближи се финале светског првенства и организатори су забринути за безбедност на трибинама. Наиме постоји шанса да дође до сукоба између навијача супарничких тимова. Зато је одлучено да се направи револуционарни распоред трибина.
Седишта трибина су распоређена у $N$ редова са по $M$ седишта. Могуће је пролазити између било која два седишта, као и са спољашњих страна ивичних седишта (ово можемо посматрати као $N \times M$ матрицу, где поља представљају седишта, а ивице путеве).
Организатори желе да поставе редаре на нека од седишта тако да сви путеви буду обезбеђени. Сваки редар чува 4 пута око свог седишта. Организатори од вас траже да нађете минималан број редара који је потребан да се ово уради.
Oпис улаза
У једином реду стандардног улаза се налазе бројеви $N$ и $M$ - број редова и број седишта по реду.
Опис излаза
У једином реду стандардног излаза исписати минималан број редара потребан да се обезбеде трибине.
Решење
m, n = map(int, input().split())
if m == 1 or n == 1:
print(max(m,n))
else:
print(2*(m+n-2) + (m-2)*(n-2)//2)
Текстуално објашњење
Финале
Главно решење
Ако посматрамо путеве на рубу матрице, видимо да и сва поља на рубу (тј. први и последњи ред и колона) морају имати редара. Ако је $N \leq 2$ или $M \leq 2$, то значи да ће сва поља у матрици имати редара, па је у том случају решење $N \cdot M$.
Надаље претпостављамо да важи $N$, $M \geq 3$. Посматрајмо матрицу добијену брисањем првог и последњег реда и колоне - у овој новој $(N-2) \times (M-2)$ матрици ћемо тражити максималан број поља где не морамо поставити редаре, ако знамо да су сви путеви на рубу већ покривени. За свака два суседна поља важи да барем једно од њих има редара, јер иначе пут који их раздваја не би био покривен. Овај услов је и довољан, јер ће тада и сви путеви бити покривени.
Дакле, потребно је наћи највећи скуп поља у коме не постоје два суседна. Ово је познат задатак: обојимо матрицу шаховски црно-бело и узмемо сва поља оне боје која се више пута појављује. Пошто се број поља црне и беле боје разликује за највише један, биће $\lceil \frac{2} \rceil$ поља једне, и $\lfloor \frac{2} \rfloor$ поља друге боје. То значи да можемо имати максимално $\lceil \frac{2} \rceil$ поља без редара, па је минималан број редара $N \cdot M - \lceil \frac{2} \rceil$.
Задатак C
Након расправе са часа филозофије, малом Стојану је пала на памет нова пословна идеја – одлучио је да се бави куповином и продајом струје. На основу изгубљеног Теслиног изума је направио батерију бесконачног капацитета, тако да сада може да купује струју данима када је јефтина и продаје је када је скупа.
Помоћу временске машине (такође Теслиног изума), Стојан је сазнао колика ће бити цена струје сваког од наредних $N$ дана (i-тог дана ће киловат-час коштати $C_i$ динара). На почетку му је на располагању $M$ динара и празна батерија. Сваког дана он може да купи колико год жели струје (док год има новца да је плати) или прода колико год жели (док год има довољно струје у батерији). Количине купљене и продате струје не морају бити цели бројеви.
Помозите Стојану да одлучи како ће трговати струјом, тако да му на крају последњег дана остане што више новца.
Опис улаза
У првој линији стандардног улаза налазе се два цела броја, $N$ и $M$ – број дана за које Стојан зна цену струје и свота новца која му је на располагању на почетку.
У другој (последњој) линији налази се N бројева $C_1,C_2,…,C_N$, где је $C_i$ цена једног киловат-часа i-тог дана.
Излазни подаци
На прву линију стандардног излаза исписати максималну суму новца коју Стојан може имати на крају последњег дана. Гарантује се да ова вредност неће бити већа од $10^{10}$.
Решење
N, M = map(int, input().split())
C = list(map(int,input().split()))
for i in range(N-1):
profit = M * C[i+1] / C[i]
M = max(M, profit)
print(M)
Текстуално објашњење
Струја
Главно решење
Ако оптимално тргујемо струјом, сигурно ћемо сваког дана или “чекати” (без куповине и продаје), или потрошити сав новац на струју, или продати сву струју коју имамо. Ово тврђење неће бити формално доказано овде, али идеја иза њега је да ако “раздвојимо” новац (или струју) и потрошимо само део, потрошен и сачуван део се могу посматрати независно. Ако потрошен део новца доноси бољу зараду од непотрошеног, боље је да потрошимо све (и обрнуто).
Сада је потребно само одабрати дане када ћемо куповати и продавати струју. Оптималан избор је да купујемо у локалним минимумима цене, односно данима када је струја јефтинија него што је била јуче и него што ће бити сутра, и да продајемо у локалним максимумима (кад је скупља од суседних дана). Да бисмо доказали да је ово оптимално, посматрајмо било који други избор дана. Тада сигурно можемо “померити” ону куповину (или продају) која није локални минимум (максимум) на “суседни” дан када је цена повољнија и зарадити више.
Локалне минимуме и максимуме можемо наћи у $\mathcal{O}(N)$ (за сваки дан гледамо само два суседа), тако да се цео задатак може решити у $\mathcal{O}(N)$. Обратите пажњу на први и последњи дан – пошто имају само једног суседа, можемо их или посматрати као специјалне случајеве, или додати “вештачке” елементе за дане $0$ и $N+1$, са ценама бесконачно и минус бесконачно.
Нешто једноставније решење за имплементацију је следеће: за сваки дан можемо одлучити да ли ћемо тог дана купити струју и одмах је продати следећег дана. У овом случају дозвољавамо да исти дан продамо струју и опет је купимо по истој цени (што је исто као да не урадимо ништа). Јасно је да ћемо у овом случају куповати оних дана када је цена мања него следећег, тако да можемо избећи “памћење” минимума и максимума.
Задатак D
Комисија је за ово такмичење поново спремила чудан уређај и наизглед бескорисна питања о њему: идеалну гумену лоптицу и стазу по којој се она котрља. Стазу ћемо посматрати као праву линију, где лоптица почиње на позицији $0$, крећући се брзином $1$ у десно, ка позитивним позицијама (дакле, након једне секунде ће бити на позицији $1$, након две на позицији $2$, …).
Да би стаза била занимљивија, на њој се налази $N$ зидова на позицијама $X_i$ и стабилностима $S_i$. Када лоптица удари у зид, одбија се и почиње да се креће у супротном смеру. Како је лоптица идеална, наставиће да се креће истом брзином $1$. Након судара, стабилност зида се смањује за $1$, и ако се смањила на $0$, тај зид нестаје.
Комисију интересује програм који ће, за дате позиције и стабилности зидова, одредити колико ће времена проћи од почетка кретања лоптице до последњег судара са зидом.
Опис улаза
У првом реду дат је један природни број, број зидова $N$. У наредних $N$ редова су дата по два цела броја $X_i$, $S_i$, редом позиција и стабилност $i$-тог зида.
Опис излаза
У једином реду излаза је потребно исписати број секунди од почетка кретања лоптице до последњег судара са зидом. Како овај број може бити веома велик, испишите његов остатак при дељењу са $10^9+7$.
Решење
MOD = 10**9 + 7
n = int(input())
left = []
right = []
for i in range(n):
x, hp = map(int, input().split())
if x < 0:
left.append({"x": x, "hp": hp})
else:
right.append({"x": x, "hp": hp})
left.sort(key=lambda wall: wall["x"], reverse=True)
right.sort(key=lambda wall: wall["x"])
nleft = len(left)
nright = len(right)
l = sum(wall["hp"] for wall in left)
r = sum(wall["hp"] for wall in right)
exitright = r <= l
if r > l:
r = l + 1
elif r < l:
l = r
def totalside(walls, n, todo, exit_):
res = 0
for i in range(n):
take = min(todo, walls[i]["hp"])
walls[i]["hp"] -= take
todo -= take
mult = (2*take - 1) if todo == 0 and take > 0 and exit_ else 2*take
res += mult * walls[i]["x"]
res %= MOD
return res
res = totalside(right, nright, r, not exitright) - totalside(left, nleft, l, exitright)
res = (res + MOD) % MOD
print(res)
Текстуално објашњење
# Одбијање ### Решење за 30 поена Довољна је проста симулација овог кретања: док год куглица има апсолутну вредност своје позиције не већу од 100, свака секунда кретања се симулира. Води се рачуна о тренутној позицији x, времену од почетка t, брзини dx (која је или 1 или -1) и тренутку најскоријег судара T. У сваком кораку се ажурира позиција x := x + dx) и провери да ли позиција одговара некој од препрека – а у том случају се ажурирају отпорност препреке, брзина и време најскоријег судара. Ово решење даје тачан одговор у временској сложености $$\mathcal{O}(N * \max_i S_i * \max_i|X_i|)%. ### Решење за 50 поена Реч је о једноставној оптимизација претходног приступа. Уместо да се у сваком кораку позиција промени за 1, довољно је водити рачуна о наредној удареној препреци са леве и са десне стране. Време између два судара је тада једнако апсолутној вредности разлике између позиција те две препреке. Најпре треба поделити препреке у два низа: препреке са негативном позицијом и препреке са позитивном позицијом. У та два низа се затим одреде препреке најближе куглици и врши се симулација кретања. Када отпорност неке препреке постане једнака нули, тада се та препрека означи као непостојећа и бира се најближа препрека са ненултом отпорности. Временска сложеност овог приступа је $$\mathcal{O}(N * \max_i S_i * \max_i |X_i| )$. ### Решења за 70 и 100 поена Ова два решења су малтене идентична и разликују се по томе што користе различите алгоритме сортирања: $\mathcal{O}(N^2)$ временске сложености и $\mathcal{O}(N \log N)$ временске сложености. Најпре се, као у претходном решењу, раздвоје низови препрека лево од нуле и препрека десно од нуле. Затим се ти низови сортирају по апсолутној вредности позиције и тако се одређује редослед којим се куглица судара са препрекама. Да ли је последње одбијање са неким левим зидом или десним зидом се одређује поређењем укупних отпорности десних зидова и левих зидова: * ако је укупна отпорност десних зидова r мања или једнака укупној отпорности левих l, тада са леве стране имамо l одбијања, а са десне l+1 одбијање; * у супротном, са леве стране и десне стране имамо по r одбијања. На основу укупног броја одбијања са обе стране је могуће одредити за сваку “деоницу” (простор између две узастопне препреке) колико је пута пређена. На пример, ако је дошло до m одбијања са леве стране, тада је прва деоница (од 0 до првог зида) пређена $2m$ пута, друга 2(m- otp_levih[0]) пута итд, докле год преостали број одбијања не постане негативан. Неопходно је посветити пажњу последњем судару и одузети 1 од броја прелазака последње деонице.Задатак E
Дата Вам је квадратна матрица која садржи само бројеве 0,1 и 2. Ви на сте на позицији 1, а Ваши непријатељи су на позицијама 2. Потребно је израчунати растојање до Вашег најближег непријатеља како бисте дошли до њега. Можете ићи горе, доле, лево и десно. Такође, уколико се налазите на ивици матрице, и уколико се померите у правцу те ивице, појавићете се на пољу на супротној страни те матрице.
Матрица садржи произвољан број 0 и 2, али је само једна 1 у њој, такође и не мора садржати број 2, тада би требало вратити 0.
Опис улаза
У првом је реду ненегативан цео број n који представља величину квадратне матрице. У следећих n редова су садржаји редова квадратне матрице.
Опис излаза
У првом и једином реду излаза треба исписати растојање до Вашег најближег непријатеља.
Решење
n = int(input())
array = []
for v in range(n):
array.append(input())
def ClosestEnemyII(array):
enemies = []
for i, row in enumerate(array):
for j, col in enumerate(list(row)):
if col == '1': px, py = (i, j)
if col == '2': enemies.append((i, j))
moves = []
for x, y in enemies:
no_wrap = abs(px - x) + abs(py - y)
col_wrap, row_wrap = abs(px - x) + abs(py - (y - len(array))), abs(px - (x - len(array))) + abs(py-y)
moves.append(min(no_wrap, col_wrap, row_wrap))
return min(moves) if moves else 0
print(ClosestEnemyII(array))