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

[Zadatak] Intervali (sa z-trening.com)

[es] :: C/C++ programiranje :: C/C++ za početnike :: [Zadatak] Intervali (sa z-trening.com)

[ Pregleda: 2601 | Odgovora: 0 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

stjepang
Stjepan Grdan
OS

Član broj: 76526
Poruke: 11
*.adsl.net.t-com.hr.



Profil

icon [Zadatak] Intervali (sa z-trening.com)22.08.2007. u 13:20 - pre 202 meseci
Zadatak je preuzet sa Z-Treninga: http://www.z-trening.com/index.php?task=50

Code:
Na brojevnoj pravoj dato je svojim krajevima n intervala. Interval ne sadrži svoje krajnje tacke. Napisati program koji nalazi najveci broj intervala koji se mogu izabrati tako da nemaju zajednickih tacaka.

Ulazni podaci:
U prvom redu standardnog ulaza nalazi se ceo broj n (0 < n <= 5000), broj intervala. U sledecih n redova nalaze se po dva cela broja li i di (-10000 < li < di < 10000) redom levi i desni kraj intervala i (1 <= i <= n ).

Izlaz programa:
Na standardni izlaz ispisati traženi najveci broj intervala koji se mogu izabrati tako da nemaju zajednickih tacaka.

Primer:

Ulaz
4
-1 1
0 5
2 3
5 9

Izlaz


Moje rjesenje ide ovako (pseudokod).
Svaki interval i ima 3 podatka: A(i) je pocetak, B(i) je kraj, a Q(i) je broj intervala j kojima je B(j) < A(i) (ili laicki receno: Q(i) je broj intervala koji se nalaze prije intervala i, a da nemaju zajednickih tocaka).
Na pocetku svaki interval i ima vrijednost Q(i) postavljenu na 1.
Svrha vrijednosti Q je memoizacija.
Code:
sort intervale po vrijednosti A

for i = 1 to N
    for k = 0 to i-1
        if (B(k) <= A(i) and Q(k)+1 > Q(i)) Q(i) = Q(k)+1
    endfor

    if (Q(i) > max) max = Q(i)
endfor

print max


E sad sto tu ne valja? U 10 test primjera samo 2 rade??

NrmMyth, moze pomoc? :)
 
Odgovor na temu

[es] :: C/C++ programiranje :: C/C++ za početnike :: [Zadatak] Intervali (sa z-trening.com)

[ Pregleda: 2601 | Odgovora: 0 ] > FB > Twit

Postavi temu Odgovori

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