Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Zadatak sa USACO sajta

[es] :: Art of Programming :: Zadatak sa USACO sajta

[ Pregleda: 2940 | Odgovora: 5 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

Član broj: 2386
Poruke: 385
217.26.66.*



Profil

icon Zadatak sa USACO sajta16.05.2004. u 19:24 - pre 241 meseci
I dosao sam (manje vise bez problema) do zadatka Shaping Regions.
Da sumiram problem :
Dat je papir dimenzija a*b,koji je beo (belo=1), i ucitava se n pravougaonika,tako da kad se neki pravougaonik procita (x,y,x1,y1,color), onda se on postavi na taj papir tako da sad taj deo papira na koga smo postavili (to su ucitane koordinate od malopre) ima boju color. Pitanje na kraju je koliko koje boje ima na papiru.

npr :
20 20 3
2 2 18 18 2
0 8 19 19 3
8 0 10 19 4

resenje :
1 91
2 84
3 187
4 38


znaci kome nije jasna postavka (verovatno svima ) samo nek nacrtaju primer i sve ce biti jasno. Moja ideja je bila da kako koji podatak ucitam da tako odmah popunjavam matricu integer-a od m[x+1,y+1] do m[x1,y1] i da usput ako na m[k,z] procitam broj c, onda Ukupno[c] smanjim, a Ukupno[color] povecam, i da m[k,z]:=color. To radi za sve osim za poslednji test primer na kome pukne zbog brzine.

Imate li nekih ideja?

mmmmmm.. aahhhhhh..
e, nije sex nego serem!
 
Odgovor na temu

StMilan

Član broj: 5061
Poruke: 144
*.ptt.yu



Profil

icon Re: Zadatak sa USACO sajta16.05.2004. u 19:49 - pre 241 meseci
Koja su ogranicenja?

Ako su pravougaonici dosta manji od cele te table onda je bolje da gledas koliko se vidi koji pravougaonik .
 
Odgovor na temu

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

Član broj: 2386
Poruke: 385
217.26.66.*



Profil

icon Re: Zadatak sa USACO sajta16.05.2004. u 21:11 - pre 241 meseci
Mislim da me nisi razumeo.
Ja mogu da stavim neki pravougaonik, pa posle njega jos npr. dva pravougaonika, tako da se od prvog pravougaonika vidi samo neki deo koji nema neki pravilni obli(nije pravougaonik).
mmmmmm.. aahhhhhh..
e, nije sex nego serem!
 
Odgovor na temu

-zombie-
Tomica Jovanovic
freelance programmer
ni.ac.yu

Član broj: 4128
Poruke: 3448
*.verat.net

Sajt: localhost


+5 Profil

icon Re: Zadatak sa USACO sajta17.05.2004. u 00:24 - pre 241 meseci
naravno da je razumeo, nego ti njega nisi..

ako je na papiru već obojen jedan pravougaonik, i treba da obojiš sledeći, može da se desi da se stari i novi preklapaju ili ne. ako se ne preklapaju, nemaš ništa novo da računaš, ali ako se preklapaju, to mogu učiniti na jedan od sledećih šest (opštih) načina, tako da umesto jednog crvenog (starog) pravougaonika, posle farbanja novog imaš od nula do četiri novih:

u prvom slučaju treba samo da smanjiš širinu (desnu koordinatu) starog pravougaonika.

u drugom slučaju, ono vidljivo što je ostalo od starog podeliš na dva pravougaonika (kao što je označeno belom linijom).

u trećem ti novi pravougaonik deli stari na dva. u četvrtom imaš tri, u petom četiri, a u šestom slučaju novi pravougaonik potpuno prekriva stari, tako da ga efektivno briše iz računice.

ponoviš ovaj postupak za svaki novi pravougaonik (tako što ispitaš da li se preklapa sa svakim već postojećim), i na kraju sabereš površine..
Prikačeni fajlovi
 
Odgovor na temu

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

Član broj: 2386
Poruke: 385
*.dialup.neobee.net.



Profil

icon Re: Zadatak sa USACO sajta17.05.2004. u 14:33 - pre 241 meseci
Da, shvatio sam da je on mene shvatio tek posto sam malo bolje razmislio o tome sta je on napisao ( bio sam jaaakooooo umoran sinoc, tako da mi mozak nije bas nesto funkcionisao ). Hvala na lepim crtezima ! :) (i uopste na odgovoru)
mmmmmm.. aahhhhhh..
e, nije sex nego serem!
 
Odgovor na temu

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

Član broj: 2386
Poruke: 385
*.dialup.neobee.net.



Profil

icon Re: Zadatak sa USACO sajta17.05.2004. u 14:57 - pre 241 meseci
Evo, upravo sam poslao resenje na usaco.org, i prosli su mi svih 11 test primera. Ideja koju sam koristio je sledeca: Uz svaku stranicu pravougaonika povuem zamisljenu liniju,i na kraju dobijem mrezu. Za svaku oblast te mreze izracunam boju (pocevsi od poslednjeg ucitanog pravougaonika) i to je to.
Posto nisam bas siguran koliko je ovo jasno sto sam rekao, evo ga kod (ako mene pitate ja mislim da je citko napisan).
mmmmmm.. aahhhhhh..
e, nije sex nego serem!
Prikačeni fajlovi
 
Odgovor na temu

[es] :: Art of Programming :: Zadatak sa USACO sajta

[ Pregleda: 2940 | Odgovora: 5 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.