|
Sva pitanja, predloge ili primedbe u vezi sa takmičenjima iz programiranja
možete slati na e-mail:
tak.prog@gmail.com
U toku perioda za žalbe, sve žalbe možete slati na ovaj isti e-mail.
|
logo by Igor Antolović
|
|
|
zadatak: Moćni rendžeri
|
Moćni rendžeri su superheroji koji brane Zemlju od napada
zlih sila predvođenih kraljicom Ritom i gospodarom Zedom. U
stalnoj borbi protiv zla pomažu im njihovi roboti zvani zordovi.
Ipak, zordovi nemaju neiscrpan izvor energije, već se moraju
dopunjavati s vremena na vreme. U jednoj bici angažovan je
određen broj zordova: neki od njih se bore (i tako troše
energiju), dok se drugi dopunjavaju. Po završenoj bici, zordovi
koji su se borili potrošili su svu energiju, i ne mogu se boriti
u narednim bitkama sve dok se ne dopune, a zordovi koji su se
dopunjavali ostaju puni i spremni da se bore kad zatreba. S
obzirom na to što zle sile u nameri da porobe Zemlju stalno
šalju sve moćnija i moćnija čudovišta, u svakoj bici
potrebno je angažovati sve više i više zordova: preciznije, u
i-toj po redu bici potrebno je angažovati tačno i zordova
(od kojih se neki bore, a ostali se dopunjavaju).
Zordovi se dopunjavaju pomoću solartomske energije. Vođa
Rendžera, Zordon, mora da vodi preciznu evidenciju koliko
zordova se dopunjava u kojoj bici, kako bi znao da svom
pomoćniku, robotu Alfi, kaže koliko solartomske energije
treba da kupi u dućanu na uglu. Ipak, vremena su teška, te i
Zordon kupuje, narodski rečeno, 'na recku'; drugim rečima, nakon
što Rendžeri uspešno odbrane Zemlju i proteraju zle sile iz
vasione (za šta im treba mnogo bitaka), Zordon izmiruje račune s
dućanom.
Ovaj put posao Rendžera bio je zaista težak: od n zordova
koje poseduju (gde je n neparan broj, da zlikovci ne bi mogli
podeliti rendžere na dva jednaka dela i napasti svaki deo
ponaosob), u poslednjoj bici, n-toj po redu, morali su da
angažuju sve! Srećom, u toj bici izvojevali su konačnu
pobedu i zauvek raskrstili sa zlim silama, pa neće biti više
napada (nećemo ni pomišljati šta bi bilo da su se
pokvarenjaci uspeli zadržati još malo i poslati još moćnije
čudovište, koje bi zahtevalo n+1 zordova; samo jedno je
sigurno: u tom slučaju niko od vas ne bi prošao na IOI, jer ne
bi ni bilo IOI, jer ne bi bilo ni Zemlje, ali ostavimo sitnice po
strani). U svoj toj golgoti Zordon je negde zaturio ceduljče na
koje je beležio koliko se zordova dopunjavalo u kojoj bici.
Ostalo mu je zabeleženo samo koji od zordova su na početku (pre
svih bitaka) bili puni a koji prazni, i još može uočiti da su
sada, posle svega, svi zordovi istog stanja (tj. ili su svi puni,
ili su svi prazni). Vlasnik dućana je jako ljut i preti da
će mu zapleniti neke stvari iz Komandnog centra, te vas Zordon
moli za pomoć: odredite koliko je zordova u kojoj bici bilo
dopunjavano.
Ulaz:
(Ulazni podaci se nalaze u datoteci rendzeri.in) U prvom redu ulazne datoteke nalazi se
prirodan, neparan broj n (1 ≤ n < 10^6), broj zordova koje
Rendžeri poseduju. U narednom redu nalazi se niz znakova '+'
i '-', dužine n, gde je i-ti znak jednak '+'
ako je i-ti zord bio pun pre dolaska zlikovaca, a '-' ako
je bio prazan.
Izlaz:
(Izlazne podatke upisati u datoteku rendzeri.out) U i-tom redu izlazne datoteke
treba upisati koliko se zordova dopunjavalo tokom i-te bitke. Ako se zadatak
može rešiti na više načina, ispisati bilo koji.
Primer 1:
rendzeri.in
|
|
rendzeri.out
|
5
-+---
|
|
1
2
0
4
0
|
Objašnjenje.
U pitanju je prvobitna postava Rendžera: Zak, Kimberli,
Bili, Trini i Džejson. Na slici je prikazano kako su se oni
borili: bledom nijansom prikazani su prazni zordovi, a jakim tonom
puni. Vidimo da su na kraju svi zordovi istog stanja (u ovom
slučaju prazni), što se poklapa s uslovom zadatka. Takođe
možemo videti da u i-toj bici učestvuje tačno i zordova
(podsećamo: neki se bore i time troše energiju, a ostatak od
tih i se dopunjuje), kao što je rečeno.
Primer 2:
rendzeri.in
|
|
rendzeri.out
|
7
+++++++
|
|
0
0
0
3
4
0
7
|
|
|
rešenje
|
Najpre opisujemo proceduru pomoću koje, za neparan broj k, postižemo da k datih zordova koji su inicijalno istog stanja nakon k bitaka i dalje budu međusobno istog stanja. Poređajmo tih k zordova ukrug i angažujmo ih redom (ciklično), svaki put nastavljajući tamo gde smo prethodno stali. Kako imamo k zordova i ukupno 1 + 2 + 3 + ... + k = k*(k + 1)/2 angažmana, konstatujući da je ovaj broj deljiv sa k (jer je k neparno), zaključujemo da ćemo stati upravo nakon što obiđemo krug ceo broj puta, pa će zaista na kraju svi zordovi biti istog stanja.
Pogledajmo sada kako se ovo primenjuje na naš problem. Neka je na početku l praznih i n – l punih zordova (moguće je i l = 0), i uzmimo l < n – l (u drugom slučaju rezonujemo potpuno isto). Izdvojmo svih l praznih zordova i još l punih. Preostalih n – 2l zordova jesu svi puni, i njih angažujmo tokom prvih n – 2l bitaka ciklično (tj. prema goreopisanoj proceduri, jer je n – 2l neparan broj), posle čega će oni ostati međusobno istog stanja. U svakoj narednoj bici, recimo i-toj (gde je n > n – 2l), angažujmo sve zordove koji su bili angažovani i u prethodnoj bici, (i – 1)-oj po redu, i njima priključimo jednog od izdvojenih koji je s njima istog stanja. Ovim postupkom postižemo da posle i-te bitke uvek imamo (bar) i zordova istog stanja, te ćemo posle n-te bitke imati n zordova istog stanja, što je i traženo.
|
|
fajl: rendzeri.pas
|
var n,i,l,d:longint;
c:char;
f:text;
procedure ciklicno(n,l:longint);
var ispred:boolean;
begin
ispred:=true;
for i:=1 to n do
begin
if ispred then if i<l then begin
writeln(f,i);
l:=l-i;
end
else begin
writeln(f,l);
l:=i-l;
ispred:=false;
end
else if i<n-l then begin
writeln(f,0);
l:=l+i;
end
else begin
writeln(f,i+l-n);
l:=2*n-i-l;
ispred:=true;
end;
end;
end;
begin
assign(f,'rendzeri.in');
reset(f);
readln(f,n);
for i:=1 to n do
begin
read(f,c);
if c='-' then inc(l);
end;
close(f);
assign(f,'rendzeri.out');
rewrite(f);
if l<n-l then d:=l
else d:=n-l;
ciklicno(n-2*d,l-d);
for i:=d-1 downto 0 do
if ((l-i) mod 2)=((n-2*i+1) mod 4 div 2) then begin
writeln(f,0);
writeln(f,n-2*i);
end
else begin
writeln(f,n-2*i-1);
writeln(f,0);
end;
close(f);
end.
|
|
|