rZamolio bih nekog da pogleda moj kod.Pada na 3 test primera ( 5 , 7 , 9 ).
Ili , ako neko ima test primere , nek posalje : relja.petrovic@gmail.com.
Unapred hvala.
Pozdrav.
Trebaju i meni 3. i 5. primeri.
(ne rade mi 3,4,5,7,9 ali da ne gnjavim, bice ta dva dovoljna)
Evo ideje koju sam koristio:
Ulazne podatke (precnik i visinu) cuvam u vektoru parova. Nakon ucitavanja taj vektor sortiram u rastuci poredak (po precniku, prvom clanu para). Zatim obavljam sledece korake dok mi taj vektor ima elemenata:
- iz vektora brisem sve elemente cija je visina (drugi clan para) >= od visine nultog clana
- povecavam sol
Na kraju ispisem sol. Sta ne valja?
Ja sam malkice drugacije radio taj zad, mada je i dalje bio greedy. Ne mogu da skontam zasto to ne radi, ali jedno mi pada na pamet - shta radis ako su ti dve kutije istog precnika, kako ih onda sortiras?
Evo shaljem ti 3. primer na pvt.
A, sada sam procitao ponovo zad pa sam skontao gde gresis. Ti ides logikom da ako si nasao kutiju A koja ima najveci precnik, onda sve one koje imaju visinu <= od nje mogu da stanu u nju, ali to nije bas tako za zad. Ti naime treba da smestis nekako te kutije jednu u drugu pa da stavis onda u tu najvecu. Evo recimo primera
prva kutija je 10000 10000
druga kutija je 5000 7000
treca kutija je 3000 8000
Znaci, istina je da mogu da stanu i 2. i 3. kutija u 1., ali 2. ne moze u 3. niti 3. moze u 2., pa ti resenje nece biti 1, ako se ne varam to bi tvoj alg dao, nego ce biti 2 - recimo stavis 2. u 1.
Hmm takodje mi ne radi 5,7,9. Da li bi neko mogao da mi posalje neki od tih test primera na pm ovde ili na ugljesas@gmail.com?
pa obako stvar je da je ovde greedy dobro resenje...jer kad se malo bolje razmisli ne moze da se nadje ni jedan primer na kom ne radi...ali da li postoji neki drugi nacin osim greedy(npr onaj sa sort po visini a jednake po visini po precniku i onda se ide redom dok se nne izaberu sve kutije)?
@MilosRadic, ima jedan nacin slozenosti NlogN,
sortiras po visini prvi, pa onda po sirini, i sada ides po redu i imas neki set vec iskoristenih kutija koje predstavljaju najvecu za svaku hrpu koju si napravio... Sada kako su sortirane i znas da sve imaju visinu manju nego ti, nadjes najvecu po sirini koja stane u trenutnu kutiju i nju maknes iz tog seta i sebe dodas... I na kraju naravno odgovor je broj elementa seta, jer svaki od njih oznacava kutiju u kojoj se nalaze sve ostale koje stanu...
dgleich pa dobro to ti je isto neki greedy,mada verovatno moze da se dokaze da uvek daje tacno resenje
