Основи програмирања

БРТСИ1300 / ОЕ1-ОП

View on GitHub

Основи програмирања: јануар 2023.

Задатак A

На твоју адресу стигла је мистериозна порука од непознатог пошиљаоца. Оно што је посебно необично јесте да је порука послата почетком 2023. године, а ова порука стиже средином децембра 2022. године. Отворивши поруку, видиш да је у прилогу видео запис финала светског првенства у фудбалу, које ће тек бити одиграно, и учествоваће репрезентације Аргентине и Француске. Порука такође садржи и “спојлован” коначан резултат утакмице. Ипак, одлучујеш да погледаш овај необичан видео запис из будућности.

На полувремену утакмице, погледаш тренутни резултат утакмице $x:y$ и сетиш се најављеног коначног резултата $a:b$ из поруке. Тог тренутка помислиш да ли је могуће одредити који тим ће следећи дати гол, претпостављајући да је коначан резултат наведен у мистериозној поруци исправан.

Опис улаза

У првом реду стандардног улаза се налазе два природна броја $a$ и $b$ (спојлован резултат). Док се у другом реду стандардног улаза налазе два природна броја $x$ и $y$ (резултат на полувремену).

Опис излаза

У једином реду стандардног излаза исписати:

Решење
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)
Текстуално објашњење # Намештање гласања ### Главно решење Претпоставимо да је низ $A$ сортиран у неопадајућем поретку, да је укупан број елемената низа $N$ и да су елементи низа индексирани бројевима од $0$ до $N-1$. Тада је медијана низа елемент са индексом $N/2$ ()при чему се рачуна целобројни део количника. Нека је $B$ број поена који Маркос жели као границу. Тада разликујемо три случаја Ако је $A[N/2] = B$, онда је медијана већ једнака броју $B$ и Маркос гласа $0$ пута. Ако је $B$ $<$ $A[N/2]$ одређујемо индекс $i$ последњег елемента који није већи од $B$ (ако такав не постоји, онда је $i=-1$). Тада постоји $i+1$ елемената који су мањи од или једнаки $B$ и $N-i-1$ елемената који су већи од $B$, при чему је $i+1 \leq N-i-1$. Да би обезбедили да $B$ буде медијана потребно је да група мањих или једнаких има бар један елемент више од групе већих, па је потребно убацити $N-i-1-(i+1)+1 = N-2i-1$ гласова. Ако је $B>A[N/2]$ одређујемо индекс $i$ првог елемента који није мањи од $B$ ( ако такав не постоји, онда је $i=N$). Тада постоји $i$ елемената који су мањи од $B$ и $N-i$ елемената који су већи од или $B$, при чему је $i \geq N-i$. Да би обезбедили да $B$ буде медијана потребно је да група већих или једнаких има бар онолико елемента колико има мањих, па је потребно убацити $i - (N - i) = 2i-N$ гласова. Сложеност алгоритма је одређена сложеношћу сортирања (која може бити $\Theta(N\log N)$ ) и сложеношћу проналажења последњег елемента који није већи од $B$, односно првог елемента који није мањи од $B$. Ако ово реализујемо као секвенцијално претраживање, сложеност дела који се односи на одређивање одговора на питања ће бити $\Theta(QN)$, па ће укупна сложеност бити $\Theta(N\log N + NQ)$. Ако проналажење описаног елемента реализујемо коришћењем бинарне претраге (коју свакако можемо користити, ако смо низ сортирали), онда је сложеност одређивања одговора на питања $\Theta(Q\log N)$, па је сложеност комплетног алгоритма $\Theta((N+Q)\log N)$.