Основи програмирања: јануар 2023.
Задатак A
На твоју адресу стигла је мистериозна порука од непознатог пошиљаоца. Оно што је посебно необично јесте да је порука послата почетком 2023. године, а ова порука стиже средином децембра 2022. године. Отворивши поруку, видиш да је у прилогу видео запис финала светског првенства у фудбалу, које ће тек бити одиграно, и учествоваће репрезентације Аргентине и Француске. Порука такође садржи и “спојлован” коначан резултат утакмице. Ипак, одлучујеш да погледаш овај необичан видео запис из будућности.
На полувремену утакмице, погледаш тренутни резултат утакмице $x:y$ и сетиш се најављеног коначног резултата $a:b$ из поруке. Тог тренутка помислиш да ли је могуће одредити који тим ће следећи дати гол, претпостављајући да је коначан резултат наведен у мистериозној поруци исправан.
Опис улаза
У првом реду стандардног улаза се налазе два природна броја $a$ и $b$ (спојлован резултат). Док се у другом реду стандардног улаза налазе два природна броја $x$ и $y$ (резултат на полувремену).
Опис излаза
У једином реду стандардног излаза исписати:
- prvi уколико је могуће закључити да ће први тим (описан бројевима $a$ и $x$) дати следећи гол
- drugi уколико је могуће закључити да ће други тим (описан бројевима $b$ и $y$) дати следећи гол
- nijedan уколико је могуће закључити да у наставку утакмице неће бити више ниједног гола
- ? уколико није могуће једнозначно закључити који тим ће постићи наредни гол
Решење
a, b = map(int, input().split())
x, y = map(int, input().split())
if x == a and y == b:
print('nijedan')
if x < a and y < b:
print('?')
if x < a and y == b:
print('prvi')
if x == a and y < b:
print('drugi')
Текстуално објашњење
Спојлер
Главно решење
Није тешко уочити да на основу резултата $a:b$ на крају утакмице, као и резултата $x:y$ на полувремену, постоји четири различита случаја:
- $x = a$ и $y = b$, односно да је резултат на крају једнак резултату на полувремену, па у наставку неће бити голова;
- $x < a$ и $y < b$, што даље значи да ће обе екипе постићи гол, па на основу резултата није могуће утврдити која ће екипа забити наредни;
- $x < a$ и $y = b$, што имплицира да ће прва екипа постићи наредни гол;
- $x = a$ и $y < b$, што значи да ће друга екипа постићи наредни гол.
Једноставним постављањем ова четири услова и одговарајућим исписима долази се до траженог решења у константној временској сложености $\mathcal{O}(1)$.
Задатак B
Дат је низ транскација Вашег банковног рачуна у току 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))
Задатак C
Пењете се уз степенице. Потребно је н корака да се дође до врха. Сваки пут се можете попети за $1$ или $2$ степеника. На колико различитих начина се можете попети на врх?
Улазни подаци
У првом је реду ненегативан цео број $n$ ($1 \le n \le 45$) из поставке задатка.
Излазни подаци
У првом и једином реду излаза треба исписати на колико различитих начина се можете попети на врх.
Решење
n = int(input())
def f(n,memo={}):
if n in memo:
return memo[n]
if n ==0:
return 1
if n<0:
return 0
memo[n]= f(n-1) + f(n-2)
return memo[n]
print(f(n))
Задатак D
На једном рачунару се извршава $N$ задатака паралелно. За сваки задатак је познат почетни и крајњи транутак његовог извршавања. Након што задатак заврши са извршавањем он прво мора да сачека да се заврше сви задаци који су почели пре њега пре него што упише свој резултат у меморију. Уписивање у меморију се врши тренутно.
Ваш задатак је да за сваки од $N$ задатака одредите у ком тренутку ће његов резултат бити уписан у меморију.
Опис улаза
Први ред стандардног улаза садржи један цео број $N$. Наредних $N$ редова стандардног улаза садрже два цела броја $A_i$ и $B_i$, почетни и крајњи тренутак задатка.
Опис излаза
У $i$-том реду стандардног изалаза исписати тренутак у ком ће $i$-ти задатак уписати свој резултат.
Решење
N = int(input())
tasks = [[i] for i in range(N)]
for i in range(N):
a, b = map(int, input().split())
tasks[i].extend([a, b])
tasks.sort(key=lambda item: item[1])
m = -1
for task in tasks:
m = max(m, task[2])
task.append(m)
tasks.sort(key=lambda item: item[0])
for task in tasks:
print(task[3])
Текстуално објашњење
# Рачунар Најпре је неопходно уочити да сваки задатак из поставке има свој редни број (индекс) у редоследу задатака, почетак и крај извршавања, те тренутак уписа резултата у меморију који је потребно одредити. Стога је корисно искористити неку од структура која групише ове четири каратеристике сваког задатка. Такође, према поставци, задаци нису сортирани ни према почетном, а ни према крајњем тренутку свог извршавања. ## Квадратно решење Довољно је у две угнежђене петље редоследом проћи по свим задацима и за сваки задатак испитати да ли постоји неки други задатак који је почео пре њега, а који се завршава након њега. Другим речима, у петљама за свака два задатка $i$ и $j$ проверавати да ли је $A_ј < A_i$ и $B_j > B_i$ и симултано ажурирати тражено време уписа у меморију на максимално $B_j$ од задатака који задовољавају претходни услов. Најзад, по редоследу проћи и исписати времена. Како се у свакој од две петље пролази кроз све задатке, ово решење има квадратну временску сложеност, односно $\mathcal{O}(N^2)$, где $N$ представља број задатака. ## Главно решење у логлинеарној сложености Да би се проблем решио на ефикасан начин, могу се задаци уместо по индексу сортирати по времену почетка извршавања. Пошто у тако сортираним задацима након $i$-тог задатка нема задатака који су почели после њега, то је довољно у само једном проласку кроз задатке, водећи рачуна о дотадашњем максимуму, ажурирати време уписа у меморију као тренутну вредност максимума. Најзад, потребно је пре исписа задатке поново сортирати по редоследу учитавања, односно по индексима, како би се у једном проласку исписала тражена времена. Како је операцију сортирања ефикасним алгоритмима могуће извршити у логлинеарној временској сложености $\mathcal{O}(N\log N)$, а како је ово временски најзахтевнија операција у предложеном решењу, то је и укупна сложеност овог решења логлинеарна по броју задатака.Задатак E
Гласа се за границу за пролаз на државно такмичење из атлетике. Сви чланови комисије ће написати на папирић неки број, који ће потом убацити у кутију за гласове. Граница ће се одредити тако што ће се узети медијана свих гласова који су убачени у кутију. Када је најпопуларнији члан комисије Маркос, познатији као „бог и батина“ дошао да гласа, приметио је да нико не обраћа пажњу на кутију са гласовима. Одлучио је да, након што остатак комисије гласа, дође и провири у кутију, открије шта су остали чланови комисије гласали и затим напише онолико гласова колико је минимално потребно да граница буде баш број X који је он замислио.
Посматрамо $Q$ сценарија где је у $i$-том сценарију број који је Маркос замислио $B[i]$. Помозите Маркосу да за сваки сценарио открије колико минимално гласова мора да убаци у кутију за гласове. Гласови који су већ били у кутији су дати низом $A$, дужине $N$.
Опис улаза
У првом реду стандардног улаза се налазе два позитивна цела броја $N$ и $Q$.
У другом реду се налази низ целих бројева $A$.
У трећем реду се налази низ целих бројева $B$.
Опис излаза
За сваки сценарио исписати решење у новом реду.
Решење
import bisect
def custom_binary_search(arr, x):
if arr[len(arr)//2] == x:
return len(arr)//2
if arr[len(arr)//2] < x:
return bisect.bisect_left(arr, x)
else:
return bisect.bisect_right(arr, x) - 1
def custom_linear_search(arr, x):
if arr[0] > x:
return -1
if arr[-1] < x:
return len(arr)
i = len(arr)//2
if arr[i] == x:
return i
if arr[i] > x:
while arr[i] > x:
i -= 1
return i
if arr[i] < x:
while arr[i] < x:
i += 1
return i
N, Q = map(int, input().split())
A = sorted(list(map(int, input().split())))
B = list(map(int, input().split()))
for X in B:
i = custom_binary_search(A, X) # for O(Nlog(N))
#i = custom_linear_search(A, X) # for O(N^2)
mx = max(i, N-i)
mn = min(i+1, N-i)
print(mx - mn)