TAKMIČENJA IZ PROGRAMIRANJA


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.

rendzeri.pas    1,750 b      izvorni kod rešenja
rendzeri.tests.rar    160,901 b      test primeri
rendzeri.checker.pas    480 b      izvorni kod programa za testiranje

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 nl punih zordova (moguće je i l = 0), i uzmimo l < nl (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.