Informatika OKTV, II. kategória, 2010, I. forduló 5. feladat.

Programozás - kezdő

Sziasztok!

Az idei informatika OKTV első fordulójának 5. feladatára van valakinek normális megoldása? A feladat szövege így hangzik:

A folyó mentén kitermelt fát N helyen gyűjtik össze és szállítják a folyón lefelé úsztatva az első gyűjtőhelyre, ahol fűrészmalomban végzik a feldolgozást. A vállalat elhatározta, hogy további fűrészmalmot állít üzembe néhány gyűjtőhelyen. Minden gyűjtőhelyről a fát a folyón lefelé haladva az első fűrészmalomba fogják szállítani. A szállítási költéség a megtett távolság és a tömeg szorzata. Ismerjük az egyes gyűjtőhelyek elhelyezkedését (az elsőtől vett távolságot km-ben) és azt, hogy mennyi fa keletkezik évente az egyes gyűjtőhelyen. Kiszámítandó, hogy hova kell telepíteni az új fűrészmalmotkat, hogy a szállatási összköltség a lehető legkisebb legyen!

A táblázat első oszlopa a gyűjtőhely sorszámát, a második oszlop az 1. gyűjtőhelytől vett távolságot, a harmadik oszlop a gyűjtőhelyen keletkező fa tömegét tartalmazza.
1 0 1
2 2 2
3 3 3
4 6 44
5 7 5
6 20 6
7 22 33
8 34 18
9 35 9
10 44 10
11 57 11
12 66 2
13 88 13
14 100 44

(a feladat eredeti szövegében táblázatba volt szedve, sorokban, de egyszerűbb volt itt oszlopokba beírni számomra - axaard)
Hová kell telepíteni
- További 1 fűrészmalmot?
- További 2 fűrészmalmot?
- További 3 fűrészmalmot?
- További 4 fűrészmalmot?

Itt a feladat szövegének vége. A feladat megoldásához semmilyen segédeszközt (se számológép, se számítógép) nem használhattunk. Valakinek van valami épkézláb megoldása? Amit én gondoltam, az ilyen 10.000 nagyságrendű szorzásokat kívánt volna, és ennél még senki nem mondott okosabbat...

Köszi előre is!
axaard

Ui.: a hivatalos megoldókulcs csak a helyes eredményeket (13, 7 13, 6 8 13, 6 8 13 14) tartalmazza, ezeket pontozza (5 5 6 6 pont), a megoldás menetéről szó sincs...

  • 8997 megtekintés

( chx | 2010. 11. 18., cs – 19:45 )

Ez egy matematikai probléma, ebben a formában mit keres az Informatika OKTV-n?
______________________
echo crash > /dev/kmem

Az informatika nem egyenlő a programozással. Legalább próbáltak volna valami körítést pakolni hozzá.
Az ilyen "informatikai" feladatokról mindig az egyik "legkeményebb" tanárom jut az eszembe, aki mindig valamilyen elcseszett, nehéz matematikai problémának a megoldását kódoltatta le velünk, de a megoldást papír+számológép kombóval ellenőrizte, mert egy for ciklusnál többet képtelen volt produkálni, és még az is kifogott rajta ha zip helyett arj-t kapott.

______________________
echo crash > /dev/kmem

FIXME, ha már megváltozott a helyzet, de, ha minden igaz, informatika tárgyból két OKTV is létezik. az egyik a fentebb tárgyalt Nemes Tihamér (11-12 évfolyam alatt is megrendezik, csak ott nem OKTV), ami programozás, illetve van egy "Alkalmazói" OKTV is, ami ~ECDL ismereteket vár el.

igen, ez egy matematikai probléma. De a jó algoritmusok megírása nem matematikai probléma?

Ha azt a megoldást vennénk, amit én csináltam, azaz minden egyes variációra kiszámolom, hogy mennyit spórólhatunk, ha oda telepítjük a fűrészmalmot, akkor:
- az egy fűrészmalom telepítésénél még megoldható, 13 szorzást kell elvégezni.
- két fűrészmalom telepítésénél már gázosabb, mert (bár ha ügyes az ember, egyes eseteket kizárhat), de 13*12 szorzást kell elvégezni, jópár összeadás mellett
- így látható, hogy a négy fűrészmalom telepítésénél 13*12*11*10 lehetőséget kell végigszámolni, ami kicsit sok. Még ha jó sok esetet is ki tudsz zárni, akkor is ezres nagyságrendű szorzásokat kellene elvégezned - számológép nélkül!

Ez ugye a számítógépnek is időbe telik. A feladat kiírójának (gondolom) az volt a célja, hogy felmérje, tudunk-e hatékony algoritmusokat írni.

Az már más kérdés, hogy ezeket a gyorsabb algoritmusokat ők sem hozták tudtunkra, lehetségesnek tartom, hogy ők számítógéppel kiszámoltatták a 10000+ szorzást.

( bambano | 2010. 11. 18., cs – 20:26 )

szerintem az egyértelműen látszik, hogy a malmot egy gyűjtőhely mellé kell építeni és ekkor csak 13 pontot kell végigpróbálgatni, az meg favágó módszerrel is megy... (höhö:))

Szerk: ha a hivatalos megoldás tényleg tartalmazza a 14-es számot, akkor a megoldás rossz.

egy kicsit de.
én kiagyaltam, hogy gyűjtőhelyre érdemes telepíteni a malmot, közben benne volt a feladatkiírásban. ezt tehát benéztem.

Viszont az is benne van, hogy már egy malom van. Ha annak az egy malomnak nem tudjuk a pontos helyét, akkor három eset lehet:
1. az eredetileg létező egy malom a 14. gyűjtőhelyen van, mert miért tenné máshova. Ekkor a kulcsban megadott megoldás, ami tartalmazza a 14-es számot, szügségképpen rossz, mert minek rakna egy helyre két malmot, amikor a malommal szemben nem volt kapacitáskorlát.
2. a másik véglet, hogy az a malom világvége tábla után olyan helyen van, ahova a kurtafarkú malac is csak duracell csere után megy ki túrni. Ekkor a legelső újonnan telepítendő malmot a 14. gyűjtőhelyre kell tenni, akkor lesz költséghatékony. De a megoldás szerint a 13. helyre teszi.
3. Az eredetileg létező malom valahol nem elmeroggyant távolságban van, de én nem látom a kiírásban, hogy hol, így nem tudjuk kiszámolni, hogy annak a fának mi a költsége, amit nem egy újonnan lerakott malomban fűrészelsz, hanem leúszik az eredetibe. Így a feladat megoldhatatlan.

A feladatnak szerintem akkor van értelmezhető megoldása ennyi kiinduló paraméter esetén, ha a 14. gyűjtőben van az eredeti malom.

( ody42 v | 2010. 11. 18., cs – 21:20 )

Kiszamolnam az osszes pontra a kovetkezo pontig usztatas költségét, ami a két pont közötti távolság és a fa tömeg szorzata.
Pl. a 14 es 13-as pont kozott:
(100-88) * 44

Igy lenne minden gyujtohelyhez egy "súly". Mivel csak egy irányba lehet úsztatni, ezért az első malomnál még eléggé triviális, a 14-estől és az 1-től kezdve elkezdeném összeadni a súlyokat, mindig azt az oldalt folytatnám, ahol kisebb a súlyok összege.
4 fűrészmalomnál már nem triviális annyira, de valszeg ott sem olyan trükkös megtalálni a lokális maximumokat.

Ezt most csak fejben pörgettem végig, lehet, h. teljesen hibás a gondolatmenet, szóval lehet jönni fikázni :)

( Nyizsa v | 2010. 11. 18., cs – 22:12 )

Én úgy csináltam hirtelen, hogy kiszámoltam minden gyűjtőhelyről az 1. pontba úsztatás költségét (a két érték szorzata). Az összköltség ugye ezek összege. Az szépen látszik, hogy a végére kell betenni. Újraszámoltam úgy, hogy a 14-es pontba raktam be egy malmot (ide a távolság 0 lett), majd a 13-asba (itt táv 0, 14-esben pedig 100-88), és kijött hogy így olcsóbb.
A további helyszínek hasonlóan kiszámíthatók, kb. megfelezzük (harmadoljuk, negyedeljük) a teljes költséget, és ahol az 1. ponttól számítva eléri ezt a költség, oda beteszünk egy malmot. Aztán ki lehet próbálni, hogy eltolva eggyel ide vagy oda olcsóbb lesz-e.
Gyors Calc-tilitoli után ez az ötletem.

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

( Gordi90 | 2010. 11. 18., cs – 22:36 )

TROLL ON
A megoldókulcsról annyit, hogy nem volt olyan évem a gimiben (5 év, tallyal bezárólag) amikor az Oktatási Minisztérium tisztességes feladatlap+megoldókulcs kombót adott volna ki a kezéből.
OKTV matekon a megoldókulcs lazán számolt mindent egy olyan 3szög alapú hasábbal ahol az alapot képező 3szög nem létezhetett az oldalak miatt.
Vagy pl. olyan igaz-hamis matek érettségis kérdés amiben az igaz is meg a hamis is helyes...
TROLL OFF
------------------------
Everyone is a winner*

( Xanco | 2010. 11. 19., p – 02:43 )

Sziasztok!

Kis agytorna gyanánt összedobtam a megoldást perlben:

http://www.infomage.hu/~xanco/prog/oktv2010/5_perl.txt

A magasabb számú gyűjtőhely, mint kiindulási pozíció és az alacsonyabb számú gyűjtöhely, mint célállomás között keresi rekurzívan az optimális malom elhelyezést, visszavezetve így egyetlen malom elhelyezésére a problémát és ennek a költségeinek számítására.

A költségek számításához segédletnek mátrixot használok. Először legenerálom az összes esetet, hogy két gyűjtőhely között mennyi a szállítás költsége, majd ezeket az értékeket aggregálom, hogy az összes köztes gyűjtőhely költségét is beleszámolom a két gyűjtőhely közötti költségbe. Ezek a mátrixok gyorsan előre legenerálhatók és utána már ezek alapján kalkulálhatók a malomelhelyezések költségei.

A feladat megoldásának azt fogadták el, ha leírtam 1, 2, 3, 4 számot: hogy hova építsék a gyűjtőhelyeket... Olyan algoritmus nekem is ment volna, ami több ezer szorzást tartalmaz - csak ezt nem tudtam volna végrehajtani, "lefuttatni". Ők pedig az eredményre kíváncsiak.

Szóval de, ez olyan fejben-papíron megoldós feladat.

( ris | 2010. 11. 19., p – 17:50 )

Azt azért hozzátehetnéd, hogy számológépet nem használhattunk...

( uid_720 | 2010. 11. 19., p – 20:10 )

A négyjegyű függvénytáblázatban nincs erre egy táblázat? Abban minden van :-D

Fuszenecker Róbert

( Muri | 2010. 11. 19., p – 22:39 )

Sziasztok!

Sajnos volt szerencsém nekem is a kezembe venni az említett feladatsort. Az előző években már megszoktam, hogy van benne hiba, de ebben kifejezetten sok volt.
Nagyon zavaró tud lenni a függvényeknél, hogy nem tudom melyik változót kell megadni a függvénynek, hogy melyikben adja vissza az eredményt, továbbá hogy új változókat bevezet egy függvény közepén. És a kedves versenyző találja ki, hogy mire gondolt a feladat írója.

Szerintem szégyen, hogy ennyi hibával (helyesírási és elvi egyaránt) egy országos verseny feladatsora kikerülhet.

Ha valakit érdekel, szívesen beszkennelem és felrakom a feladatokat. A hivatalos oldalon természetesen sem a feladatsor, sem a megoldókulcs nincs még fent.

Ne is mondd, a 4-es feladatban az Első fv. második variációja engem is eléggé megkavart. Gyakorlatilag a 4-es feladat nagy részét, meg az 5-s feladat kb. 3/4-részét buktam el.

Egyébként szerintem röhelyes, hogy a megoldókulcs csak a 4 eredményt pontozza az utolsó feladatnál. Vagy pontozza csak azt, de akkor ne 5-6 ponttal!

( kukacster | 2010. 11. 19., p – 23:21 )

14 szorzás után ezt látom:
1 0 1 0
2 2 2 4
3 3 3 9
4 6 44 264
5 7 5 35
6 20 6 120
7 22 33 726
8 34 18 612
9 35 9 315
10 44 10 440
11 57 11 627
12 66 2 132
13 88 13 1144
14 100 44 4400
1. malom: a legnagyobb költségcsökkentés szemmel láthatólag a 14. sor 4400-es értékének leapasztásával érhető el, de ha hozzávesszük a 13. sor 1144-ét, még jobb.
2. malom: a táblázatunk alja így néz ki most:
13 0
14 528
észrevehető, hogy a legmagasabb összeg a 726, ha azt eltüntetjük, akkor csökkennek a későbbiek is, tehát ez kecsegtet sikerrel.
3. malom: ez már nehezebb: ismét a 726-ra gondolnék, de sajnos akkor rosszabb eredményt érek el, mint ha a 8-12 sorokat összegzem, majd a 7-6-ot
ezzel gyakorlatilag már csak egy nagy szám marad, a 14. sorban az 528, de ezt már csak a 4. malomnál oldom meg:
4. malom: itt megint a legnagyobb egyedül álló értéket veszem.
Hogy mi az algoritmus?
Talán ha egyet kell letenni, a kiugró értéket megkeresni, megnézni, hogy annak szomszédjában nincs-e magas érték, ha igen és annak csökkentésével jobb eredményt kapok, oda teszem a malmot, amúgy az előbbihez.
(ok, táblázatkezelőt használtam és sokat segített a megoldási kulcs is:))

Számomra kicsit átláthatatlan a koncepciód, már az egy malomnál is. A helyes táblázat így néz ki:
n s t sum(t) sum(t)*s
14 100 44 44 4400
13 88 13 57 5016
12 66 2 59 3894
11 57 11 70 3990
10 44 10 80 3520
9 35 9 89 3115
8 34 18 107 3638
7 22 33 140 3080
6 20 6 146 2920
5 7 5 151 1057
4 6 44 195 1170
3 3 3 198 594
2 2 2 200 400
1 0 1 201 0
Ahol az első három oszlop a feladatban megadott oszlopok, a harmadik oszlop, hogy mennyi fát szállítunk tovább az adott gyűjtőhelyről, a negyedik pedig, hogy mennyit spórolunk, ha az adott gyűjtőhelyre építjük a fűrészmalmot. Ezt még papíron is ki lehetett volna számolni.
A "viccesebb" része az a feladatnak, mikor nem egy, hanem két fűrészmalmot kell kiszámolni, és ezek különféle kombinációira (13*12, 13*12*11, 13*12*11*10) vagyunk kíváncsiak...

( jimmi | 2010. 11. 20., szo – 23:46 )

Megcsináltam Pythonban, szerintem némileg egyszerűbb, mint a korábban elhangzott Perles megoldás. Sajnos a futási idő nálam is négyzetes, így papíron kb. esélytelen. Kiváncsi lennék, mire gondoltak a rendezők.

http://pastebin.com/FMjLMvSu

( Aadaam v | 2010. 11. 21., v – 12:19 )

Segitek, jo?

Az informatika OKTV-t a BME / ELTE CS tanszeken allitjak ossze, tehat Computing Science.

Ok nem informatikusok (Software Engineer, mernok-informatikus), hanem szamitastudomanyosok (Computing Scientist, kb. progmat).

A feladatok jo resze a tanszek konyveibol van (tipikusan az Algoritmuselmelet, vagy a Grafelmelet, typotex mindketto), ezek alapjan gyerekjatek megoldani.

A jatek arra megy ra, hogy a delikvens magatol rajon-e az AlgElm-re kb.

( axaard | 2010. 11. 21., v – 23:09 )

Közben a gyakorikerdesek.hu oldalon egy ilyen választ kaptam:

"Először készíthetsz egy 14x14-es mátrixot, melynek minden mezőjébe beírod, hogy az adott helyről a másik helyig mennyi költséggel jár elszállítani az összes fát. Elég a mátrix egyik felét kitölteni. Ez (kb) 14*14/2 kivonás + szorzás + összeadás, tehát 100-as nagyságrendű. Utána pedig ezek közül a számok közül rendre a megfelelő 2-t, 3-at, 4-et, 5-öt kell összeadni.
+1 malomnál 13 lehetséges eset van, ahol 2 számot kell összeadni, és minimálisat kiválasztani => 13 összeadás
+2 malomnál 13 alatt a 2 db (3 tagú) összeadás => 78 összeadás
+3 malomnál 13 alatt a 3 = 286 db
+4 malomnál 715 db összeadás

Ez nem kevés, de ha közben gondolkozol is, egy csomó lehetséges esetet ki is lehet szűrni(amikor a költség már meghaladja az eddigi minimumot. Tehát a 10000-es becslés (pláne hogy szorzásról beszéltél, pedig csak összeadás kell) elég túlzás. Számológépet sem lehetett használni?"

Ez így (ránézésre) egy picit egyszerűbb, és talán megoldható...

( axaard | 2010. 11. 24., sze – 16:59 )

Elméletileg megvan a megoldás. Vagyis nem megoldás a szó szoros értelmében, de talán megmagyarázza, hogyan is merték feladni ezt a feladatot.

Infó-tanárom levelezett a feladatkitűzőkkel. Elméletileg ők kitaláltak erre egy algoritmust. Aztán azt lekódolták, és megnézték, mi lesz az eredmény. Majd feladták nekünk, számológép, számítógép nélkül. Köszi...

Egyébként közületek ki indult idén OKTV-n informatikából, II. kategóriában? Hány pontotok lett? Melyik feladatra mennyi?

Abból, hogy
- létezik egy triviális, nagy műveletigényű megoldás
- neked nem sikerült jobb megoldást találnod
- a feladatkitűzők ellenőrizték a sajátjukat gépen
nem következik, hogy az ő megoldásuk is akkora műveletigényű, hogy nem számolható végig papíron.

Ha nem voltam elég egyértelmű: az infótanárom állítása szerint ezt a feladatkitűzők mondták. Ezt ő, a velük folytatott levelezésére alapozva mondja.

Ha pedig te tudsz kisebb műveletigényű megoldást, várom építő jellegű hozzászólásodat. Vagy ha csak ötleted van, hogy hol tudnak erre a feladatra egy, papíron elvégezhető megoldást adni.