Основи програмирања: септембар 2024.
Задатак A
Пред Вама је сјајна идеја за стартап компанију, која решава проблем од виталног значаја за опстанак света. Неопходно је основати стартап компанију која ће давати занимљиве и маркетиншки употребљиве називе другим стартап компанијама. Како бисте се адекватно спремили за овакав каријерни искорак, потребно је да у потпуности разумете тривијални алгоритам који је тренутно масовно заступљен. Првобитно се ентитет који је потребно именовати (било да се ради о компанији, услузи или производу) укратко опише речима, а потом се формира скраћеница од употребљених речи.
Речи, наравно, могу бити записане малим или великим почетним словом. Претпоставка је да су кључне речи у опису писане управо великим почетним словом. Сама скраћеница која се формира инцијално би била празна, а потом се редом обрађују речи из описа. Уколико разматрана реч почиње великим словом, њено прво слово постаје део скраћенице; у супротном се реч прескаче. Другим речима, скраћеница бива састављена од првих слова свих речи записаних великим почетним словом, задржавајући редослед који су формирале речи у опису ентитета.
Опис улаза
У првом реду стандардног улаза налази се број $n$, који означава број речи које чине опис.
У наредној линији стандардног улаза налази се опис ентитета сачињен од $n$ речи.
Опис излаза
У једином реду стандардног излаза исписати генерисану скраћеницу.
Решење
n = int(input())
reci = input().split()
skracenica = ""
for rec in reci:
if rec[0].isupper():
skracenica += rec[0]
print(skracenica)
Текстуално објашњење
### Главно решење: Пратећи поставку, ниска која представља скраћеницу јесте састојана од почетних слова речи из описа која су иницијално записана великим словом.Задатак B
Дошао је септембар и ђаци прваци су кренули у школе. Нова генерација за учитељицу Милену доноси са собом одговорност и изазове, али вероватно и доста смеха и забаве. Један релативно тежак задатак за Милену јесте децу упознати са нематерњим енглеским језиком. Милена ипак зна да је ово градиво за децу веома важно, и велики акценат ставља на то. Прво жели да деца науче енглеску абецеду, и она их мотивише да је науче певањем. Наиме, она од деце тражи да певуше нову абецеду као песмицу.
Испоставља се да је овакав приступ деци јако занимљив, али су убрзо почели да смишљају сопствене верзије абецеде и онда њих певуше. Дечије верзије абецеде подразумевају пермутовање 26 слова присутних у оригиналној енглеској абецеди. Милена покушава да запише шта деца певуше, али њих је много, и она понекад заборави шта је чула пре него што стигне да запише. Смислила је нов занимљив задатак за своје ђаке. Сваки од ђака добија слова која је учитељица чула од њих и записала, а на њима је да одреде колико пута су они морали отпевати целу своју абецеду да би Милена могла да чује сва слова која је записала.
Опис улаза
У првом реду стандардног улаза налази се 26 малих слова присутних у енглеској абецеди, поређаних онако како дете пева своју верзију абецеде.
У другом реду стандардног улаза налази се ниска малих слова која представља оно што је учитељица Милена чула и записала.
Опис излаза
У једином реду стандардног излаза исписати колико је најмање пута дете морало да отпевуши целу сопствену верзију абецеде да би учитељица могла да запише сва слова која је чула.
Решење
abeceda=input()
rec=input()
brojac=1
for i in range(len(rec)-1):
if abeceda.index(rec[i])>=abeceda.index(rec[i+1]):
brojac+=1
print(brojac)
Текстуално објашњење
Из једног певушења абецеде се може "чути" више слова само ако је њихов поредак исти и у абецеди и у ономе што је учитељица записала. Дакле, повећање бројача, односно поновно певушење абцеде је неопходно уколико поредак два суседна слова из речи није исти и у дечијој абецеди.Задатак C
Велепознати предузетник Андреј Таталовић одмара у Шумадији; јако му се свиђа гостопримство и ракија, али сматра да квалитет путева није адекватан за његовог Бугатија наранџасте боје. Мишљење јавности о Андреју је у главном подељено у 2 групе: једни величају његов лик и дело, док други сматрају да је обичан муљатор и манипулатор. Свакако, Андреј је увидео прилику да подели своје знање и искуство са амбициозним младим људима, а и да успутно заради још новца. Он жели да у Шумадији отвори факултет за предузетнике.
Блажа је гледајући у Баба Јагину кристалну куглу успео да дозна да постоји $N (1 \leq N \leq 10^5)$ потенцијално заинтересованих кандидата у Шумадији и околини. Уједно је успео чак и да дозна материјално стање те да из њега изведе и максималну висину школарине $c_i (1 \leq c_i \leq 10^6)$ коју је спреман да плати сваки од потенцијалних будућих самофинансирајућих студената ФИНкултета. Блажа наравно да жели да прикупи максималну количину новца од школарина за ФИНкултет како би могао адекватно да награди најбоље, то јест њему лично најлојалније и најоданије наставнике и сараднике, али и да лично буде награђен због свог доприноса (и Баба Јага своје услуге не даје бесплатно). Ако успешно израчунате оптималну висину школарине и укупну количину новца коју Блажа може зарадити, поред поена за задатка имате и јединствену прилику да при (поновном) упису ФИНкултета на свечаности приликом пријема нових студената I године добијете бесплатну Ноблицу!
Опис улаза
У првом реду стандардног улаза налази се број $N$, односно број људи заинтересованих да упишу факултет.
У другом реду стандардног улаза налази се $N$ целобројних вредности $c_1,c_2,…,c_n$, где $c_i$ представља максималну висину школарине коју је $i$-ти кандидат спреман да плати.
Опис излаза
У једином реду стандардног излаза исписати оптималну количину новца, као и висину школарине. Уколико постоји више начина да се дође до исте укупне количине новца, испишите варијанту са најнижом школарином.
Решење
N=int(input())
c=list(map(int,input().split()))
c=sorted(c[0:N])
suma=N*c[0]
cena=c[0]
for i in range(1,N):
if c[i]!=c[i-1]:
trenutna_suma=(N-i)*c[i]
if trenutna_suma>suma:
suma=trenutna_suma
cena=c[i]
print(suma,cena)
Текстуално објашњење
Ако се посматра сортиран низ школарина које су студенти спремни да плате, односно цена, могуће је у једном проласку одредити максимални профит. Наиме, потребно је да се тренутна максимална вредност представи као производ броја студената и тренутне разматране цене, коју је поменути број студената спреман да плати. Пролажењем кроз низ цена, односно разматрањем свих парова броја студената и висине цене коју су спремни да плате, могуће је на основу највеће вредности поменутих производа израчунати максимални профит.Задатак D
Газда Миле, наш вољени пољопривредник, успешно је затворио сезону откупа шљива и жели да се мало опусти. Сетио се да га добар другар Лука већ неко време позива да дође у његово родно село - Горњу Трнаву. Уједно се сетио да је Лука спомињао да се у локалној кафани тамо организује Томбола, сјајна прилика да се опусте и окушају срећу. Нажалост, Миле сазнаје да су органи реда припретили власнику кафане затварањем уколико не престане илегално организовање Томболе. Срећом, договорили су компромисно решење, па се у поменутој кафани (овај пут легално) сада организује Бинго.
За игру Бинго је потребан водитељ игре, као и бубањ са 90 куглица, на којима су исписани природни бројеви од 1 до 90. Пре него што игра почне, сваки од $n$ играча од водитеља добија папирић на коме се налази 25 бројева, распоређених у табелу димензија $5 \times 5$. Свако поље дакле садржи један број између 1 и 90, и сви бројеви на једном папирићу су различити. Такође се на сваком од папирића налази јединствена комбинација бројева.
Када су сви играчи опремљени папирићима и оловкама, игра може да почне. Водитељ извлачи куглице из бубња; прочита наглас број $x_i$ и одлаже извучену куглицу са стране. Играчи онда проверавају своје папириће, и означавају извучени број уколико га имају. Победник је први играч који означи све бројеве у једном реду, колони, или пак дијагонали на папирићу. Победник онда узвикне Бинго! и бива награђен.
Како би игру учинио занимљивијом, водитељ је увео ново правило. Наиме, он мора извући $m$ куглица из бубња пре него што се сме огласити победник. Водитељ је онда у следећој итерацији игре извукао $m$ куглица, и истог тренутка настала је галама: сви играчи су у глас викали Бинго!.
Водитељ је сада збуњен и није сигуран коме може веровати. Ако знате комбинације на папирићима играча, све бројеве који су извучени, као и број извучених куглица, одредите играче који су заправо означили читав ред,колону или дијагоналу.
Опис улаза
У првом реду стандардног улаза налази се природан број $n$ ($1 \le n \le 50$), који представља укупан број играча.
У наставку следи $n$ пута по $6$ редова, таквих да:
- Први од редова садржи ниску од највише 20 слова, која означава име играча. Засигурно не постоје 2 играча истог имена.
- Наредних 5 редова садржи по 5 природних бројева, односно комбинација од 25 бројева са листића играча.
У наредном реду стандардног улаза налази се природан број $m$ ($1 \le m \le 90$), односно број куглица које водитељ мора извући пре проглашења победника игре.
У последњем реду стандардног улаза налази се $m$ природних бројева између 1 и 90, односно бројеви које је извукао водитељ.
Опис излаза
У првом реду стандардног излаза исписати број $k$, број играча који имају Бинго! након извлачења $m$ куглица.
У наредних $k$ редова исписати имена играча, оним редоследом којим су унети као улазни податак.
Решење
def check_bingo(board, numbers):
for i in range(5):
for j in range(5):
if board[i][j] in numbers:
board[i][j] = 0
for i in range(5):
if board[i][0] == board[i][1] == board[i][2] == board[i][3] == board[i][4] == 0:
return True
for i in range(5):
if board[0][i] == board[1][i] == board[2][i] == board[3][i] == board[4][i] == 0:
return True
if board[0][0] == board[1][1] == board[2][2] == board[3][3] == board[4][4] == 0:
return True
if board[0][4] == board[1][3] == board[2][2] == board[3][1] == board[4][0] == 0:
return True
return False
n = int(input())
names = []
boards = []
for i in range(n):
name = input()
board = []
for j in range(5):
board.append(list(map(int, input().split())))
names.append(name)
boards.append(board)
m = int(input())
numbers = list(map(int, input().split()))
bingo = []
for i in range(n):
if check_bingo(boards[i], numbers):
bingo.append(names[i])
print(len(bingo))
for name in bingo:
print(name)
Текстуално објашњење
Срж решења јесте дефинисање функције која адекватно проверава да ли играч има “Бинго!”, односно, која пореди вредности на главној и споредној дијагонали матрице, као и њеним колонама и врстама. Првобитно се означе бројеви од интереса, овде конкретно вредношћу 0. Затим се проверава да ли играч на свом листићу има 5 суседних означених бројева, што га чини валидним добитником игре. Потребно је за сваког од играча проверити да ли је на основу извучених бројева могуће да је добитник игре.
Задатак E
У канцеларији једног технолошког стартапа у центру града ради много запослених који се бавe разним пројектима и задацима. Канцеларију је окупирало $N(2 \leq N \leq 10^5)$ радника, и постоји списак свих запослених. На списку су радници индексирани редом бројевима $1,2,3,…,N$. Радници су подељени у два тима, и то тим A и тим B.
Како би потпомогли мотивацију радника да постигну оптималне резултате, надређени су сваком запосленом наредили да током радног времена надгледа одређен број колега. Листа радника које $i$-ти запослени надгледа почиње самим собом (радник са индексом $i$), све до радника са индексом $E_i$ (укључујући и радника са индексом $E_i$; $\quad i \leq E_i \leq N$).
Међу запосленима у поменутој канцеларији се налазе и лидери тимова A и B. Лидери тимова се одликују тиме што списак радника које надгледају мора садржати све чланове њиховог тима, или пак лидера другог тима (а потенцијално и оба истовремено). Главни менаџер Јасна не зна ко су лидери, али има доступне све спискове. Помозите Јасни тако што на основу спискова утврдите могући број парова лидера тимова A и B.
Опис улаза
У првом реду стандардног улаза налази се број $N$, односно број радника у канцеларији.
У другом реду стандардног улаза налази се ниска дужине $N$, где $i$-ти карактер означава тим којем припада $i$-ти радник.
У другом реду стандардног улаза налазе се $E_1,E_2,…,E_N$, где $E_i$ означава последњег радника са целокупног списка којег надгледа $i$-ти радник.
Опис излаза
У једином реду стандардног излаза исписати могући број парова лидера тимова A и B.
Решење
N = int(input())
s = input()
arr = list(map(int, input().split()))
arr = [x - 1 for x in arr]
eA, eB, lA, lB = -1, -1, -1, -1
for i in range(N - 1, -1, -1):
if (s[i] == 'A'):
eA = i
if (s[i] == 'B'):
eB = i
for i in range(N):
if (s[i] == 'A'):
lA = i
if (s[i] == 'B'):
lB = i
ans = 0
if (arr[eA] >= lA):
for i in range(eA):
if (i == eB):
continue
if (s[i] == 'B' and arr[i] >= eA):
ans += 1
if (arr[eB] >= lB):
for i in range(eB):
if (i == eA):
continue
if (s[i] == 'A' and arr[i] >= eB):
ans += 1
if ((arr[eA] >= lA or (eA <= eB and arr[eA] >= eB)) and (arr[eB] >= lB or (eB <= eA and arr[eB] >= eA))):
ans += 1
print(ans)
Текстуално објашњење
Приметити да сваки радник надгледа себе и неколико радника који се налазе иза њега на целокупном списку, односно немогуће је да постоји пар радника који надгледају један другог. С тим у вези, или ће први члан тима А на списку бити уједно лидер тима А, или ће први члан тима B на списку бити лидер тима B (или оба истовремено). Иницијално проверимо да ли први припадник тима А надгледа све чланове свог тима, односно да ли је лидер тима А; а затим уколико јесте проверавамо број могућих лидера тима B (или први са списка који надгледа све, или члан тима B којег надгледа утврћени лидер тима А). Потребно је поновити исти поступак, с тим да се проверава да ли је први члан тима B уједно и лидер, а онда пребројати могуће парове, односно могуће лидере тимова А.