[Help] C++ feladat, nem tudom megoldani

 ( mukso | 2011. november 29., kedd - 20:18 )

sziasztok, elég fontos lenne ha ezt a feladatot meg tudná oldani valaki.

Nevesincs város polgármestere elhatározta, hogy értékesíti a város mellett levő téglalap alakú földdarabot. A földet egyforma méretű parcellákra osztotta.

A polgármester úgy döntött, hogy a parcellákat nyilvános pályázat keretében adja el, azaz egy adott határidőig minden érdeklődő lezárt borítékban leadhatja ajánlatát. Egy pályázó csak egy ajánlatot nyújthat be, amelyben meg kell adnia, hogy melyik parcellá-tól melyik parcelláig terjedő részt kívánja megvenni, és mennyiért.
A pályázat sikeres volt, a határidő lejártáig N pályázat érkezett. Ezek közül ki kell választani azokat az ajánlatokat, amelyek a legtöbb bevételt eredményezik, s persze úgy, hogy egyetlen parcellát sem ítélnek oda egynél több pályázónak. Egy-egy pályázó vagy az összes kért parcellát megkapja, vagy egyet sem kap meg. Előfordulhat, hogy a maxi-mális bevétel eléréséhez nem kell eladni az összes parcellát.
Írj programot licit.cbp (main.cpp), amely megadja a választ a polgármes-ter problémájára!
Bemenet:
A licit.be állomány első sorában a pályázatok N száma (1<=N<=100) és a parcel-lák M száma (1<=M<=100) található, egy szóközzel elválasztva. A következő N sor az egyes pályázók adatait tartalmazza, a pályázókat ez a sorrend azonosítja. Mindegyik sorban 3 szám van egy-egy szóközzel elválasztva: A B FT, ami azt jelenti, hogy a pályá-zó az A sorszámú parcellától (1<=A<=M) a B sorszámú parcelláig (A<=B<=M) terjedő ré-szért FT forintot fizetne (1000<=FT<= 1000000).
Kimenet:
A licit.ki állomány első sorába az elérhető legnagyobb bevételt kell írni. A má-sodik sorba a nyertes pályázók sorszámai kerüljenek egy-egy szóközzel elválasztva. Ha több megoldás is van, csak egyet kell kiírni (bármelyiket).

Példa:
licit.be
4 5
1 5 10000
2 4 5000
4 5 5000
4 4 6000

licit.ki
11000
2 4

Hozzászólás megjelenítési lehetőségek

A választott hozzászólás megjelenítési mód a „Beállítás” gombbal rögzíthető.

Ha már nem az a kérés, hogy segítsenek neked megoldani, hanem hogy valaki oldja meg helyetted, visszakérdezek:
Mennyit fizetsz érte?

Nem jó a példád, mert a 2-es és 4-es pályázat is megvenné a 4-es parcellát.

Szokásos reakció ilyen kérésekre: Mutasd a kódot, meddig jutottál.
(No meg: ez nem házifeladat megoldó portál)

Ez egy milyen jó kis feladat. Ráadásul C-ben lehet megoldani. Anno nekem ilyet Piszkálban meg Bézikben kellett írni. Takarítottam is keményen a billentyűzetet az okádéktól lol.

Ja igen, és virítsd a kódot hadd nézzük meddig jutottál.

--
GPLv3-as hozzászólás.

Tessék:

begin
  writeln("Parcellázó program version 1.0 - all rights reserved");
end.

:-)

--
A főnököm mindig megtartja amit ígér, ha pénzt ígér azt is!

Szerintem ennél a feladatnál pont mindegy, hogy az pascal vagy c :)
--
HUPbeszolas FF extension

Nem csak ennél.

Pölö: "Kérek egy pohár vizet."

Mindegy milyen nyelven mondod, úgyse adok.

--
GPLv3-as hozzászólás.

Fantasztikus!
--
HUPbeszolas FF extension

A kulcsszó: interval scheduling. Jó kódolást!

--
Debian - The "What?!" starts not!
http://nyizsa.uni.cc

A kérdés: bármilyen megoldás jó, vagy emberi idő alatt le is futó megoldást várnak?

Mert a "buta" megoldást aki nem tudja összeütni, az inkább ne foglalkozzon informatikával...

szerintem csak motiválatlan egy kicsit. amikor az ember sokáig csak warningok meg errorok formájában kap visszajelzést, akkor hajlamos időnként elkedvetlenedni.

viszont ha most elkezdek szentbeszédet tartani arról, hogy mekkora szívás 25 évesen egyetemre jelentkezni akarni, akkor mindenki ásítva fogja elcsukni a böngészőablakot.

Mert te úgy gondolod, hogy az egyetemen tanítanak programozni, igaz?

hát... nagyon remélem :D

szerk.: általánosban meg szakközépben még tanítottak. ebből vontam le az ezek szerint elhamarkodott következtetést -.-

Akkor "megnyugtatlak", az általános meg a szakközepes szint megmarad az egyetemen is :)

Hát azért ezzel vitatkoznék. Az egyetemen nem azt fogják megtanítani (illetve azért van róla szó), hogy paszkálban vagy cében (vagy bármilyen nyelven) hogyan kell egy problémára programot írni. Hanem az elméleti alapokat tanulhatod meg ha képes vagy rá. A mély elméleti (erős matematika) alapok nélkül nem sokat ér az a tudás ha "csináltál már programot". Én úgy gondolom, hogy jellemzően általános iskolában és középsuliban egyszerűbb elméleti alapokkal és kicsit töb gyakorlati megvalósítással tanítják a programozást. De ez nem igazi programozás. Ellenben a felsőoktatásban elsajátíthatsz egy csomó olyan mélyebb matematikai tudást (analízis, logika, formális nyelvek automaták, algoritmusok, programozási paradigmák, stb) minek segítségével megoldhatsz bonyolult feladatokat. Tehát nem egy vagy több programnyelv ismerete tesz (jó) programozóvá hanem az, hogy az elmélet birtokában bármilyen programnyelven képes vagy megoldó programot írni. Én úgy gondolom, hogy ezt a tudást nagyjából a felsőoktatás tudja megadni a középiskola pedig nem.

--
maszili

Az egyetemi elméleti/némely gyakorlati anyagból megtanulni programozni annyit ér, mint szótárból nyelvet tanulni...

Csak így, indoklás nélkül, mert megtehetem... :-)

Ha már hasonlatoknál tartunk: elméleti tudás nélkül programozni tanulni meg olyan, mint fórumokból nyelvet tanulni.

Teljesen nyilvánvaló (legalábbis számomra), hogy az elméleti és a gyakorlati tudás kiegészíti egymást, az egyetem csak az elméleti tudás megadására alkalmas, abban is csak részben. Ahhoz a hallgatónak is tennie kell valamit, hogy a megfelelő szintű elméleti tudást megszerezze (önképzés, választható tárgyak, stb.), a gyakorlatiról már nem is beszélve.

--
Don't be an Ubuntard!

Szerintem rossz a hasonlatod.
Mint a topiknyitó példáján is látszik előbb egy elméleti megoldást kellene készítenie amit aztán a programnyelv segítségével visz át a gyakorlatba. Ha lövése sincs az elméleti alapokról akkor pl. hiába tudja nagyon ügyesen (mert azt már sokszor csinálta), hogyan kell c++ nyelven egy fájlt megnyitni...

--
maszili

Nos részben egyetértek veled, az egyetem elméleti oktatásban jó, és kell is az az elméleti oktatás, vagy legalábbis a nagy része. Azonban az, hogy volt kb. 6 java tantárgyam a Bsc. során, és 6-ból 5 (!) alkalommal elkezdtük az alapjaitól tanulni a Javát (szó szerint értsd, tehát "na és akkor gyerekek mi az hogy osztály? " stb.) az szerintem egy elég siralmas dolog.
Ennél már csak az a szánalmasabb, hogy volt akinek erre szüksége volt, mert gőze nem volt 5. alkalommal se a kivételkezelésről például.

Ja és itt az ELTE-ről beszélek, ami igaz, hogy köztudott hogy elméleti oktatásban a jobb, na de azért mégis...

És ezt sikerült kötelező tárgyakból, vagy azért neked is kellett ügyesen válogatnod hozzá?

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee." -- Ted Ts'o

Ez a sok java tárgy mind kötelező volt, választhatóba ezek után egyet se vettem fel.
Inkább a tanárok kiválsztásánál nem volt sokszor szerencsém, mert hozzátenném, hogy azért van 1-2 tanár aki normálisan tartja az órákat.
Csak vagy nehéz bekerülni hozzájuk, vagy nem ismerem egyiket se és akkor találomra kell választani.

Tanítani tanítanak, aztán hogy megtanul-e, az csak rajta múlik.

No, egy gyors gugli ki is dobta, amit kb. sejtettem: ezt a feladatot először a 2001-es Nemes Tihaméron adták fel, ráadásul nem is a felső kategóriában, hanem a 9-10. osztályosoknak, és nem is a döntőn, hanem csak a második fordulóban. :D

eddig gondolom mindenki eljutott. ha megoldást is találtál, akkor legalább linkeld be ahelyett, hogy csak itt vigyorogsz :]

Nekem nem kell megoldást találni, mert én meg tudom oldani magam is, ismerem a megoldás "kulcsát" :P

Viszont azt gondolom, hogy abból nem tanul a delikvens.

igen, a kulcsszó megvan, már csak le kell ülnie a kérdezőnek és elkezdeni csinálni. sokszor az a legnehezebb.

na megyek kicsit bölcs lenni máshol.

jó éjt, a kérdezőnek meg ezúton üzenem, hogy ÜLJ LE ÉS TANULJ! :D

A nemdeterminisztikus megoldas raadasul meg trivialis is :)

Determinisztikus az, nagyon is, csak nem fut le polinomiális időben.

ezert kar volt visszaterned a hupra, Zaneck2

nem csak ezt írtam, de te nyilván térdelőrajtban vártad, hogy valamibe beleköthess.

sőt ha tovább elemzem a dolgot, téged már a hozzászólásod megírásának elkezdése pillanatában előre zavart az a gondolat, hogy nem fogom szó nélkül hagyni. pedig azt kellett volna tennem...

de ahhoz túl sok a szabadidőm.

Ez a tag más topikokban is térdelőrajtban kötekszik.

Látszik, hogy szoftvermérnök és nem üzletember :-)

Pedig igaza van, Erendis nem sok segítséget adott a kérdezőnek, ellenben különböző offtopic hozzászólásokat generál. Az még hagyján, amikor althreadbe reagál, de ezen thread nyitó commentjének semmi értelme nem volt. Még csak nem is troll, ami legalább a topicot olvasókat szórakoztatná.

--
Don't be an Ubuntard!

Akkor rendben van.

...szerinted.

"nem tudom megoldani "

Egy jó hírem van, de kettő lesz belőle.

Ha sokáig gondolkozol rajta, utánajársz és próbálkozol, mégis meg fogod tudni oldani.
Illetve ha mégsem tudod, akkor sincs baj, mert még nem késtél el azzal, hogy pályát változtass.

szerintem igenis van, amikor már késő pályát változtatni.

csak én pl. még mindig várom azt a munkahelyet, ahol nem mondjuk egy spamküldő script megírása a csúcsok csúcsa.

van tobb ezer ilyen. keress, ne varj. jah, de ehhez az is kell, hogy neked se a spamkuldo script legyen a csucs.

"szerintem igenis van, amikor már késő pályát változtatni."

Még akkor se, amikor a főnök kér meg rá.

Oldd meg tetszőleges pszeudokódban és megírom neked C++-ban.

ha megírta pszeudokódban, onnantól már c++-ban is meg fogja tudni írni

Nem feltétlenül, mert ahhoz már a C++ specifikus ismeretekre is szükség lehet (fájlból biztonságosan beolvasni változókba stb.).

ez ilyen biro által kiértékelt SZTE Algoritmusok és adatszerkezetek kötelező feladat szagú... pfejj... :) azért napközben elgondolkodunk rajta kollégámmal, ha másért nem, a nosztalgia kedvéért :D

--
A gyors gondolat többet ér, mint a gyors mozdulat.

Szinte biztos, hogy biro-s kötelező program. Annak idején az egyik évfolyamtárs kapta és poénból megcsináltam én is.

Addig eljutottal, hogy irj egy main.cpp-t? Ha igen, mi van benne?
--
Ki oda vagyik, hol szall a galamb, elszalasztja a kincset itt alant. | Gentoo Portal

Javaslat: szakadj el a nyelvtől, előbb az algoritmust állítsd össze! Utána kezdd el "lefordítani" C vagy C++ vagy akármilyen konkrét nyelvre.

(Mindenesetre ha és amennyiben a példa tényleg így szerepel a feladat kiírásában, akkor az oktatás ill. a tanerő hozza a formáját.)

Pontatlan feladatspecifikáció.
Mennyit kér a polgármester?

Le vagy maradva, a polgármesterek manapság már nem kérnek hanem adnak.

A leírás alapján ez nekem KÖMAL feladatnak tűnik. Nézz szét első körben a pontverseny archívumában, hátha fent van a megoldás.

Valószínűleg ha ez házi feladat, akkor a feladó ismeri az esetleg a neten fellelhető kész megoldásokat, és ellenőrizni fogja, hogy a beadott megoldás mennyire hasonlít a már létező megoldásokra.

--
Don't be an Ubuntard!

Hogy valami konstruktívat is olvass:
Először ismerkedj meg a backtrack algoritmussal.

Amire szükséged lesz:
Egy aktuális lista, ami tárolja az elfogadott ajánlatokat, egy megszorítással: a listába csak olyan ajánlatokat adunk hozzá, amik nagyobb sorszámúak, mint a legutolsó ajánlat (ha van)
Egy eddigi legjobb lista (az előző lista elmentve, mint legjobb ajánlat)
Egy eddigi legjobb összérték (az előző listához tartozó összeg)

Én valahogy úgy kezdenék neki, elkezdeném az (*)aktuális listához hozzáadni a hozzáadható (megszorítás) ajánlatokat.
Ezt addig csinálom, amíg tudom bővíteni a listát.
Ha már nem, akkor ha az aktuális lista összértéke nagyobb, mint a fejlegyzett legjobb összérték, elmentem az aktuális listát, mint legjobb lista, és az aktuális összértéket, mint legjobb összérték.

Ezután eltávolítom az aktuális listából a legutolsó elemet, és visszatérek (*)-hoz

Ha nem tévedek, akkor az algoritmus úgy áll le, hogy üres az aktuális lista, az elmentett listában lesz az optimális ajánlat, az ára pedig a legjobb összértékben.

Megjegyzések:
-Lehet, hogy tévedek :-)
-Ha bárhol ezt a postot továbbközlöd, hogy megvan az algoritmus és hogyan implementáld, megharaplak!

De honnan tudod, hogy mikor kell a backtracknek leallnia?
Szerintem inkabb egy szelessegi kereso algoritmus jobb lenne.
Amikor leporog, csak meg kell keresni azt az agat ami a legjobb erteket adja.

Látom nem mutatsz nagy érdeklődést a válaszok iránt, de azért felteszek egy kérdést, ami eddig nem volt.

Ha ez egy házi feladat, valamilyen programozást oktató tárgyból, vagy valamilyen algoritmuselméletet oktató tárgyból adták ki?

Előbbi esetében a megvalósítás szempontjából a használt algoritmus gyakorlatilag lényegtelen, egy exponenciális lefutású megoldás is teljesen megfelel, a lényeg a beolvasás és a megfelelő osztályhierarchia kialakításán van, persze a specifikációnak megfelelő kimenet előállításán kívül.

Utóbbi esetben pedig sokkal inkább számít az algoritmus, engem a hátizsák problémára emlékeztet, persze annak egy kötöttebb verziója (amit ki lehet használni az algoritmus megalkotásakor). Ez esetben nem érdemes sokat foglalkozni azzal, hogy maga a program mennyire elegáns, elég, ha a specifikált bemenetre a specifikációnak megfelelő kimenetet tudod garantálni, gyakorlatilag bármilyen módon, amit a C++ megenged.

Mindezt csak azért írom, mert a feladat sürgős, ha nem lenne az, akkor mindkét szempontnak megfelelő program az ideális megoldás.

--
Don't be an Ubuntard!

A helyzet akkor válik igazán kínossá, ha az algoritmus elkészítése, és utána a C++ program megírása is problémát okoz.

-----
A kockás zakók és a mellészabások tekintetében kérdezze meg úri szabóját.

[off]
Az ilyen feladatoknál mindig hiányolom az i/o mennyiséget.
Mellékelhetnének a kitűzők 1-2Megányit ami "minden" lehetséges
konfigurációt tartalmaz. Ezek itt pl. nem szégyellik kitenni a nagy tesztállományaikat:
http://plg1.cs.uwaterloo.ca/~acm00/
Ez azért se rossz dolog mert így hamarabb kiderül ha a kitűző se gondolt mindenre... Van ilyen is.
Szegény "mukso" még ha meg is oldaná valamilyen módon, nem lehetne (empirikusan) biztos a helyességben,
hacsak nem bizonyítaná be (de akkor meg nem tette volna fel itt a kérdést).
[/off]
A megoldás keresésnél a következő utat választanám:
O(2^n) -> O(n^2) -> O(nlog(n)) :)

hova jársz?

Az általánosság megszorítása nélkül feltehetjük, hogy wc-re biztosan!

Tök jópofa feladat, megcsináltam (bár nem C++-ban, hanem Javaban, de igazából édesmindegy). O(n*log(n))-es megoldást tudok rá adni.

Abból indulj ki, hogy:
- ha felteszed egy tetszőleges elemről, hogy benne van a végeredményben, akkor már csak két "kisebb" problémát kell megoldanod, az elemtől jobbra és az elemtől balra lévő további elemekre külön-külön
- esélyes, hogy ha tárolod a kisebb problémák megoldásait, akkor azok eredményét többször is fel tudod használni.

Sok sikert! :-)

http://codepad.org/OVFvaFwc

Az én megoldásom nagyon parasztos ?

[off]A "listálya" szó az egyik kommentben azért elég fájdalmas volt :D[/off]

Építő jellegű kritika...
:-D

valami építő-jellegűt is szeretnél? szerintem a "megoldásod" nem a feladatot oldja meg, azaz hibás az algoritmus.

kicsit off, de

Donald E. Knuth A számítógép programozás művészete I.-IV.

OpenBSD 5.0/i386 theo for the prezident:D