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

Zadatak sa takmicenja!

[es] :: Art of Programming :: Zadatak sa takmicenja!

Strane: 1 2

[ Pregleda: 5489 | Odgovora: 20 ] > 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
*.verat.net



Profil

icon Zadatak sa takmicenja!25.02.2004. u 15:32 - pre 244 meseci
Citat:

U čast mladih programera Srbije, organizuje se velika predstava na stadionu.
Učesnici su deca predškolskog uzrasta koja svojim rasporedom na terenu prikazuju
razne figure. Da bi cela predstava bila uspešna, deca na početku moraju da stanu
u jedanu vrstu po tačno utvrđenom redosledu. Međutim, deca su vrlo mlada i
nemirna, tako da skoro nikad ne zauzmu potrebni redosled na početku. Reditelj
predstave ih mora pravilno rasporediti što brže kako predstava ne bi kasnila.

Vaš zadatak je da pomognete reditelju da pravilno rasporedi decu. Svako
dete ima jedinstven broj od 1 do n, gde je n ukupan broj dece. Jedini siguran način
da se uspostavi željeni rasporede je da se jedno po jedno dete premesti sa svog
trenutnog mesta u vrsti na njen početak ili kraj, sve dok se ne postigne željeni
raspored. Pomozite reditelju da nađe minimalni broj premeštanja.

Ulaz. U prvom redu tekstualnog fajla ZAD3.DAT nalazi se ceo broj n (1 Ł n Ł
10000), broj dece. U drugom redu nalaze se n celih brojeva, svaka dva su
razdvojena jednim razmakom, koji predstavljaju polazni raspored dece u redosledu
od početka do kraja. U trećem redu fajla nalazi se n celih brojeva, koji predstavljaju
željeni redosled koji deca treba da zauzmu.

Izlaz. U prvi red izlaznog fajala ZAD3.RES upisati minimalni broj premeštanja dece t.
U sledećih t redova izlaznog fajla upisati potrebna premeštanja, svako premeštanje
u jednom redu, u redosledu u kome se izvode. Jedno premeštanja se zapisuju tako
što se u napiše slovo p ili k, a zatim broj deteta koje se premešta na početak,
odnosno kraj reda u zavisnosti od slova.

Primer:

ZAD3.DAT ZAD3.RES

5 3

5 1 4 3 2 k 5

3 1 2 5 4 p 3

k 4




Da li neko ima ideju kako se ovo resava ?

[filmil: code->quote. Nemojte koristiti code ako nije u pitanju stvarno kod, jer onda automatski ostajete bez formula i sl.]

[Ovu poruku je menjao filmil dana 26.02.2004. u 02:24 GMT]
mmmmmm.. aahhhhhh..
e, nije sex nego serem!
 
Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.adsl.zonnet.nl

Jabber: filmil@jabber.org
ICQ: 36601391


+3 Profil

icon Re: Zadatak sa takmicenja!26.02.2004. u 00:22 - pre 244 meseci
Čini mi se da treba početi od kraja.

Zadatak je malo bez potrebe zakomplikovan dvostrukom permutacijom dece. Umesto toga, postavka je mogla da bude samo: deca treba da se poređaju u redosled 1...n, a na početku stoje u proizvoljnom „ispreturanom“ rasporedu. To je sasvim isto, osim što je onda ulazna datoteka kraća za jedan red.

Druga stvar je da minimalno rešenje nije jedinstveno. Na primer, ako postoji samo dvoje dece i redosled je (2,1), to se može raspetljati bilo kao (k, 2) bilo kao (p, 1). Dakle tražimo bilo koje rešenje najmanje dužine.

Što se počinjanja od kraja tiče evo u čemu je stvar. Nemoj gledati prvi potez u premeštanju, već poslednji. U poslednjem potezu se ili dete sa brojem 1 dovodi na prvu poziciju premeštanjem na početak (i to uvek može da se izvede, bez obzira gde dete 1 stoji) ili se dete sa brojem n dovodi na kraj, ili su deca već uređena pa je posao gotov. Pretpostavimo da smo napravili jedan od tih poteza i zabeležimo sa strane koji je potez napravljen.

Sada gledamo preostalu decu. Njih ima n-1, a njihovi brojevi su ili od 1 do n-1 ili od 2 do n, što zavisi od prethodnog koraka. Na njih primenimo isti postupak od malopre. Pretpostavi da posle nekog vremena došao do niza preostale dece koji je uređen u rastućem poretku. Ako si dotle stigao, preostala deca ne treba da se uređuju i sve što ti preostaje je da odštampaš kao rešenje onaj niz premeštanja koji si pravio, ali unazad.

 
Odgovor na temu

Mihailo Kolundzija
Novi Sad

Član broj: 11323
Poruke: 100
*.dialup.ns.ac.yu



+1 Profil

icon Re: Zadatak sa takmicenja!26.02.2004. u 04:00 - pre 244 meseci
Da okušam sreću:

Nađeš element početnog niza koji je najdalji od svoje pozicije u krajnjem
nizu, a nalazi se desno od nje (pozicije u krajnjem nizu). Udaljenost
računaš kao indeks tog elementa u krajnjem nizu. Za slučaj da element nije
desno od svoje pozicije u krajnjem nizu, udaljenost je nula.
Kada si našao taj element, napraviš pomoćni niz u koji ubacuješ samo
elemente početnog niza koji su u krajnjem nizu desno od elemeta koji si
našao u prvom koraku. Ubacuješ ih u redosledu u kojem su u početnom nizu.
Sad posmatraš pomoćni niz i podniz krajnjeg niza desno od elementa iz prvog
koraka, i opet nađeš element koji je najdalji od svoje pozicije u
posmatranom podnizu, a nalazi se levo od nje. Udaljenost računaš kao indeks
s desna u levo. Za slučaj da element nije levo od svoje pozicije u
posmatranom podnizu krajnjeg niza, udaljenost je nula.
Kada si našao ove dve udaljenosti iz prvog i drugog koraka, sabereš ih, i
sačuvaš.

Sad uradiš slično kao u prva dva koraka, samo u obrnutim smerovima (zameniš
"desno" sa "levo" i obratno).

Uporediš dva zbira, i manji ti predstavlja minimalni broj koraka.

Korake konstruišeš na osnovu toga da li si minimum dobio iz prvog, ili
drugog pokušaja.
Za prvi pokušaj:
Element iz prvog koraka staviš na levi kraj, a onda na levi kraj stavljaš
elemente koji su levo od njega u krajnjem nizu, ali u obrnutom redosledu.
Zatim element iz drugog koraka baciš na desni kraj, a onda na desni kraj
pobacaš elemente koji su desno od njega u krajnjem nizu, u pravom
redosledu.
Ako si minimum dobio u drugom pokušaju, opet razmeni "levo" i "desno".

Tvoj primer:

5 1 4 3 2

3 1 2 5 4

Pokušaj prvi.
Udaljenosti:
(5, 0), (1, 0), (4, 0), (3, 1), (2, 3) - dvojka je najdalja
posmatramo pomoćni niz 5 4 (izbacimo 2 1 3 iz početnog) i podniz 5 4 (desno
od dvojke u krajnjem nizu)
Udaljenosti:
(5, 0), (4, 0).
Zbir je 3.

Pokušaj drugi.
Udaljenosti:
(5, 2), (1, 0), (4, 1), (3, 0), (2, 0) - petica je najdalja
posmatramo pomoćni niz 1 3 2 (izbacimo 5 i 4 iz početnog) i podniz 3 1 2
(levo od petice u krajnjem nizu)
Udaljenosti:
(1, 0), (3, 1), (2, 0) - trojka je najdalja
Zbir je 3.

Sad nam je svejedno, pa ćemo, za razliku od tvog primera, da se odlučimo za
prvu varijantu.
Korak prvi: dvojka na levi kraj
Korak drugi: jedinica na levi kraj
Korak treći: trojka na levi kraj

Za varijantu dva (za svaki slučaj, da bude jasnije).
Korak prvi: petica na desni kraj
Korak drugi: četvorka na desni kraj
Korak treći: trojka na levi kraj

Nadam se da nisam napravio neku suludu grešku.
 
Odgovor na temu

Mihailo Kolundzija
Novi Sad

Član broj: 11323
Poruke: 100
*.dialup.ns.ac.yu



+1 Profil

icon Re: Zadatak sa takmicenja!26.02.2004. u 12:30 - pre 244 meseci
On Thu, 26 Feb 2004 05:00:16 CET, Mihailo Kolundzija wrote:

Citat:

> Nadam se da nisam napravio neku suludu grešku.


Izgleda da jesam.
 
Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.decis.nl

Jabber: filmil@jabber.org
ICQ: 36601391


+3 Profil

icon Re: Zadatak sa takmicenja!26.02.2004. u 15:30 - pre 244 meseci
U međuvremenu sam probao da prepevam objašnjenje od sinoć u program.

Pošto problem ima 2D strukturu, može se rešiti u gde je n broj dece, a rekurzija se lepo utopi u obilazak
ove strukture. Izlaz nije baš u formatu koji se traži, i izbacio sam
dvostruku permutaciju ali nadam se da je to u redu.

Ne znam kako se može ići ispod kvadratne složenosti u ovom konkretnom
slučaju, ali ispod ne može nikako jer je
u pitanju samo specifična varijanta sortiranja.

Sledi primer rada. Program je dat u prilogu.

f

P.S. Poruka br. 1000

Izlaz:
Code:

$ python
Python 2.3.1 (#1, Sep 24 2003, 16:45:45)
[GCC 3.2.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import children
>>> a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> children.compute(a)
0 : [ ]

>>> a = [1, 2, 3, 4, 6, 5, 7, 8, 9, 10]
>>> children.compute(a)
5 : [ ('p', 5) ('p', 4) ('p', 3) ('p', 2) ('p', 1) ]

>>>

Prikačeni fajlovi
 
Odgovor na temu

leka
Dejan Lekić
senior software engineer, 3Developers
Ltd.
London, UK

Član broj: 234
Poruke: 2534
*.racasse.se

Sajt: dejan.lekic.org


+2 Profil

icon Re: Zadatak sa takmicenja!27.02.2004. u 08:17 - pre 244 meseci
Haha, Fico fataj aviJon pa da nazdravimo u cast slanja 'iljadite poruke! :)
Dejan Lekic
software engineer, MySQL/PgSQL DBA, sysadmin
 
Odgovor na temu

StMilan

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



Profil

icon Re: Zadatak sa takmicenja!27.02.2004. u 12:59 - pre 244 meseci
Na http://www.yuoi.nis.edu.yu/ imate na dnu tekstove, test primere i resenja sa takmicenja sa kojeg je zadatak. To je bilo Republicko takmicenje prosle godine.

Inace, sto se tice kompikovanja formulacije u ovom slucaju, stavljaju se tako neke vestacke komplikacije, cisto da bi se malo otezalo takmicarima. A i lepse je da se smisli tako neka velika formulacija, umesto dve recenice o dve permutacije i brojevima.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.dial.InfoSky.Net



+2789 Profil

icon Re: Zadatak sa takmicenja!26.03.2004. u 00:20 - pre 243 meseci
A da li ste primetili da uposte nije prilozen sors resenja drugog zadatka sa takmicenja (trouglovi), vec samo izvrsni fajl zad2test.exe i test primeri (ulazne i izlazne datoteke), kao i da je postavka prvog zadatka JAAAKO nepismeno napisana? Mozda je to bio razlog sto na prvom zadatku niko nije osvojio ni jedan poen. Inace mi se ovaj zadatak o kome se diskutovalo (treci na takmicenju) cini znatno tezim od prvog. No, rastumacio sam prilozeni sors resenja zadaka koji je predmet diskusije ove teme i zelim da ga objasnim.


Prvo, data je polazna permutacija dece preko niza p. Na i-tom mestu se nalazi dete sa brojem p[ i ]. Na slican nacin je data preko niza q ciljna permutacija dece.

Drugo, lako se zakljucuje da nema smisla isto dete premestati dva puta. Naime, ako bi se ono premestilo bilo na pocetak bilo na kraj da bi se posle odredjenog broja poteza ponovo premestilo, do iste pozicije bi se doslo i bez njegovog prethodnog premestanja, dakle sa premestanjem manje.

Trece, na osnovu drugog decu mozemo svrstati u tri grupe: onu decu koju smo u nekom premestanju premestili na pocetak, onu decu koju nismo premestali uopste i onu decu koju smo u nekom premestanju premestili na kraj. Nakon svih premestanja deca koju nismo premestali ce se naci desno od sve dece koju smo u nekom premestanju premestali na pocetak, a levo od sve dece koju smo u nekom premestanju premestali na kraj. Tada ce se najpre u vrsti naci deca koju smo prilikom nekog premestanja premestili na pocetak, i to u obrnutom redosledu od redosleda premestanja, potom ce biti rasporedjena deca koju nismo premestali uopste, i to u istom redosledu u kome su bila na pocetku, i na kraju vrste ce biti rasporedjena deca koju smo prilikom nekog premestanja premestili na kraj vrste i to u redosledu premestanja.

Broj premestanja je jednak broju dece koju smo premestali, a to je n- broj dece koju nismo premestali. Znaci, broj dece koja se ne premestaju treba da bude sto veci. Ona se posle svih premestanja nalaze u sredini, i to u istom redosledu koji su zauzimala na pocetku, tako da se problem svodi na pronalazenje najduzeg niza uzastopnih elemenata u ciljnoj poziciji koji rasporedjeni u istom redosledu u pocetnoj poziciji, pri cemu njihove pozicije u pocetnoj poziciji ne moraju biti uzastopne. To su ona deca koju necemo premestati. Nakon toga se deca koja se u ciljnoj poziciji nalaze levo od njih premestaju na pocetak u obrnutom redosledu od redosleda pojavljivanja u ciljnoj poziciji, i na kraju se deca koja su u zavrsnoj poziciji desno od dece koja se nece premestati premestaju na kraj, i to u redosledu pojavljivanja u zavrsnoj poziciji.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.dial.InfoSky.Net



+2789 Profil

icon Re: Zadatak sa takmicenja!26.03.2004. u 10:41 - pre 243 meseci
Filipe, kao sto mozes da vidis, kod ima LINEARNU slozenost. Tacno je da da se niz duzine n NE MOZE sortirati sa manje od log_2(n!) ~ O(n log(n)) upita, ali ovaj problem si pogresno povezao sa sortiranjem, mada lici.

Pretpostavimo da je na pocetku bila data polazna permutacija dece, a da treba decu dovesti u red u rastucem poretku brojeva koje nose. Tada nam je VEC POZNATA zavrsna konfiguracija 1 2 ... n, pa bi se "sortiranje" u nasem slucaju svelo na

Code:

for (i=1; i<=n; i++)
   cout << i << " ";

cout << endl;


No, ovde ih nije potrebno sortirati, vec navesti niz premestanja koji ih dovodi u zeljeni redosled. Gornju ideju nije moguce primeniti na sortiranje jer ovde znamo da su elementi niza prirodni brojevi u rasponu od 1 do n, pri cemu se svaki pojavljuje tacno jeanput, pa nije tesko bez ikakvih izracunavanja napisati krajnji redosled dece.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

StMilan

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



Profil

icon Re: Zadatak sa takmicenja!30.03.2004. u 18:54 - pre 243 meseci
Citat:
Nedeljko:
A da li ste primetili da uposte nije prilozen sors resenja drugog zadatka sa takmicenja (trouglovi), vec samo izvrsni fajl zad2test.exe i test primeri (ulazne i izlazne datoteke), kao i da je postavka prvog zadatka JAAAKO nepismeno napisana? Mozda je to bio razlog sto na prvom zadatku niko nije osvojio ni jedan poen. Inace mi se ovaj zadatak o kome se diskutovalo (treci na takmicenju) cini znatno tezim od prvog.


Izgleda da je taj prvi zadatak pun nekih stamparskih gresaka. Na par mesta fale neke reci. A i taj zadatak je bio samo za laksu kategoriju.

A sta zelis da kazes time da nije prilozen sors resenja drugog zadatka? Mislis li da su test primeri neispravni?
 
Odgovor na temu

Mirko Rajkovača
Subotica

Član broj: 18458
Poruke: 119
*.ptt.yu



Profil

icon Re: Zadatak sa takmicenja!31.03.2004. u 22:35 - pre 243 meseci
Bas bi voleo da mi neko kaže kako da se uradi taj drugi zadatak sa trouglovima,
moraju se ispitati svake tri linije da bi se videlo da li ispunjavaju uslov trougla(a+b>c).
Sto znaci da moramo koristi tri ugneždene for petlje
for (l1=0;l1<n;l1++) //n=5000
for (l2=l1+1;l2<n;l2++)
for (l3=l2+1;l3<n;l3++)
//sledi testiranje


Pa i da nema nista u ove tri petlje to traje "par" minuta, da ne spominjemo taktove koji se utrose na testiranje. A uslov zadatka je da se uradi za manje od 1s.

Ako neko ima ideju kako je ovo moguće neka kaže, jer po meni nema teorije!
Razlika izmedju softvera i hardvera je:
Softver je nesto sto mozes psovati, a hardver je... pa hardver je nesto sto mozes sutati
 
Odgovor na temu

Mihailo Kolundzija
Novi Sad

Član broj: 11323
Poruke: 100
*.reverse.qsc.de



+1 Profil

icon Re: Zadatak sa takmicenja!01.04.2004. u 09:53 - pre 243 meseci
Kakav je to zadatak sa trouglovima?
Inace, ja ne uspevam da pristupim onom sajtu koji je Milan naveo (kaze: "The page cannot be found").
 
Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.decis.nl

Jabber: filmil@jabber.org
ICQ: 36601391


+3 Profil

icon Re: Zadatak sa takmicenja!01.04.2004. u 10:09 - pre 243 meseci
Citat:
Nedeljko:
Filipe, kao sto mozes da vidis, kod ima LINEARNU slozenost.... ovaj problem si pogresno povezao sa sortiranjem, mada lici.


U pravu si; gledajući tvoje objašnjenje nema nikakve sumnje. Bilo mi je sumnjivo da bi bio dozvoljen ulaz od par desetina hiljada elemenata ako je algoritam u najboljem slučaju kvadratni.
 
Odgovor na temu

Mirko Rajkovača
Subotica

Član broj: 18458
Poruke: 119
*.ptt.yu



Profil

icon Re: Zadatak sa takmicenja!01.04.2004. u 12:54 - pre 243 meseci
Mihailo evo ti taj zadatak sa trouglovima:
Citat:
Zadatak 2. Trouglovi

Dat je skup od n duži različitih dužina. Napisati program koji određuje koliko se nepodudarnih trouglova može obrazovati od tih duži. Za obrazovanje trougla se jedna duž može koristiti samo jednom.
Ulaz. U prvom redu tekstualnog fajla ZAD2.DAT je prirodan broj n (n < 5000). U svakom od p narednih redova se nalazi po jedan prirodan broj, dužina jedne od duži. Dužine duži nisu veće od jedne milijarde (1000000000).
Izlaz. U jedinom redu tekstualnog fajla ZAD2.RES nalazi se ceo broj, ukupan broj trouglova koji se mogu obrazovati od zadatih p duži.

Primer:

ZAD2.DAT ZAD2.RES
4 2
2
3
4
6

Ako imaš neku ideju kako ovo da se reši bez testiranja svih kombinacija prosvetli me!
Razlika izmedju softvera i hardvera je:
Softver je nesto sto mozes psovati, a hardver je... pa hardver je nesto sto mozes sutati
 
Odgovor na temu

StMilan

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



Profil

icon Re: Zadatak sa takmicenja!01.04.2004. u 15:54 - pre 243 meseci
Sajt radi, sad sam probao.

Mirko, nemoj da odmah odustajes ako ne znas resenje. Razmisli malo.

Mislim da je ovo resenje, vrlo je moguce da moze i brze.
Sortiras prvo brojeve, izbacis duplikate.
Uzmes dve duzine, trecu biras da bude veca od te dve a manja od njihovog zbira. Binarnom pretragom nadjes taj zbir, odnosno prvu manju duzinu u sortiranom nizu. Na osnovu indeksa tog elementa lako vidis koliko stranica sa one dve cine trouglove.

Slozenost je O(n2log n).
 
Odgovor na temu

Mirko Rajkovača
Subotica

Član broj: 18458
Poruke: 119
*.ptt.yu



Profil

icon Re: Zadatak sa takmicenja!01.04.2004. u 21:29 - pre 243 meseci
Milane hvala ti na upustvu, nisam razmišljao u tom smeru.
Evo uradio sam taj zadatak sa trouglovima ali jos nije tacan za neke testove(npr.Zad29).
Ako neko vidi gde sam napravio grešku neka kaže!
Code:

//---------------------------------------------------------------------------
#include <stdio.h>
#pragma hdrstop
//---------------------------------------------------------------------------
#pragma argsused
int     N,Duzi[5000];
//---------------------------------------------------------------------------
void Load(char *fin)
{
 int i=0;
 FILE *file=fopen(fin,"r");
 fscanf(file,"%d",&N);
 for (i=0;i<N;i++)
  fscanf(file,"%d",&Duzi[i]);
 fclose(file);
}
//---------------------------------------------------------------------------
void Sort()
{
 int i1,i2,a;
 for(i1=0;i1<N;i1++)
  for(i2=1;i2<(N-i1);i2++)
   {
    if (Duzi[i2-1]==Duzi[i2])
     {
      Duzi[i2]=0;
      continue;
     }
    if (Duzi[i2-1]<Duzi[i2])
     {
      a=Duzi[i2-1];
      Duzi[i2-1]=Duzi[i2];
      Duzi[i2]=a;
     }
   }
}
//---------------------------------------------------------------------------
int Find(int value,int from,int to)
{
 int mid=(to+from)/2;
 if (to<from)
  return NULL;
  
 if ((Duzi[mid]<value) && (Duzi[mid-1]>value))
  return mid;
 else
  {
   if (Duzi[mid]<value)
    return Find(value,from,mid-1);
   else
   if (Duzi[mid]>value)
    return Find(value,mid+1,to);
  }

}
//---------------------------------------------------------------------------
int main(int argc, char* argv[])
{
 FILE *file;
 unsigned long int    i1,i2,i3,
        minB,minC,count=0;
 char fin[10],fout[10];
 sprintf(fin,"%s.dat",argv[1]);
 sprintf(fout,"%s.res",argv[1]);
 Load(fin);
 Sort();
 for (i1=0;i1<N-2;i1++)
  {
   minB=Find(Duzi[i1]/2,i1,N);
   for (i2=i1+1;i2<minB;i2++)
    {
     minC=Find(Duzi[i1]-Duzi[i2],minB,N);
     if ( minC>0 )
      count+=minC-i2-1;
    }
  }

 file=fopen(fout,"w");
 fprintf(file,"%u",count);
 fclose(file);
        return 0;
}
//---------------------------------------------------------------------------


Razlika izmedju softvera i hardvera je:
Softver je nesto sto mozes psovati, a hardver je... pa hardver je nesto sto mozes sutati
 
Odgovor na temu

StMilan

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



Profil

icon Re: Zadatak sa takmicenja!01.04.2004. u 22:32 - pre 243 meseci
Pogledaj malo binarnu pretragu. To je najpipaviji deo, iako bi trebalo da je najprostije. U
Code:
if ((Duzi[mid]<value) && (Duzi[mid-1]>value))
bi negde trebalo da stoji >= ili <=. Moguce je vrlo da gresim, ovo sam na brzinu pogledao.
 
Odgovor na temu

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

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



Profil

icon Re: Zadatak sa takmicenja!12.04.2004. u 13:36 - pre 243 meseci
Evo, ja kao vredni mladi programer, uzeo sam jos malo da vezbam zadatke, i dosao do jos jednog problema(prica kaze sledece) :

Citat:

DIJAGONALE
U ravni je dat konveksni ppoligon sa n temena(n<10000).
U poligonu je postavljeno nekoliko dijagonala. Svake dve od tih
dijagonala nemaju zajednickih tacaka ili je jedina zajednicka tacka
neko teme poligona. Tako je poligon podeljen na nekoliko disjunktnih
potpoligona. Napisati program koji odredjuje potpoligon cije su stranice
polaznog poligona i/ili povucene dijagonale tako da u unutrasnjosti
potpoligona nema ni jedne povucene dijagonale polaznog poligona,
a potpoligon ima maksimalan broj temena.


Zadatak je sa saveznog od prosle godine.
Imam ja neke ideje, ali ni jedna mi ne izgleda 100% sigurna(npr, da idem redom pa da obilazim sve potpoligone, ali i tu imam nekoh problema).
mmmmmm.. aahhhhhh..
e, nije sex nego serem!
 
Odgovor na temu

Mihailo Kolundzija
Novi Sad

Član broj: 11323
Poruke: 100
*.reverse.qsc.de



+1 Profil

icon Re: Zadatak sa takmicenja!16.04.2004. u 15:24 - pre 242 meseci
Evo jedne proste ideje sa moje strane, mada sudeci po prethodnim pokusajima, vrlo je moguce da sam se negde z.

Sortiras dijagonale s leva na desno.
Za svaku dijagonalu, pocevsi od najlevlje, nadjes broj tacaka poligona koji su levo od nje, a na osnovu toga i broj tacaka potpoligona ciji je ona "desni kraj" (vodi racuna o broju tacaka levo od prethodne dijagonale). (na kraju ti ostane najdesnija dijagonala, koja obrazuje potpoligon sa tackama desno od sebe).
Posle ovoga imas najveci potpoligon sa trazenim osobinama.
 
Odgovor na temu

Mihailo Kolundzija
Novi Sad

Član broj: 11323
Poruke: 100
*.reverse.qsc.de



+1 Profil

icon Re: Zadatak sa takmicenja!19.04.2004. u 07:42 - pre 242 meseci
Izgleda da niko nije hteo da prokomentarise koju sam glupost napisao, pa cu ja to sad uciniti (sa malim zakasnjenjem, posto ranije nisam imao oklen to da ucinim). Dakle, ona "ideja", najblaze receno, ne valja.
Mozda bi se to moglo uraditi na sledeci nacin.

i) Postavi duzinu najduzeg potpoligona na nulu, upamti jednu tacku poligona koja je i kraj neke od dijagonala (neka ti ona posluzi za pocetak obilazenja po obimu poligona).

ii) Dok ne ispraznis skup dijagonala:
ii.a) Obilazis po obimu poligona dok ne naidjes na tacku koja je kraj neke od dijagonala.
ii.b) Ako je ona i krajnja tacka neke od dijagonala ciji je drugi kraj prethodno upamcena tacka, to znaci da si nasao jedan potpoligon unutar kojeg nema niti jedne dijagonale. Broj tacaka tog potpoligona znas (brojis dok obilazis), i ako je on veci od prethodno nadjenog najduzeg potpoligona, onda postavis najduzi nadjeni potpoligon na ovaj novi. U svom velikom poligonu izbacis tacke tog potpoligona koje nisu krajnje tacke te dijagonale, a iz skupa dijagonala izbacis datu dijagonalu.
ii.c) Upamtis trenutnu tacku.

iii) Na kraju ti je ostao poligon bez ijedne dijagonale. Njemu prebrojis tacke, i ako je duzi od ranije nadjenog najduzeg potpoligona, najduzi postavis na ovaj preostali.
 
Odgovor na temu

[es] :: Art of Programming :: Zadatak sa takmicenja!

Strane: 1 2

[ Pregleda: 5489 | Odgovora: 20 ] > FB > Twit

Postavi temu Odgovori

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