Основи програмирања: јун 2024.
Задатак A
Марко, будући шаховски велемајстор, сконцентрисано прати шаховску партију Магнуса Карлсена и Хикаруа Накамуре, желећи да провери да ли је тачна тврдња да је играч који побеђује онај који на крају партије има мање преосталог времена на сату.
Наиме, сваки од играча има свој сат на коме прати колико му је времена преостало. На почетку партије сваки од играча на располагању има 90 минута, а након сваког одиграног потеза играчу се на сату додаје 30 секунди. Док је један играч на потезу, време на његовом сату се смањује, а време на сату противника мирује. Потези играча се одвијају наизменично, а партију започиње Магнус.
Нажалост, Марко на крају партије није успео да види колико је играчима преостало времена и сада не може да провери своју тврдњу. Међутим, Марко је на свом папиру записивао колико је времена било потребно играчима за сваки од потеза. Ту ускачете ви - одредите време које је преостало на сатовима играча!
Опис улаза
У првом реду стандардног улаза налази се природан број $n$ ($1 \le n \le 50$), који представља укупан број одиграних потеза.
У $i$-том од следећих $n$ редова приказано је време за које је одигран $i$-ти потез, у формату ММ:СС, где је ММ број минута, а СС број секунди.
Време преостало на сатовима ни у једном случају неће бити мање од 00:00, нити веће од 99:59.
Опис излаза
У првом реду стандардног излаза исписати време које је преостало на Магнусовом сату, а у другом реду време које је преостало на Хикаруовом сату, у формату ММ:СС.
Решење
n = int(input())
magnus = 90 * 60
hikaru = 90 * 60
for i in range(n):
minute, sekunde = map(int, input().split(':'))
ukupno = minute * 60 + sekunde
if (i % 2 == 0):
magnus -= ukupno
magnus += 30
else:
hikaru -= ukupno
hikaru += 30
print(str(magnus // 60).zfill(2) + ':' + str(magnus % 60).zfill(2))
print(str(hikaru // 60).zfill(2) + ':' + str(hikaru % 60).zfill(2))
Текстуално објашњење
Познат је редослед играча на основу редног броја записа, тако да је само потребно водити рачуна о конверзији укупног броја минута и секунди у заједнички формат секунди, као и да сваки завршен потез играчу доноси продужење времена од 30 секунди.
Задатак B
Илија јако воли музику, и јако воли своје пријатеље; те му је пало на памет да организује ултимативну журку на којој ће бити сви његови другари и на којој ће свирати музика коју сви воле. Међутим, да би то испунио, он мора да одлучи који жанр музике да одабере за своје пријатеље.
Илија има $N$ пријатеља ($2 \le N \le 10^5$) који су нумерисани од $1$ до $N$ и сваки пријатељ воли тачно један жанр музике $h_i$ ($1 \le h_i \le N$). Он жели да сви његови пријатељи заволе исти жанр музике како би могли заједно да уживају на његовој журци.
Да би то постигао, Илија планира организовати боемске вечери. Боемско вече се састоји од окупљања свих пријатеља у континуираном распону од $i$ до $j$. То значи да Илија може позвати произвољан број пријатеља, али мора одабирати групе тако да су људи које позива нумерисани узастопно, односно да прате редослед дате нумерације. Током ових вечери, пријатељи размењују мишљења и препоруке о својим омиљеним музичким албумима. Ако постоји жанр музике који више од половине пријатеља у групи воли, након вечери, сви пријатељи у тој групи ће заволети тај жанр. У супротном, ниједан пријатељ неће променити свој укус. На пример, у групи од $16$ пријатеља, $9$ или више њих би требало да воле исти жанр музике да би сви остали променили свој укус и заволели тај жанр.
Илија жели да зна који жанрови музике могу постати омиљени свим његовим пријатељима истовремено. Он може организовати само једно боемско вече у једном тренутку, али може организовати онолико боемских вечери колико је потребно да сви пријатељи заволе исти жанр музике.
Улазни подаци
У првом реду стандардног улаза налази се цео број $T$, који означава број независних тест случајева ($1 \le T \le 10$).
Сваки тест случај је у следећем формату:
У првом реду сваког тест случаја налази се број $N$ за тај тест случај.
У другом реду сваког тест случаја налази се $N$ целих бројева, који се односе на омиљене жанрове музике $h_i$ сваког од $N$ пријатеља, редом.
Излазни подаци
За сваки од $T$ тест примера исписати по једну линију излаза у следећем формату:
Ако је могуће да сви Илијини пријатељи заволе исти жанр музике истовремено, испишите све могуће такве жанрове (у растућем поретку). У супротном, испишите −1.
Решење
def solve(arr):
result = []
for i in range(len(arr) - 1):
if arr[i] == arr[i + 1] or (i < len(arr) - 2 and arr[i] == arr[i + 2]):
result.append(arr[i])
result = sorted(list(set(result)))
if len(result) == 0:
result = [-1]
return result
def main():
T = int(input())
for _ in range(T):
N = int(input())
arr = list(map(int, input().split()))
print(*solve(arr))
if __name__ == "__main__":
main()
Текстуално објашњење
Приметити да у групама пријатеља са 2 или мање члана није могуће променити мишљење сваког од њих, јер не постоји “већина”. За групе од 3 пријатеља, потребно је да $i$-ти и $i+1$-и, или $i$-ти и $i+2$-и члан воле исти жанр музике како би се усагласила сва 3 пријатеља. Могуће је доказати да за сваку групу пријатеља са 3 или више члана унутар које је остварено већински заједничко мишљење (односно сви чланови групе ће након боемске вечери заволети исти жанр) важи да унутар ње постоји група од 3 члана са постигнутом већином, односно група описана 2. реченицом овог објашњења. Акценат је дакле на поменутим групама од 3 члана, и на основу њих се формира резултат од интереса, односно скуп могућих решења.
Задатак C
Радивоје воли да гледа серије на популарном стриминг сервису Студио ФИН. Пошто је Радивоје веома заузет човек, направио је распоред за наредних $N$ ($1\le N \le10^5$) дана када ће гледати своје омиљене серије. Како је овај стриминг сервис претплатнички, сада мора да одлучи како да минимизира износ новца који треба да плати.
Овај стриминг сервис има занимљив систем претплате: претплата на сервис за $d$ узастопних дана кошта $d+K$ ($1\le K \le10^9$) новчића. Претплата може бити започета у било које време, и може се започети нова претплата уколико је тренутна претплата истекла. С обзиром на ово, израчунати минимални износ новца који Радивоје треба да плати да би испунио свој распоред.
Улазни подаци
У првом реду стандардног улаза налазе се цели бројеви $N$ и $K$.
У другом реду се налази $N$ целих бројева који описују дане када ће Радивоје гледати серије: $1 \le d_1 < d_2 < … < d_N \le 10^{14}$.
Излазни подаци
У првом и једином реду излаза треба исписати минималан број новчића који Радивоје мора да издвоји како би испунио жељени распоред.
Решење
N, K = map(int, input().split())
dani = [int(x) for x in input().split()]
rez = 0
for i in range(N):
if i == 0:
# Првог дана сигурно мора да се покрене претплата.
rez += K + 1
else:
# Да ли је оптимално продужити постојећу претплату, или почети нову?
cena_produzenja = dani[i] - dani[i-1]
cena_nove = K + 1
rez += min(cena_nove, cena_produzenja)
print(rez)
Текстуално објашњење
Као што је прокоментарисано, првог дана у низу је сигурно неопходно да отпочне нова претплата. Надаље се на основу описаног начина наплате пореде два начина реализације претплате на основу размака између 2 дана од интереса. Конкретно, бира се боља од опција директног продужења већ започете претплате, или отказивање исте а отпочињање нове када наиђе следећи дан од интереса.
Задатак D
Свима је познато да су Деда Мразови ирваси велики сладокусци! Од свих слаткиша, омиљени су им шећерни штапићи. Због тога је Деда Мраз одлучио да их почасти шећерним штапићима који су преостали након што је поделио новогодишње пакетиће деци широм света, а за шта је имао њихову неизоставну помоћ.
Деда Мраз има укупно $N\;(N \ge 1)$ ирваса, при чему је позната висина сваког од њих, а жели да их нахрани са укупно $M\;(M \le 2 \cdot 10^5)$ шећерних штапића познатих дужина.
Да их не би заболео стомак од превелике количине слаткиша и да се, пре свега, не би препирали око тога коме припада која количина, Деда Мраз планира да храни ирвасе на посебан начин. Наиме, план му је да храни ирвасе штапић по штапић, према задатом редоследу. Сваки штапић ће једним крајем окачити за греду на плафону штале, тако да својим другим крајем тачно додирује тло. Ирвасе ће, затим, поређати према задатом редоследу, а онда једног по једног доводити до шећерног штапића. Сваки ирвас ће дати штапић изгрицкати до своје висине, с обзиром на то да више не може да дохвати. Деда Мраз неће додатно спуштати шећерни штапић у односу на висину на којој га је иницијално закачио. Нажалост, у том случају могуће је да неки од ирваса неће појести ниједан део неког штапића када на њега дође ред, у случају да се штапић у том тренутку налази изнад његове главе.
Након што су сви ирваси имали прилику да грицкају дати шећерни штапић, сваки од њих ће порасти за висину једнаку дужини дела шећерног штапића који је појео. Деда Мраз ће онда закачити следећи штапић на претходно описани начин, а затим поновити процес храњења ирваса једног по једног, увек према истом редоследу.
Након што је направио план, Деда Мраз жели да предвиди и његов исход - помозите му да израчуна висине својих ирваса после ове слатке гозбе!
Опис улаза
У првој линији стандардног улаза дати су бројеви $N$ и $M$, при чему $N$ представља број ирваса, а $M$ број шећерних штапића које Деда Мраз има.
У другој линији стандардног улаза дате су почетне висине свих ирваса, поређане према редоследу у ком ће их Деда Мраз водити до шећерних штапића. Висине ирваса налазе се у опсегу $[1, 10^9]$.
У трећој линији стандардног улаза дате су иницијалне дужине шећерних штапића, поређане по редоследу према ком ће их Деда Мраз, једног по једног, качити за греду. Дужине штапића налазе се у опсегу $[1, 10^9]$.
Опис излаза
У $N$ редова стандардног излаза исписати коначне висине ирваса након што су нахрањени шећерним штапићима, према редоследу у ком су задате њихове иницијалне висине.
Решење
N, M = map(int, input().split())
irvasi = list(map(int, input().split()))
stapici = map(int, input().split())
for s in stapici:
if s <= irvasi[0]:
irvasi[0] += s
else:
pojedeno_trenutno = 0
for i in range(N):
if irvasi[i] > pojedeno_trenutno:
nova_visina = min(irvasi[i], s)
irvasi[i] += nova_visina - pojedeno_trenutno
pojedeno_trenutno = nova_visina
for i in irvasi:
print(i)
Текстуално објашњење
Једноставно се симулира процес једења штапића од стране ирваса. Приметити да се ради ефикасности решења иницијално провери да ли ирвас може појести “цео” штапић, уколико да, може се прескочити исрцпно итерирање кроз ниоз ирваса.
Задатак E
На окружном такмичењу из информатике учествује $N$ такмичара. Њихова имена су $1, 2, \ldots, N$. Сви такмичари раде у великој просторији у којој се налази $N$ рачунара у низу. Имена рачунара су $1, 2, \ldots, N$. Na почетку, такмичар $1$ седи за рачунаром $1$, такмичар $2$ за рачунаром $2$, итд., такмичар $N$ за рачунаром $N$.
Како су такмичари генерално неприпремљени и фрагилни, они се стално жале на рачунаре, подземне воде и промају и траже да се преместе за неки други рачунар. Прецизније, током такмичења се десило тачно $M$ премештања, редом. У $i$-том премештању ($1 \leq i \leq M$) тачно два такмичара мењају места: такмичар који је у том тренутку радио на рачунару $A_i$ сада прелази на рачунар $B_i$ а такмичар који је у том тренутку радио на рачунару $B_i$ прелази на рачунар $A_i$. Могуће је да се током такмичења неки такмичар премести више пута (можда и неколико пута на исти рачунар).
Организатор Програмер Пера води евиденцију о премештању такмичара и сваки пут када постоји бар један такмичар чији се редни број разликује за више од $K$ од редног броја рачунара за којим тај такмичар тренутно ради, Пера се намршти јер се такмичар баш удаљио од свог почетног рачунара, што је сумњиво! Ваш задатак је да након сваког премештања одредите да ли се Пера намрштио.
Опис улаза
У првом реду стандардног улаза налазе се ненегативни цели бројеви $N$, $M$ и $K$, редом, који представљају број такмичара, број премештања и Перин параметар за сумњу. У наредних $M$ редова налазе се по два различита природна броја $A_i$ и $B_i$: редни бројеви рачунара са којих се такмичари међусобно премештају.
Опис излаза
Исписати $M$ бројева, сваки у посебном реду, где је $i$-ти број $1$ уколико се након $i$-тог премештања Пера намрштио а $0$ уколико није.
Решење
n, m, k = map(int, input().split())
r = list(range(1, n+1))
num_suspicious = 0 # trenutni broj sumnjivih takmicara
for i in range(m):
a, b = map(int, input().split())
if abs(a - r[a-1]) > k:
num_suspicious -= 1
if abs(b - r[b-1]) > k:
num_suspicious -= 1
if abs(a - r[b-1]) > k:
num_suspicious += 1
if abs(b - r[a-1]) > k:
num_suspicious += 1
r[a-1], r[b-1] = r[b-1], r[a-1]
if num_suspicious > 0:
print("1")
else:
print("0")
Текстуално објашњење
| Означимо са $R_i$ редни број ученика који седи за рачунаром $i$. На почетку је $R_i = i$ за свако $i = 1, 2, \ldots, N$. У сваком премештању ми практично мењамо места два елемента низа $R$ и након сваког премештања желимо да проверимо да ли постоји неки индекс $i$ за који важи $ | i - R_i | > K$. |
| Поменуту проверу можемо урадити праволинијски: у сваком од $M$ корака заменимо два елемента низа а затим прођемо кроз цео низ и упоредимо $ | i - R_i | $ и $K$. Сложеност овог алгоритма је $O(NM)$ и решава подзадатак 1 ($20$-$30$ поена) али је превише спор за остале подзадатке. |
Приметимо да када вршимо проверу након $i$ премештања, за све индексе $j$ који нису учествовали у првих $i$ премештања важи $R_j = j$; дакле, не морамо проверавати цео низ већ (у $i$-том кораку) само индексе из првих $i$ премештања ($А_1, B_1, A_2, B_2, \ldots, A_i, B_i$; међу њима може бити истих). Ово даје алгоритам сложености $О(M^2)$ што је довољно за прва два подзадатка ($40$-$50$ поена).
| У трећем подзадатку важи $K = N - 3$. Међутим, једини индекси $i$ за које је могуће да важи $ | i - R_i | < N - 3$ су $1, 2, N-1$ и $N$ (остали се не могу довољно “удаљити”; проверити!) па је након сваке замене довољно проверити вредности $R_1, R_2, R_{N-1}$ и $R_N$ што нам даје укупну сложеност $O(N+M)$ и решава овај подзадатак ($20$ поена). |
| Да бисмо решили цео задатак, приметимо да није неопходно стално проверавати пуно индекса већ је довољно да у сваком тренутку памтимо колико има индекса $i$ за које важи $ | i - R_i | > K$; означимо ту количину са $x$ (на почетку је $x = 0$). Поменути индекс постоји акко је $x > 0$. Заменом два елемента низа вредност $x$ се може променити највише за $2$ и разликовањем неколико случајева лако “update”-ујемо $x$ (нпр. ако је $ | A_i - R_{A_i} | \leq K$ и $ | B_i - R_{B_i} | > K$, а $ | A_i - R_{B_i} | > K$ и $ | B_i - R_{A_i} | > K$, тада се након $i$-тог премештања $x$ повећава за $1$, итд.) . Сложеност овог решења је $O(N+M)$ и осваја свих $100$ поена. |