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

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

View on GitHub

Основи програмирања: август 2024.

Задатак A

Газда Миле, нама познати земљопоседник, на имању које сте му раније помогли да преуреди поред пашњака има и један омањи воћњак. Одговоран какав јесте, на време је почео да планира бербу.


Наиме, Газда Миле је ангажовао $M$ радника да обере $N$ стабала воћа. Оптималан начин је да се радници распореде што је више могуће једнако, узимајући у обзир и то да је ове године свако дрво родило приближно једнаку количину воћа. Дакле, ако Газда Миле у свом воћњаку, на пример, има $N = 3$ стабла, а ангажовао је $M = 8$ радника, најбоље је да их распореди тако да по $3$ радника беру воће са првог и другог дрвета, док ће остала $2$ радника брати воће са трећег дрвета.


Опис улаза


У првом реду стандардног улаза налази се број $N$, који означава број стабала у воћњаку.


У другом реду стандардног улаза налази се број $M$, који означава број радника које је Газда Миле ангажовао.


Опис излаза


Стандардни излаз треба да садржи $N$ линија - по једну за свако дрво из воћњака. Ако ће $k$ радника брати воће са $i$-тог стабла, тада $i$-та линија стандардног израза треба да садржи $k$ симбола *.


Решење
n = int(input())
m = int(input())
x = n

for i in range(n):
    if (m % x == 0):
        l = (m // x) * "*"
        m -= m // x
    else:
        l = (m // x + 1) * "*"
        m -= m // x + 1
    x -= 1
    print(l)

Задатак B

Свима је познато да су Деда Мразови ирваси велики сладокусци! Од свих слаткиша, омиљени су им шећерни штапићи. Због тога је Деда Мраз одлучио да их почасти шећерним штапићима који су преостали након што је поделио новогодишње пакетиће деци широм света, а за шта је имао њихову неизоставну помоћ.


Деда Мраз има укупно $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)

Задатак 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)

Задатак D

Анастасија и Бојана играју игру са гомилом каменчића која у почетку садржи $S$ каменчића ($1\leq S \leq10^{10^5}$). Девојке се наизменично смењују у узимању каменчића, при чему Бојана увек прва игра. Када је на реду нека од девојака, она мора узети $x$ каменчића из гомиле; где је $x$ било који позитиван број који она одабере, при чему он мора бити палиндром. Ако је гомила празна када нека девојка треба да игра, та девојка губи.


Појашњење: Позитиван број је палиндром ако се чита исто унапред и уназад; примери палиндрома су $1$, $121$ и $9009$. Нуле на почетку нису дозвољене; на пример, $990$ није палиндром.


Сваки од тест случајева се састоји од $T$ ($1\leq T \leq10$) независно одиграних партија игре палиндрома. Исписати ко побеђује у играма ако обе девојке играју оптимално за сваки од тест случајева.


Опис улаза


У првом реду стандардног улаза налази се број $T$, који означава број партија.


У наредних $T$ линија стандардног улаза налази се цео број $S$ који карактерише сваку од $T$ одиграних партија.


Опис излаза


За сваку од одиграних партија у једном реду стандардног излаза исписати која девојка побеђује под претпоставком оптималне игре. Уколико је победница Бојана, исписати $B$,у супротном исписати $A$.


Решење
T = int(input())
for _ in range(T):
	start = input()
	print('A' if start[-1] == '0' else 'B')

Задатак 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")