Основи програмирања: септембар 2023.
Задатак A
Седмоструки светски шампион, Џонас Њубауер спрема се за следеће светско првенство у Класичном Тетрису. Пошто зна да његова конкуренција вредно вежба, укључујући и његовог младог ривала Џозефа који се скоро појавио на Тетрис сцени, слободном проценом је закључио да му је потребно још укупно $T$ минута играња како би обезбедио своју осму титулу. Смислио је следећи план тренирања.
Наизменично ће играти Тетрис $X$ минута, па $Y$ минута одмарати очи и пити кафу. Када заврши са одмором, поново ће се вратити на играње Тетриса и тако у круг док укупно не одигра тачно планираних $T$ минута (престаје да тренира у тренутку када заврши $T$-ти минут играња).
Колико му је укупно потребно минута од почетка тренинга (рачунајући и време за одмор између играња) како би одиграо $T$ минута Тетриса?
Бум! Тетрис за Џонаса! <3
Опис улаза
У јединој линији улаза налазе се три цела позитивна броја $X$, $Y$ i $T$.
Опис излаза
У јединој линији излаза исписати колико минута је потребно од почетка тренинга како би Џонас одиграо $T$ минута Тетриса.
Решење
x, y, t = map(int, input().split())
print(t+(t-1)//x*y)
Текстуално објашњење
### Решење за $T \leq 2\cdot X$ и $1 \leq X, T \leq 10^9$: Постоје само две могуће ситуације: ако важи $T \leq X$, онда ће Џонас неће морати да паузира и решење је $T$. Ако $X< T \leq 2\cdot X$, Џонас ће морати да направи једну паузу, па је решење у том случају $T+Y$. ### Решење за $1 \leq X, T \leq 1000$: Можемо симулирати Џонасово играње, или минут по минут или у блоковима од $X+Y$ минута. Ово решење је преспоро да би радило за $100$ поена. ### Главно решење: Приметимо да ће за сваких одиграних пуних $X$ минута, Џонас паузирати $Y$ минута. Таквих блокова ће бити $\lfloor \frac{T}{X} \rfloor$, где је $\lfloor x \rfloor$ цео део од $x$. Онда ће решење бити $\lfloor \frac{T}{X} \rfloor \cdot (X+Y) + T\%X$, где је $T\%X$ остатак при дељењу $T$ са $X$ (односно оно што му остане да одигра након последње паузе). Једини изузетак овој формули јесте ситуација када $X$ дели $Т$. Тада нећемо имати паузу у последњем блоку, па је потребно да од претходне формуле одузмемо $Y$.Задатак B
Дата је матрица $А$ која има две врсте и три колоне (тј. димензија $2 \times 3$). Елементи матрице су цели бројеви који су већи од нуле или једнаки нули. Заменити све елементе матрице који су једнаки нули позитивним целим бројевима (природним бројевима), тако да збир свих елемената у прве две колоне буде једнак збиру елемената у последње две колоне. Ако има више могућих начина да се то изведе, одредити ону замену код које је збир свих елемената матрице минималан. Ако постоји више различитих матрица са минималним збиром, одштампати било коју.
Oпис улаза
У два реда стандардног улаза се налазе по три цела броја који представљају две врсте дате матрице.
Опис излаза
Ако не постоји матрица са траженим особинама исписати $−1$ у првом реду стандардног излаза. Ако постоји матрица са траженим особинама, исписати елементе те матрице, у сваком од два реда по једну врсту матрице.
Решење
def range(x, y):
inf = 1e10
return (x if x else 1) + (y if y else 1), \
(x if x else inf) + (y if y else inf)
def substitute(x, y, sum):
if x == 0 and y == 0:
x = 1
y = sum - 1
elif x == 0:
x = sum - y
elif y == 0:
y = sum - x
return x, y
a, b, c = map(int, input().split())
d, e, f = map(int, input().split())
if b == 0: b = 1
if e == 0: e = 1
u = range(a, d)
v = range(c, f)
if u[1] < v[0] or v[1] < u[0]:
print(-1)
else:
z = max(u[0], v[0])
a, d = substitute(a, d, z)
c, f = substitute(c, f, z)
print(a, b, c)
print(d, e, f)
Текстуално објашњење
Приметимо да ако су збирови подматрице коју чине прве две колоне и подматрице коју чине последње две колоне једнаки, онда су једнаки збир елемената у првој колони и збир елемената у трећој колони. Према томе, провераваћемо да ли можемо да подесимо вредности нула-елемената тако да збир прве и збир треће колоне буду једнаки. Елементи који се налазе у другој (средњој) колони не утичу на збир и због тога је довољно оне који су једнаки нули поставити на један. Нека је $nz$ укупан број нула у првој и трећој колони. Ако је $nz=0$, онда у тим двема колонама нема нити један елемент који се може променити. Ако су збирови тих колона једнаки, онда проблем има решење и то је матрица у којој је само средња колона ажурирана тако што су елементи који су једнаки нули замењени јединицом. Ако је $nz=1$, онда је само један елемент једнак нули и он може променити вредност. Његова вредност се одреди тако да збирови прве и треће колоне буду једнаки. Ако је та вредност већа од нуле, онда проблем има решење. Ако је $nz=3$, онда је само један од 4 елемента у првој и трећој колони различит од нуле. Нека је $k$ редни број колоне у којој се налази тај не-нула елемент. Једно од решења се добија тако што се други елемент у колони $k$ изједначи са један, а елементи у колони $4-k$ (колоне нумерисане бројевима 1, 2 и 3) изједначе са одговарајућим елементима (иста врста) у колони $k$. Ако је $nz=4$, онда су сва четири елемента једнаки нули и треба их променити у један. Ако је $nz=2$, имамо два подслучаја: Не-нула елементи су у истој колони (нека је то колона $k$). Тада елементе у колони $4-k$ трeба изједначити са одговарајућим у колони $k$ (то је једно од могућих решења). Не-нула елементи су у различитим колонама. Нека су вредности тих елемената $a$ и $b$ (обележени тако да је $a \leq b$). Једно од могућих решења се добија тако што се нула-елемент у колони у којој је $b$ изједначи са $1$, а нула-елемент у колони у којој је $a$ изједначи са $b-a+1$. Лако се проверава да ово решење задовољава све услове задатка.Задатак C
Даници је на зимском распусту постало мало досадно па је обећала да ће за сваки природан број N
који јој другари пошаљу, пронаћи њему најближи цео број чије су цифре гледане с лева ка десно поређане у неопадајућем редоследу, а ако има више таквих бројева, пронаћи ће их све и исписати, очекивано, у неопадајућем редоследу. За $m$-тоцифрен природан број $N$ у декадном запису $N=c_{m−1} \cdot 10^{m−1}+c_{m−2} \cdot 10^{m−2}+\ldots+c_2 \cdot 10^2+c_1 \cdot 10^1+c_0 \cdot 10^0$ кажемо да је неопадајући ако му број јединица $c_0$ није мањи од броја десетица $c_1$, број десетица $c_1$ није мањи од броја стотина $c_2$, број стотина $c_2$ није мањи од броја хиљада $c_3$, итд. Другим речима природан број је неопадајући ако и само ако за сваки пар суседних цифара $c_i$ и $c_{i−1}$ важи $c_i \lt c_{i−1}$, при чему $0 \lt t_i \lt m$ и $c_i \in { 0,1,2,3,4,5,6,7,8,9 }$.
Како је и њеним другарима та игра постала занимљива, након почетног загревања са двоцифреним и троцифреним, почели су да јој шаљу све веће и веће бројеве. Помозите малој Даници да упркос томе одржи своје обећање.
Опис улаза
У једином реду стандардног улаза налази се задати природан број $N$ у декадном запису.
Излазни подаци
У једном реду стандардног излаза исписати најближи неопадајући цео број, односно све такве бројеве одвојене размаком уколико их има више од једног.
Решење
def nnm(n):
"""враћа најближи неопадајући број који је мањи или једнак n"""
c = list(str(n))
i = 1
while i < len(c) and c[i] >= c[i-1]:
i += 1
while 0 < i < len(c) and c[i] < c[i-1]:
c[i-1] = str(int(c[i-1]) - 1)
i -= 1
c[i+1:] = '9' * (len(c) - i-1)
return int("".join(c))
def nnv(n):
"""враћа најближи неопадајући број који је већи или једнак n"""
c = list(str(n))
i = 1
while i < len(c) and c[i] >= c[i-1]:
i += 1
c[i:] = c[i-1] * (len(c) - i)
return int("".join(c))
def nn(n):
"""враћа поворку неопадајућих бројева најближих броју n"""
m = nnm(n)
v = nnv(n)
rm = n - m
rv = v - n
if rm < rv:
return (m,)
if rv < rm:
return (v,)
if rm == rv == 0:
return (n,)
else:
return (m, v)
print(*nn(int(input('Unesite proizvoljan prirodan broj: '))))
Текстуално објашњење
Потребно је приметити да провера да ли је одређени број неопадајући не зависи линеарно од вредности тог броја, већ од броја његових цифара који је за природне бројеве у декадном запису пропорционалан $\log_{10}N$. Идејно најједноставније решење највероватније је да се крене од задатог броја $N$ и редом проверава да ли је неопадајући или не, тако што ће се најпре испитати сам задати број $N$, затим $N\pm1$, па $N\pm2$ и тако даље. Међутим, свакако елегантније решење је да се за унети број $N$ на ефикасан начин пронађе најближи неопадајући број већи и најближи неопадајући број мањи од задатог броја, а потом врати онај који се налази на мањој разлици од $N$, односно да се испишу оба, уколико се испостави да су подједнако удаљена. Да би се одредио најближи неопадајући број већи од задатог броја, најпре у низу цифара унетог броја почевши од цифре највећег значаја треба пронаћи прво место где низ постаје опадајући, односно две суседне цифре за које важи $c_{i} > c_{i-1}$, а затим све цифре у опсегу од $c_{0}$ до $c_{i-1}$ променити у $c_{i}$. Тако ће на пример број $N=12321$ бити преправљен у $12333$, а самим тим и одређен најближи неопадајући број већи од задатог броја. Слично томе, како би се одредио најближи неопадајући број мањи од задатог броја, прво се на исти начин пронађе монотоно неопадајући префикс броја $N$, потом $c_{i}$ умањи за један, а цифре у опсегу од $c_{0}$ до $c_{i-1}$ промене у $9$. За горњи пример $N=12321$ то значи да ће најближи неопадајући број мањи од задатог броја бити $12299$. Треба обратити пажњу да декрементирање последње цифре префикса може проузроковати промену његове монотоности, као на пример код $N=12345554321$, па најближи неопадајући број неће бити $12345549999$, ни $12345499999$, већ $12344999999$. Узимајући и тај случај у обзир долази се до најближег неопадајућег броја који је мањи од задатог. Уз напомену да је временска сложеност проналаска најближег неопадајућег броја линеарна по дужини низа цифара, односно логаритамска по вредности задатог броја $N$, преостаје само да се провери који је од два неопадајућа броја ближи, и да се исти испише, чиме је задатак урађен у $\mathcal{O}(\log{N})$ временској сложености.Задатак D
Млади Иван је одлучио да постане озбиљан такмичар из програмирања и његов план да то оствари се састоји из тога да имитира ликове из текстова задатака са такмичења. Баш због тога је за рођендан од родитеља тражио низ природних бројева дужине N, а пошто је добар дечак и вредан ученик, добио је баш такав низ, низ $A_1,A_2,…,A_N$.
Уз низ је добио и шпил од $Q$ картица. Постоје два типа картица:
-
На првом типу картице налазе се четири броја: $1 l r x$. Када се картица овог типа искористи елементи низа са индексима од $l$ do $r$ се промене за $x$ (ако је $x$ позитивно онда се повећају, ако је негативно онда се смање), тј. елемент $A_l$ постаје $A_{l+x}$, елемент $А_{l+1}$ постаје A_{l+1+x} и тако до $A_r$ који постаје $A_{r+x}$.
-
На другом типу картице налази се само број $2$. Када се картица овог типа искористи, Иван записује тренутни збир свих елемената низа на папир
За сваку картицу, ви знате бројеве који су записани на њој. Иван се игра тако да искористи сваку картицу тачно једном, али може их искористити у било ком редоследу. Његова жеља је да укупан збир свих бројева који су записани на папир (услед коришћења картице другог типа) буде што је већи могућ. Пошто је још увек такмичар у тренингу, замолио је вас, искусне такмичаре, да му помогнете да то уради.
Опис улаза
У првом реду улаза се налази природан број $N$ – дужина низа. У другом реду се налази низ $N$ природних бројева $A_1,A_2,…,A_N$ – почетне вредности низа A. У трећем реду се налази природан број $Q$ – број картица. У наредних $Q$ линија налазе се описи картица: уколико ред почиње са $1$, у питању је картица првог типа и у истом реду следе природни бројеви $l$, $r$ i $x$ тим редом; уколико ред почиње са $2$, у питању је картица другог типа.
Опис излаза
На излаз исписати највећи могући збир записаних бројева.
Решење
N = int(input())
S = sum(map(int, input().split()))
cntQ2 = 0
for _ in range(int(input())):
Q = tuple(map(int, input().split()))
if Q[0] == 1 and Q[3] > 0:
S += Q[3]*(Q[2]-Q[1]+1)
elif Q[0] == 2:
cntQ2 += 1
print(S*cntQ2)
Текстуално објашњење
Да би збир одговора на упите био што већи, потребно је да сума елемената низа буде што већа. Сума елемената је највећа онда када елементи низа имају највећу могућу вредност. Највећа могућа вредност се добија након што се примене сви упити типа $1$ у којима се елементи низа увећавају за неку позитивну вредност. Због тога је потребно прво извршити упите типа $1$ код којих се вредност елемената увећавају за позитиввну вредност, а затим све упите типа $2$ и на крају упите типа $1$ код којих се вредности елемената увећавају за негативну вредност.
Ако је сума елемената низа износила $S$, онда након примене упита $1\ l\ r\ x$ сума елемената низа износи $S_n = S + (r - l + 1) \cdot x$.
Према томе, потребно је одредити суму свих елемената након примене свих упита типа $1$ код којих се неки елементи увећавају за неку позитивну вредност (нека та сума износи $S_m$) и број упита типа $2$ (нека је то $n_2$). Тада ће сума одговора на упите изноосити $n_2 \cdot S_m$.
Лако се показује да је сложеност алгоритма $\Theta(n+m)$, где је $n$ број елемената у низу, $m$ укупан број упита.
Задатак E
Mars. Druga najmanja planeta Solarnog sistema, prečnika dva puta manjeg od Zemlje čija je godina otprilike dva puta duža od Zemljine, planeta koja poseduje dva prirodna satelita i drugu najvišu planinu u Sunčevom sistemu. Slučajnost? Tako ne misli Mateja Dejmon, astro-botaničar koji je greškom ostao ostavljen na ovoj planeti kada je peščana oluja omela istraživačku misiju Ares 3.
On na raspolaganju ima svoju bazu, nekoliko kila krompira i plodno marsovsko zemljište dimenzije $N \times N$ metara koje je on izdelio na $N^2$ polja dimenzija $1 \times 1$ metar (raspoređenih u N redova i N kolona) a zatim posadio $M$ krompira u nekih $M$ polja (tih $M$ polja ćemo zvati početna polja). Međutim, zbog posebnog sastava marsovskog zemljišta, krompir je, osim na $M$ početnih polja, izrastao i na svakom polju u čijem se redu ili koloni nalazilo bar jedno od $M$ početnih polja.
Ukoliko vam je poznato gde je Mateja posadio krompire, pomozite mu da izračuna na koliko je ukupno polja izrastao krompir kako bi procenio svoje zalihe za čekanje na misiju Ares 4.
Опис улаза
U prvom redu standardnog ulaza nalaze se dva prirodna broja $N$ i $M$, razdvojena razmakom, koja redom predstavljaju dimenziju zemljišta i broj početnih polja na kojima je zasađen krompir. Zatim sledi opis početnih polja: u narednih $M$ redova nalaze se po dva prirodna broja $x_i$ i $y_i$, razdvojena razmakom, koja označavaju da je $i$-ti krompir zasađen u polju koje se nalazi u $x_i$-tom redu (gledano odozgo nadole) i $y_j$-toj koloni (gledano s leva nadesno).
Опис излаза
U prvom i jedinom redu standardnog izlaza treba ispisati jedan prirodan broj - ukupan broj polja na kojima je izrastao krompir.
Решење
n, m = map(int, input().split())
rows = set()
cols = set()
for _ in range(m):
x, y = input().split()
rows.add(x)
cols.add(y)
a, b = len(rows), len(cols)
print((a + b)*n - a*b)