zadatak sa takmicenja

[ shaDy @ 10.01.2002. 20:16 ] @

Lupam glavu vec neko vreme oko jednog zadatka sa takmicenja iz
programiranja ali nikako da ga resim.

Zadatak:

Prvo se zada sirina i duzina platforme(neki pravougaonik).
onda se zadaju dimenzije n broja pravougaonika(znaci sirina i duzina).
E sad. Treba naci algoritam koji ce da poreda pravougaonike na platformu
uz najbolju iskoristenost prostora, a ukoliko ima vise
pravougaonika nego sto moze stati na platformu onda se ostatak
odbacuje(znaci poredaju se da bude najbolja iskoristenost prostora a ostali
pravougaonici se jednostavno zanemare).

ajde bilo bi super ako bi neko znao ovo da resi

Poz

[ diablo @ 23.01.2002. 12:15 ] @

Citat:

shaDy:
Lupam glavu vec neko vreme oko jednog zadatka sa takmicenja iz
programiranja ali nikako da ga resim.

Zadatak:

Prvo se zada sirina i duzina platforme(neki pravougaonik).
onda se zadaju dimenzije n broja pravougaonika(znaci sirina i duzina).
E sad. Treba naci algoritam koji ce da poreda pravougaonike na platformu
uz najbolju iskoristenost prostora, a ukoliko ima vise
pravougaonika nego sto moze stati na platformu onda se ostatak
odbacuje(znaci poredaju se da bude najbolja iskoristenost prostora a ostali
pravougaonici se jednostavno zanemare).

ajde bilo bi super ako bi neko znao ovo da resi

Poz

Vidi ovako :

ideja je da ti prvo uneses dimenzije platforme,broj n-pravougaonika i njihove dimenzije, ako sam dobro razumeo.Izracunas njihove povrsine (p. n-pravougaonika razunas tako sto u for petlju ubacis niz tako da pri upisu dimenzija izracuna povrsinu i doda prvom clanu niza

A sto se tice najbolje iskoriscenosti prostora, moras taj niz posle da sortiras, u opadajucem poretku(nacrtaj sliku, uzmi proizvoljne dimenzije i videces da je tako), i posle toga ti ostaje da od povrsine platforme oduzmes male povrsine uz 2 uslova da je platforma veca od male povrsine i da je platforma veca ili jednaka 0.

Poz

P.S. Sa kog takmicenja je taj zadatak

[ kajla @ 23.01.2002. 13:34 ] @

Zadatak uopšte nije jednostavan, čuo sam za jednog lika koji je napravio takav program i prodavao ga ovima koji prodaju panele drveta. (panel drveta se može posmatrati kao pravougaonik odrežđenih dimenzija, i kad dođe kupac on naruči jedan panel ali ovi treba da mu iseku na manje pravougaonike koje kupac zadaje - fora je najbolje iskoristiti panel drveta), uglavnom progy je prodavao za 500 DEM. U svakom slučaju ako uspeš bilo bi lepo da postuješ algorotam.

poz.

[ diablo @ 23.01.2002. 21:15 ] @

Ne znam u svakom slucaju ja sam taj program bez problema prvo napisao u Pascalu i radio je besprekorno, a u c++ imam malih poteskoca zbog toga sto se ukoci(!@#@!) iz nepoznatih razloga, i nesto ne mogu da provalim gde je bug, mada nisam ni imao mnogo vremena za to..

A dryga je stvar ako se trazi i da iscrta npr onaj ostatak platforme, o tome nisam razmisljao...mada u navedenom txtu gore ne pise da treba...bas zanimljivo,moracu malo da posvetim tome paznje:)

[ Ivan Dimkovic @ 23.01.2002. 23:08 ] @

Heh.. izgleda na svakom takmicenju utrci slican zadatak - ja sam na takmicenjima bio u III i IV gimnazije (oba puta sam stigao samo do republickog.. na zalost) i secam se da je prvi put bio slican problem, ali sa optimalnim secenjem zice - a drugi put je bilo nesto slicno sa sortiranjem pravougaonika..

U svakom slucaju, resenja za zicu nisam video, ali za pravouganike je bilo nesto relativno trivijalno..

[ Milan Aksic @ 24.01.2002. 01:13 ] @

Citat:

diablo:
Ne znam u svakom slucaju ja sam taj program bez problema prvo napisao u Pascalu i radio je besprekorno, a u c++ imam malih poteskoca zbog toga sto se ukoci(!@#@!) iz nepoznatih razloga, i nesto ne mogu da provalim gde je bug, mada nisam ni imao mnogo vremena za to..

A dryga je stvar ako se trazi i da iscrta npr onaj ostatak platforme, o tome nisam razmisljao...mada u navedenom txtu gore ne pise da treba...bas zanimljivo,moracu malo da posvetim tome paznje:)

Ako vec ne bude islo, bilo bi dobro kada bi postovao taj kod, dokle god, da si stigao :)

[ shaDy @ 24.01.2002. 17:50 ] @

Citat:

diablo:
Poz

P.S. Sa kog takmicenja je taj zadatak

Neznam tacno, drugar mi je rekao za ovaj zadatak. Sa ICM-a ja mislim ali nisam 100% siguran.

Malopre sam naleteo na diskusiju na ovu temu, ako neko nije pogledo
to je" Art Of Programing" -> "problem optimizacije".

Poz