[ stjepang @ 22.08.2007. 13:20 ] @
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 3 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? :) |