Основи програмирања: јануар 2024.
Задатак A
Марица, студенткиња природно-математичког факултета, редовно похађа вежбе из предмета Теорија апроксимација и квадратурне формуле. Вежбе су врло једноставне: асистенткиња на табли напише $N$ природних бројева и од студената тражи да их апроксимирају, а затим и квадрирају. Међутим, Марица не познаје довољно ову теорију, па се концентрише на своју омиљену разоноду - бојење датих бројева воденим бојицама.
Марица цифре сваког броја боји на специфичан начин: цифру $1$ боји црвеном, цифру $2$ плавом, цифру $3$ жутом, цифру $4$ наранџастом, цифру $5$ зеленом и цифру $6$ љубичастом бојом. Остале цифре јој нису занимљиве и њих не боји. Наравно, она користи само основне боје - црвену, плаву и жуту. За бојење једне цифре основном бојом потребно јој је $2$ милиграма (mg) одговарајуће боје, док јој је за бојење осталим бојама потребан по $1$ милиграм одговарајућих основних боја: за наранџасту $1\,\text{mg}$ црвене и $1\,\text{mg}$ жуте, за зелену $1\,\text{mg}$ жуте и $1\,\text{mg}$ плаве, а за љубичасту $1\,\text{mg}$ плаве и $1\,\text{mg}$ црвене боје.
Помозите Марици да израчуна колико ће јој милиграма сваке од основних боја бити потребно, како би обојила датих $N$ природних бројева.
Улазни подаци
У првом реду стандардног улаза налази се природан број $N$ - број бројева које Марица планира да обоји.
У наредних $N$ редова налази се по један природан број $A_i$, који представља један од бројева које треба обојити.
Излазни подаци
У првом и једином реду стандардног излаза исписати $3$ цела броја, одвојена са по једним размаком, која представљају број милиграма црвене, плаве и жуте боје, респективно, неопходан Марици за тражено бојење.
Решење
N = int(input())
r = {"crvena": 0, "plava":0, "zuta":0}
for i in range(N):
broj = input()
for cifra in broj:
if cifra == "1":
r["crvena"] += 2
elif cifra == "2":
r["plava"] += 2
elif cifra == "3":
r["zuta"] += 2
elif cifra == "4":
r["crvena"] += 1
r["zuta"] += 1
elif cifra == "5":
r["plava"] += 1
r["zuta"] += 1
elif cifra == "6":
r["crvena"] += 1
r["plava"] += 1
else:
continue
print(str(r["crvena"]) + " " + str(r["plava"]) + " " + str(r["zuta"]))
Текстуално објашњење
Бојење
Решење за $1 \le A_i \le 9$
Сви бројеви су једноцифрени, и познато је колико бројева је унесено. Потребно је проћи кроз сваку од $N$ цифара, утврдити која је, и у складу са бројем који представља додати по $1\,\text{mg}$ одређене две боје (уколико је цифра коју посматрамо $4$, $5$, или $6$), или додати $2\,\text{mg}$ одређене боје (за бројеве $1$, $2$, или $3$), или пак ништа, у супротном. Временска сложеност: $\mathcal{O}(N)$, меморијска: $\mathcal{O}(1)$.
Решење за $N = 1$
Дат је само један број, који може имати било колико цифара. Потребно је проћи кроз сваку од цифара тог броја, утврдити која је, и у складу са бројем који представља поступити као у претходној групи примера. Процес се понавља док се целобројним дељењем броја са $10$ не добије нула. Временска сложеност: $\mathcal{O}(logN)$, меморијска: $\mathcal{O}(1)$.
Главно решењe
Идеја за решавање претходног примера се сада користи на сваком од $N$ унетих бројева појединачно, док се константно води рачуна о количинама фарбе. Временска сложеност: $\mathcal{O}(NlogN)$, меморијска: $\mathcal{O}(1)$.
Задатак B
Добро је познато (још од 1888. године и Ничеовог дела Сумрак идола) да оно што нас не убије - то нас ојача. Тако је и са тачкама, квадратима, такмичарима, па и самом комисијом… Ако већ не може да као раније организује три круга квалификација, комисија може задати три тајна броја (видети прошли круг) и три јавне тачке у равни (гледате их управо). Ако већ тачно три године, још од доба последње пандемије (и другог круга квалификација школске 2020/2021. године), нико и даље не пита како је квадрат?, а он преживи, постаће надквадрат (нем. Überquadrat) и обухватиће све три јавно задате тачке!
Наиме комисија је задала тачно три тачке у Декартовом правоуглом координатном систему у равни дефинисане целобројним координатама $(x_1, y_1)$, $(x_2, y_2)$ и $(x_3, y_3)$. Ваш задатак је да пронађете површину најмањег квадрата са страницама паралелним координатним осама који их садржи, односно обухвата све три задате тачке!
Опис улаза
У прва и једина три реда стандардног улаза налазе се целобројне координате тачака и то: у првом реду $(x_1, y_1)$, у другом реду $(x_2, y_2)$ и у трећем реду $(x_3, y_3)$. У сваком реду координате $x$ и $y$ су раздвојене размаком.
Опис излаза
У првом и једином реду стандардног излаза, исписати површину најмањег квадрата са страницама паралелним координатним осама, односно правама $x=0$ и $y=0$, који обухвата три задате тачке.
Решење
def nadkvadrat(p1, p2, p3):
xmin, xmax = min(p1[0], p2[0], p3[0]), max(p1[0], p2[0], p3[0])
ymin, ymax = min(p1[1], p2[1], p3[1]), max(p1[1], p2[1], p3[1])
dx, dy = xmax - xmin, ymax - ymin
return max(dx, dy)**2
t1 = tuple(map(int, input().split()))
t2 = tuple(map(int, input().split()))
t3 = tuple(map(int, input().split()))
print(nadkvadrat(t1, t2, t3))
Текстуално објашњење
# Надквадрат ### Главно решење За решење задатка довољно је пронаћи масимум и минимум по свакој координати од три задате тачке, а затим квадрирати већу од разлика двеју координата. Другим речима, ако су три тачке у Декартовом координатном систему задате координатама $(x_1, y_1)$, $(x_2, y_2)$ и $(x_3, y_3)$, тада је најпре неопходно пронаћи $x_\text{max} = \text{max}(x_1, x_2, x_3)$ и $x_\text{min} = \text{min}(x_1, x_2, x_3)$, те $y_\text{max} = \text{max}(y_1, y_2, y_3)$ и $y_\text{min} = \text{min}(y_1, y_2, y_3)$. Да се у задатку тражила површина минималног обухватајућег *правоугаоника*, онда би дужине страница тог правоугаоника биле $\Delta x = x_\text{max} - x_\text{min}$ и $\Delta y = y_\text{max} - y_\text{min}$. Међутим, с обзиром да се тражи површина минималног обухватајућег *квадрата*, то је страница квадрата заправо $\text{max}(\Delta x, \Delta y)$, а површина тог квадрата $(\text{max}(\Delta x, \Delta y))^2$ до чега се долази у константној временској и просторној сложености $\mathcal{O}(1)$. Да је уместо три, у општијем случају било задато $N$ тачака у простору, могао би се применити идентичан алгоритам, а његова сложеност била би $\mathcal{O}(N)$, то јест линеарна по броју задатих тачака чије се обухватање квадратом тражи.Задатак C
У месту под називом Љубовија, на фарми је радио фармер Драган (из родног села Петловца понео је надимак Син Драган), познат по својој љубави према питањима која су често остајала неистражена. Но, једно од најдубљих питања живота на селу често је пролазило испод радара - зашто кокошке прелазе пут?
Научници у Србији су одувек били фасцинирани класичним вицем “Зашто је кокошка прешла пут?”, али они су, услед жеље да се ухвате у коштац са питањем од круцијалног значаја за опстанак планете, желели отићи корак даље.
Наиме, одлучили су ангажовати Сина Драгана, како би им он пружио стварне податке о преласцима путева кокошака са своје фарме у Љубовији, а како би даље могли испитати шта је заправо у основи овог феномена.
Син Драган је проблему приступио на следећи начин: Сваког дана је бележио $N$ опсервација, свака од њих је садржала $ID_i$ кокошке (цео број у опсегу од $1$ до $10$), као и страну пута на којој се налазила кокошка $s_i$ ($0$ или $1$).
Помозите Сину Драгану и тиму научника из Србије, тако што ћете на основу података које вам Драган достави, избројати колико пута се десило да је кокошка прешла пут.
Опис улаза
У првом реду стандардног улаза налази се број $N$, који означава број опсервација које је Син Драган забележио.
У наредних $N$ линија стандардног улаза налазе се $ID_i$ и $s_i$, где $ID_i$ означава идентификациони број кокошке, а $s_i$ означава страну пута на којој се кокошка налази у време опсервације.
Опис излаза
У једном реду стандардног излаза исписати колико пута је кокошка прешла пут.
Решење
N = int(input())
last_seen = [0 for _ in range(N)]
crossings = 0
for _ in range(N):
index, current = map(int, input().split())
current +=1
index -= 1
if (last_seen[index] > 0 and (last_seen[index] != current)):
crossings +=1
last_seen[index] = current
print(crossings)
Текстуално објашњење
# Кокошке ### Главно решење Доступно је $N$ опсервација, од којих свака садржи информацију о $1$ од кокошака и њеној позицији. Може се тврдити да је кокошка прешла пут уколико постоје $2$ опсервације о њој, при чему се страна пута разликује. Дакле, потребно је да постоје $2$ опсервације истог индекса, а различитог показивача стране. Податке је потребно сместити тако да се у сваком тренутку може одредити да ли је кокошка са одређеним индексом већ виђена, и на којој страни је виђена. Итерирајући кроз све опсервације, проверити да ли је кокошка из тренутне опсервације већ виђена, као и да ли је претходно виђена на страни супротној од оне из тренутне опсервације. Ова два услова гарантују да је дошло до промене стране, стога повећати бројач који чува резултат, уколико нису испуњени, наставити итерирање даље.Задатак D
На Факултету инжењерских наука акредитован је нови студијски програм - Електротехника и рачунарство, који ће, поред 60 студената који слушају наставу на српском језику, примати и до 30 страних студената, који ће слушати наставу на енглеском језику. Професори са Катедре за електротехнику имају задатак да оформе групе за предстојеће лабораторијске вежбе и дали су прилику страним студентима да доставе нека ограничења/захтеве. Наиме, два студента могу захтевати да буду или да не буду у истом тиму.
Ваш задатак је да одредите број ових ограничења који није задовољен расподелом која је објављена од стране Катедре.
Опис улаза
У првом реду стандардног улаза налази се цео број $X$ (већи или једнак $0$), и односи се на број захтева парова студената који желе радити у истом тиму. С тим у вези, у наредних $X$ линија ће се налазити два имена (раздвојена размаком) студената који морају бити расподељени у исте тимове.
У наредном реду стандардног улаза налази се цео број $Y$ (већи или једнак $0$), и односи се на број захтева парова студената који не желе радити у истом тиму. С тим у вези, у наредних $Y$ линија ће се налазити два имена (раздвојена размаком) студената који морају бити расподељени у различите тимове.
Загарантовано је да се у $X + Y$ линија које се односе на ограничења сваки пар студената може појавити само једном (не постоји могућност да 1 пар студената има противречне захтеве). Уједно, не постоје 2 студента који имају исто име.
У наредном реду стандардног улаза налази се цео број $G$ (већи или једнак $1$), и односи се на тимове из расподеле коју је саставила Катедра. С тим у вези, у последњих $G$ линија ће се налазити по три имена студената (раздвојена размаком) који представљају расподељене тимове.
Имена студената се састоје од великих слова (1 до 10 слова). Сваки студент који се појавио у ограничењима ће се појавити у тачно једном од састављених тимова.
Опис излаза
У једном реду стандардног излаза исписати број између $0$ и $X + Y$, који се односи на број ограничења прекршених предложеном расподелом на тимове.
Решење
must, mustNot = {}, {}
for i in (must, mustNot):
for _ in range(int(input())):
s1,s2 = input().split()
if s1 not in i:
i[s1]=[s2]
else:
i[s1].append(s2)
violations = 0
for _ in range(int(input())):
groups = set(input().split())
for i in groups:
violations += sum(1 for mi in must.get(i,[]) if mi not in groups) + sum(1 for mni in mustNot.get(i,[]) if mni in groups)
print(violations)
Текстуално објашњење
# Групе ### Главно решење Потребно је забележити парове студената који смеју, односно не смеју бити расподељени у исте групе. Како је након објављивања прелиминарног распореда, ради провере прекршених услова, потребно брзо претражити дозвољене/недозвољене парове студената, користе се речници. Први студент при уносу ће бити кључ у одговарајућем речнику, док ће други студент представљати референцирану вредност. Групе се уносе у скупове, опет, ради оптимизације претраге. За сваког члана групе проверити прекршена ограничења, тако што се испита да ли се у групи не налази студент који је по захтеву морао бити пар члана који се посматра, или, да ли се у групи налази студент који по захтеву није смео бити пар члана који се посматра. Поступак се понавља за сваку од група, и на крају је резултат вредност бројача који је инкрементиран на основу поменутих услова.Задатак E
Неша и Лука на часовима информатике највише воле да играју познату игру “папир, камен, маказе”. Након 1024 одигране партије Нешу су болеле руке и игра му је досадила, а час је још увек трајао. Због тога је одлучио да осмисли своју, мало компликованију верзију ове игре.
У Нешиној верзији он је нападач и има војску сачињену од три дивизије: $N_a$ војника који за борбу користе папир (да збуне противника), $N_b$ војника који су спретни у бацању камења, и $N_c$ војника којима су оружје маказе. Лукин циљ у игри је да се одбрани и његова војска изгледа слично: $L_a$ војника у “папир” дивизији, $L_b$ војника у “камен” дивизији и $L_c$ војника у “маказе” дивизији.
Лука треба да распореди своју војску тј. да за сваког свог војника одреди са којом Нешином дивизијом ће се борити, тако да што више Нешиних војника буде поражено. При томе важе следећа правила која се односе на Лукину “папир” дивизију:
- Ако се један Лукин војник из “папир” дивизије бори са Нешином “камен” дивизијом, може да порази два војника.
- Ако се један Лукин војник из “папир” дивизије бори са Нешином “папир” дивизијом, може да порази једног војника.
- Ако се два Лукина војника из “папир” дивизије боре са Нешином “маказе” дизивијом, могу да поразе једног војника.
Из правила се види (иако је то позната чињеница) да је папир јачи од камена а слабији од маказа. Аналогна правила важе и за друге две Лукине дивизије: камен је јачи од маказа а слабији од папира, маказе су јаче од папира а слабије од камена.
Пошто није пратио на часу, Лука не уме сам да дође до најбољег распореда, па му треба ваша помоћ. Који је највећи број Нешиних војника које он може да порази?
Опис улаза
У првој линији стандардног улаза налазе се три ненегативна цела броја: $N_a$ - број Нешиних војника у “папир” дивизији, $N_b$ - број Нешиних војника у “камен” дивизији, $N_c$ - број Нешиних војника у “маказе” дивизији. У другој линији стандардног улаза налазе се три ненегативна цела броја: $L_a$ - број Лукиних војника у “папир” дивизији, $L_b$ - број Лукиних војника у “камен” дивизији, $L_c$ - број Лукиних војника у “маказе” дивизији.
Опис излаза
У првом и једином реду стандардног излаза исписати један ненегативан цео број који представља максималан број Нешиних војника које Лука може да порази.
Решење
n = [0, 0, 0]
l = [0, 0, 0]
def Stage2():
neutral = [0, 0, 0]
score = 0
for i in range(3):
neutral[i] = min(l[i], n[i])
score += neutral[i]
for i in range(3):
j = (i + 2) % 3
bad = min((l[i] - neutral[i]) // 2, (n[j] - neutral[j]))
score += bad
return score
def Branch(i):
if i == 3:
return Stage2()
score_stage2 = Branch(i + 1)
j = (i + 1) % 3
if l[i] > 0 and n[j] == 1:
l[i] -= 1
n[j] -= 1
score_stage2 = max(score_stage2, 1 + Branch(i + 1))
l[i] += 1
n[j] += 1
return score_stage2
n[0], n[1], n[2] = map(int, input().split())
l[0], l[1], l[2] = map(int, input().split())
score = 0
for i in range(3):
j = (i + 1) % 3
good = min(l[i], n[j] // 2)
l[i] -= good
n[j] -= good * 2
score += good * 2
score += Branch(0)
print(score)