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.

o-timberlend.pas    2,218 b      izvorni kod rešenja
o-timberlend.solution.pdf    85,185 b      rešenje problema
o-timberlend.tests.7z    1,432,636 b      test primeri

zadatak: O-Timberlend

Glavna zanimacija stanovnika Timberlenda je timberbay. Svake godine se proglašava pobednik, a to je stanovnik koji je imao najviše tačnih odgovora. Sem stanovnika, koji su aktivni danju, u Timberlendu žive još growlini i cutlini koji su aktivni noću. Samo tada oni izlaze u timberdolinu i menjaju njen izgled. Growlini sade drveće, posipaju ih magičnim prahom i drveća do jutra porastu. Cutlini opet pojedu celo drvo ne ostavljajući panjeve za sobom.

Rano u jutro dok još nije svanulo stanovnici Timberlenda izvlače iz šešira brojeve Qi, a čim svane moraju brzo da podignu jednu od dve palice: "yes" ili "no" palicu. Palicu "yes" treba podići ako je u Timberdolini moguće postaviti pravugaoni teren za timberbol površine Qi izmedju drveća, a palicu "no" ako to nije moguće. Svaki tačan odgovor donosi poen za godišnju nagradu. (Pod pravougaonim terenom se podrazumevaju samo tereni koji imaju stranice paralelne granicama Timberdoline i kojima su stranice celobrojne.)

Ulaz.

(Ulazni podaci se učitavaju sa standardnog ulaza.) Iz prvog reda standardnog ulaza čitaju se dva broja N i Q. N predstavlja dimenziju kvadratne Timberdoline (2 ≤ N ≤ 100). Q predstavlja broj dogadjaja. U sledećih Q redova nalaze se dogadjaji. Oni mogu biti:

  • grow x y Growlini su posadili drvo na polju (x, y)
  • cut x y Cutlini su pojeli drvo na polju (x,y)
  • vote p Pitanje "da li je u timberdolinu moguće postaviti pravougaoni teren površine p"

(1 ≤ Q ≤ 50000), (1 ≤ pN2), (1 ≤ x, yN), i neće biti više od 365 dogadjaja "vote p" (za svaki dan u godini po jedno odgovor. Setite se proglašenje pobednika je na kraju godine).

Izlaz.

(Izlazne podatke ispisati na standardan izlaz.) Na standardnom izlazu, za svaki dogadjaj "vote p" potrebno je u posebnom redu ispisati "yes" ili "no".

Napomena.

U početku nema nijednog drveta.

Primer 1.

standardni ulaz      standardni izlaz
4 11
grow 1 4
vote 10
vote 12
grow 3 2
vote 7
vote 6
grow 4 3
grow 2 1
cut 3 2
vote 4
vote 9
        
no
yes
no
yes
yes
no

Objašnjenje.

Ilustracija primera iz zadatka.
vote 10 - odgovor je "no" jer nije moguće postaviti pravougaonu oblast povrsine 10
vote 12 - odgovor je "yes" jedna mogucnost prikazana je na slici "Day 1"
vote 7 - odgovor je "no" jer nije moguće postaviti pravougaonu oblast povrsine 7
vote 6 - odgovor je "yes" jedna mogucnost prikazana je na slici "Day 2"
vote 4 - odgovor je "yes" jedna mogucnost prikazana je na slici "Day 3"
vote 9 - odgovor je "no" jer nije moguće postaviti pravougaonu oblast površine 9

fajl: o-timberlend.pas
var Polje, Pom   : Array[0..102, 0..102] of Word;
    Faktx, FaktY : Array[1..100] of Word;
    Dokle, Xmin, Ymin, N, P, Q, i, j, k, x, y, w, Area, BrFakt : Word;
    c: Char;

Function MozeLi:String;
var i, j : Integer;
Begin
  For k := 1 to BrFakt do
    if (FaktX[k] <= n) and (Fakty[k] <= n)
      then for i := 0 to N-1 do
             for j := 0 to N-1 do
               if (i+FaktX[k] <= n) and (j+FaktY[k] <= n)
                 then if Pom[i+FaktX[k], j+FaktY[k]] + Pom[i, j] =
                         Pom[i, j+FaktY[k]] + Pom[i+FaktX[k], j]
                        then Begin
                               MozeLi := 'yes';
                               exit;
                             end;
  MozeLi := 'no';
end;

begin
  readln(N, Q);
  For w := 1 to Q do
  Begin
    Read(c);
    Case C of
    'g' : Begin
            Read(c);Read(c);Read(c);
            Readln(x, y);
            Polje[x,y] := 1;
          end;
    'c' : Begin
            Read(c);Read(c);
            Readln(x, y);
            Polje[x,y] := 0;
          end;
    'v' : Begin
            Read(c);Read(c);Read(c);
            Readln(Area);

          { rastavljanje na parove do korena }

            j := 0;
            For i := 1 to Trunc(Sqrt(Area)) do
              if (Area mod i = 0)
                then Begin
                       Inc(j);
                       FaktX[j] := i;
                       FaktY[j] := Area div i;
                     end;
          { formiranja parova preko korena }

            For i := 1 to j do
            Begin
              Inc(j);
              FaktX[j] := FaktY[i];
              FaktY[j] := FaktX[i];
            end;
            BrFakt := j;

          { Upisujem koliko drveca ima u pravoug. oblasti
            od donjeg levog ugla do [i,j] (dinamika) }

            For i := 1 to N do
              For j := 1 to N do
                Pom[i,j] := Polje[i,j] + Pom[i-1,j] + Pom[i,j-1] + Polje[i,j] - Pom[i-1,j-1];

          { u funkciji MozeLi, vrsi se provera ima li drveca unutar
            svakog pravougaonika koji staje u matrice }

            Writeln(MozeLi);
          end;
    end;
  end;
end.