Основи програмирања: фебруар 2024.
Задатак A
Миша је замислио три позитивна цела броја - $a$, $b$ и $c$. Никоме није рекао које је бројеве замислио, али је на табли написао четири броја, која се добијају као резултати израза $a+b$, $a+c$, $b+c$ и $a+b+c$, у насумичном редоследу.
Одредити које је бројеве замислио Миша.
Имати у виду да је могуће да су неки од замишљених бројева једнаки, као и да сва три броја могу бити једнака $(a = b = c)$.
Опис улаза
У првом и једином реду стандардног улаза налазе се четири цела броја - $x_1$, $x_2$, $x_3$ и $x_4$ - раздвојена размацима, која представљају резултате израза $a+b$, $a+c$, $b+c$ и $a+b+c$ у насумичном редоследу.
Опис излаза
У једином реду стандардног излаза исписати три тајна броја, раздвојена размацима, сортирана у неопадајућем поретку.
Уколико постоји више различитих решења, исписати било које од њих.
Решење
niz = list(map(int, input().split()))
zbir_svih = max(niz)
niz.remove(zbir_svih)
x = [0, 0, 0]
x[2] = zbir_svih - niz[0]
x[0] = niz[1] - x[2]
x[1] = niz[2] - x[2]
x.sort()
print(str(x[0]) + " " + str(x[1]) + " " + str(x[2]))
Текстуално објашњење
Три тајанствена броја
Главно решењe
Једноставно је закључити да ће највећи од $4$ унета броја представљати збир $3$ тајанствена броја, обзиром да се ради о позитивним целим бројевима. Како су преостала $3$ броја које је Миша писао на табли резултати сабирања $2$ од $3$ замишљена тајанствена броја, сваки од $3$ тајанствена броја може се добити разликом укупне суме и поменутих збирова $2$ члана. Низ је пре штампања потребно сортирати, како би се добио тражени поредак.
Задатак B
У месту под називом Љубовија, на фарми је радио фармер Драган (из родног села Петловца понео је надимак Син Драган), познат по својој љубави према питањима која су често остајала неистражена. Но, једно од најдубљих питања живота на селу често је пролазило испод радара - зашто кокошке прелазе пут?
Научници у Србији су одувек били фасцинирани класичним вицем “Зашто је кокошка прешла пут?”, али они су, услед жеље да се ухвате у коштац са питањем од круцијалног значаја за опстанак планете, желели отићи корак даље.
Наиме, одлучили су ангажовати Сина Драгана, како би им он пружио стварне податке о преласцима путева кокошака са своје фарме у Љубовији, а како би даље могли испитати шта је заправо у основи овог феномена.
Син Драган је проблему приступио на следећи начин: Сваког дана је бележио $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$ опсервација, од којих свака садржи информацију о једној од кокошака и њеној позицији. Може се тврдити да је кокошка прешла пут уколико постоје две опсервације о њој, при чему се страна пута разликује. Дакле, потребно је да постоје две опсервације истог индекса, а различитог показивача стране. Податке је потребно сместити тако да се у сваком тренутку може одредити да ли је кокошка са одређеним индексом већ виђена, и на којој страни је виђена. Итерирајући кроз све опсервације, проверити да ли је кокошка из тренутне опсервације већ виђена, као и да ли је претходно виђена на страни супротној од оне из тренутне опсервације. Ова два услова гарантују да је дошло до промене стране, стога повећати бројач који чува резултат, уколико нису испуњени, наставити итерирање даље.Задатак C
На Факултету инжењерских наука акредитован је нови студијски програм - Електротехника и рачунарство, који ће, поред 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)
Текстуално објашњење
# Групе ### Главно решење Потребно је забележити парове студената који смеју, односно не смеју бити расподељени у исте групе. Како је након објављивања прелиминарног распореда, ради провере прекршених услова, потребно брзо претражити дозвољене/недозвољене парове студената, користе се речници. Први студент при уносу ће бити кључ у одговарајућем речнику, док ће други студент представљати референцирану вредност. Групе се уносе у скупове, опет, ради оптимизације претраге. За сваког члана групе проверити прекршена ограничења, тако што се испита да ли се у групи не налази студент који је по захтеву морао бити пар члана који се посматра, или, да ли се у групи налази студент који по захтеву није смео бити пар члана који се посматра. Поступак се понавља за сваку од група, и на крају је резултат вредност бројача који је инкрементиран на основу поменутих услова.Задатак D
У енигматици, пирамида је тип мозгалице који треба да се попуни са $P$ речи у $P$ редова. Да би се правилно попунила, почиње се од прве речи која се састоји од само једног слова. Свака наредна реч има једно слово више од претходне и може да се добије додавањем једног слова, а затим произвољним мењањем редоследа добијених слова.
Вама је дат низ од $N$ стрингова који се састоје од великих слова енглеске абецеде. Ови стрингови не морају нужно бити речи неког језика, већ могу бити произвољни низови слова. Притом, $k$-ти стринг има дужину тачно $k$. Ваш задатак је да одредите највећи природан број $P$ такав да првих $P$ стрингова чини пирамиду.
Опис улаза
Прва линија стандардног улаза садржи један природан број $N$ - број стрингова. Наредних $N$ линија садржи по један стринг ($k$-ти стринг ће бити дужине тачно $k$), односно низ великих слова енглеске абецеде.
Опис излаза
У прву и једину линију стандардног излаза исписати највећи природан број $P$ такав да првих $P$ стрингова чини пирамиду.
Решење
n = int(input())
#input_strings = ['']
counted_chars = [{}]
p = 0
while p < n:
input_string = input()
counted_char = {char: input_string.count(char) for char in set(input_string)}
consec_diff = 0
for key in counted_char:
consec_diff += abs(counted_char[key] - counted_chars[-1].get(key, 0))
if consec_diff != 1:
break
#input_strings.append(input_string)
counted_chars.append(counted_char)
p += 1
print(p)
Текстуално објашњење
# Пирамида ## Анализа Лако се закључује да се проблем своди на утврђивање да ли пар узастопних стрингова могу бити узастопни редови пирамиде. Провера да ли два стринга могу бити узастопни редови се своди на утврђивање броја појављивања појединих слова енглеског алфабета (над којим су стрингови написани). Ако са $n_x[A], n_x[B], n_x[C], ..., n_x[Z]$ означимо број појављивања, редом, слова $A, B, C, ..., Z$ у стрингу $x$, а са $n_y[A], n_y[B], n_y[C], ..., n_y[Z]$ означимо број појављивања, редом, слова $A, B, C, ..., Z$ у стрингу $y$, онда стрингови $x$ и $y$ могу бити узастопни редови пирамиде ако и само ако важи $$ |n_y[A]-n_x[A]| + |n_y[B]-n_x[B]| + |n_y[C]-n_x[C]+...+|n_y[Z]-n_x[Z]| = 1. $$ ## Смернице за алгоритам Имплементација се своди на проверу да ли парови узастопних стрингова могу бити редови пирамиде. А та провера се своди на одређивање броја појављивања појединих слова у та два стринга. Пребрајање се може извести једним пролазом кроз одговарајући стринг. Поступак се прекида у тренутку када се стигне до пара узастопних стрингова који не могу бити узастопни редови пирамиде или када се стигне до последњег пара стрингова.Задатак 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)