Z Trening Zadaci u PHP

[ crnimilosradojevic @ 16.02.2013. 14:41 ] @

Evo posto nisam video da ima otvorena tema za ovakve zadatke u PHP-u, ajd reko da otvorim. Ko je iole razmisljao da nauci programiranje, najverovatnije bi krenuo sa sajtova poput naseg domaceg z treninga, pa eto mogli bismo na jednom mestu da komentarisemo zadatke i resenja naravno! :)

evo za pocetak, ja imam jedan problem i ne ide mi u glavu sta gresim. Evo i teksta zadatka

Citat:

Gradonacelnik Z-sitija je posle dugo odlaganja dozvolio da se otvore picerije u gradu. Posto je grad veliki, a picerije su bile zabranjenje (Zbog zdravlja, bar tako kaze gradonacelnik) odjednom se otvorilo mnogo picerija.

Grad mozemo da zamislimo kao matricu sa NxN kvadrata, gde svaki kvadrat predstavlja jedan blok grada. Svaka picerija raznosi picu samo u okolne blokove, tacnije svaka picerija raznosi picu u svaki blok koji je udaljen najvishe K blokova od bloka gde se picerija nalazi (pri cemu udaljenost predstavlja minimalan broj koraka koje raznosac mora da napravi setajuci se Istocno/Zapadno ili Severno/Juzno, kretanje dijagonalno je zabranjeno u Z-sitiju). Na primer, ako je N = 5, i neka picerija se nalazi na polju (3, 3) i raznosi najvishe 2 bloka udaljenosti, sledeca mapa pokazuje gde sve data picerija raznosi pice.

00X00
0XXX0
XXXXX
0XXX0
00X00

Posto mali Z mnogo voli da jede pice, on zeli da se preseli u blok u kome ce moci da najveci izbor (broj picerija koji raznose pice u taj blok je maksimalan).

Pomozite malom Z-u da nadje koliki je taj maksimum. Odnosno, ukoliko se useli u blok gde ce imati najveci izbor, koliki ce taj ibor biti.

Ulaz:
Sa prve linije standardnog ulaza se ucitavaju dava broja, N i M, oba broja iz intervala [1, 1000]. Broj N predstavlja dimenziju grada u blokovima (Grad ima NxN blokova), a M predstavlja broj picerija u gradu. Zatim se u M redova ucitavaju podaci o svakoj piceriji, i to tri broja X, Y, K, gde X i Y predstavljaju blok u kome se picerija nalazi, 1 <= X,Y <= N, i Broj K, koji predstavlja maksimalnu udaljenost na koju data picerija raznosi pice, 1 <= K <= 1000.

Izlaz:
Na standardni izlaz ispisati jedan broj, koji predstavlja broj picerija koje raznose pice u blok koji ima najveci izbor. (Blok u koj najvishe picerija isporucuju pice).

Primer:
Ulaz:
5 2
3 3 2
1 1 2

Izlaz:
2

Objasnjenje:
Prva picerija raznosi picu u sledece blokove
00X00
0XXX0
XXXXX
0XXX0
00X00

A druga:
00000
00000
X0000
XX000
XXX00

Te je kolicina picerija koje raznosi u dati blok:
00100
01110
21111
12110
11200

Pa je maksimalan broj 2, sto je i resenje.

I skontao sam da je najbolje pretraziti matricu po piceriji i posmatrati je kao podmatricu, i na taj nacin umesto 10^9 dobijemo maksimalno 10^9 iteracija, i to ako bi svaka picerija bila na sredini i pokrivala iste blokove. Evo i mog (doduse netacnog) resenja, i ne mogu da prokljuvim razlog zasto uvek dobijem timeout.

Code:

<?php
$f = fopen("php://stdin","r");
$m = fscanf($f,"%d %d");
$t=  microtime();
while ($m[1]--) {
    $arr = fscanf($f, "%d %d %d");
    $startx=(($temp=$arr[0]-$arr[2])<1)?1:$temp;
    $endx=(($temp=$arr[0]+$arr[2])>$m[0])?$m[0]+1:$temp;
    $starty=(($temp=$arr[1]-$arr[2])<1)?1:$temp;
    $endy=(($temp=$arr[1]+$arr[2])>$m[0])?$m[0]+1:$temp;
    $max=0;

    while ($endx--!=$startx) {
     $realendy=$endy; $realstarty=$starty;
     while ($realendy--!=$realstarty) {
         $step=abs($endx-$arr[0])+abs($realendy-$arr[1]);
         if ($step<$arr[2]+1) {
             $result[$endx][$realendy]++;
             if ($max<$result[$endx][$realendy]) $max++;
         }
     }
    }
}
echo $max;
?>

Ako nadjete neko bolje resenje javite da diskutujemo... I drugi zadaci dolaze u obzir...

Ako vec neko ne zna ili nije jos cuo za z-trening move videti vise o tome ovde

_{[Ovu poruku je menjao crnimilosradojevic dana 16.02.2013. u 22:27 GMT+1]}

_{[Ovu poruku je menjao crnimilosradojevic dana 16.02.2013. u 22:27 GMT+1]}

_{[Ovu poruku je menjao crnimilosradojevic dana 16.02.2013. u 22:28 GMT+1]}