Az 1. ábra egy 3D testet mutat, amelyik felépíthetö a 2. ábrán látható 12 fajta blokkból. Az ábrán látható színezések csak az átláthatóságot hivatottak könnyíteni, egyéb jelentésük nincs.
Írj programot, amely egy megadott testet kirak a rendelkezésre álló blokkokból úgy, hogy a felhasznált blokkok darabszáma (nem a fajták száma!) minimális legyen! Minden egyes blokkfajtából tetszőleges számú felhasználható, bármilyen eltolás és forgatás alkalmazásával.
A testet és a blokkokat a bennük lévő elemi (1x1x1-es) kockák felsorolásával írjuk le. Az egyes elemi kockákat azon sarkuk koordinátájával (x, y, z) adjuk meg, amelyik a legközelebb van az origóhoz (amelyre x+y+z minimális). A elemi kockák számát a test, illetve blokk térfogatának nevezzük.
A test, illetve a blokkok összefüggőek (két elemi kocka akkor összefüggö, ha van közös lapjuk).
Bemenet:
A TYPES.IN állomány a blokkfajtákat írja le, és minden tesztesetre azonos (a 2. ábra blokkjainak leírását tartalmazza, a fajták sorszáma szerint rendezett sorrendben). Az egyes blokkokat leíró sorok közül az elsö a blokk sorszámát (I, 1 < = I < = 12), a második a blokk térfogatát (V, 1 < = V < = 4) tartalmazza. Az ezután következö V sor három egész számot (x, y, z) tartalmaz, az egyes elemi kockák x, y, z koordinátáit (1 < = x, y, z < = 4).Kimenet:A BLOCK.IN állomány a kirakandó testet írja le. Az elsö sor a test térfogatát (V, 1 < = V < = 50), míg a fennmaradó V sor a test elemi kockáinak koordinátáit tartalmazza (1 < = x, y, z < = 7).
A BLOCK.OUT állomány első sora egyetlen egész számot (M) tartalmazzon, a felhasznált minimális blokkszámot. A második sorba a felhasznált M db blokk fajtájának sorszámát kell írni. Több megoldás is lehetséges, de csak ezek egyikét kell megadnod.Példa:
Megjegyzés:
TYPES.IN BLOCK.IN BLOCK.OUT 1
1
1 1 1
2
2
1 1 1
1 2 1
3
3
1 1 1
1 2 1
1 3 1
4
3
1 1 1
1 2 1
1 1 2
5
4
1 1 1
1 2 1
1 3 1
1 4 1
6
4
1 1 1
1 2 1
1 1 2
1 2 2
7
4
1 1 1
1 2 1
1 1 2
1 1 3
8
4
1 1 1
1 2 1
1 3 1
1 2 2
9
4
1 2 1
1 3 1
1 1 2
1 2 2
10
4
2 1 1
1 2 1
2 2 1
2 1 2
11
4
1 1 1
1 2 1
2 2 1
1 1 2
12
4
2 2 1
2 1 2
1 2 2
2 2 218
2 1 1
4 1 1
2 3 1
4 3 1
2 1 2
3 1 2
4 1 2
1 2 2
2 2 2
3 2 2
4 2 2
2 3 2
3 3 2
4 3 2
4 2 3
4 2 4
4 2 5
5 2 55
7 10 2 10 121. Ez a BLOCK.IN állomány az elsö ábrán megadott „ló” leírását tartalmazza.2. A BLOCK.OUT állomány második sorában az alábbiak bármelyike is lehetne:
2 7 10 11 12
2 7 11 11 12
4 4 7 10 11
4 4 9 10 11
Egy egyenes út mentén falvak helyezkednek el, mindegyiket egy egész koordinátával azonosítjuk. Minden pontban csak egyetlen falu lehet. Két falu távolságát a koordinátájuk különbségének abszolút értékével adjuk meg.Egyes falvakban postahivatalt kell építeni, mégpedig úgy, hogy a falvak és a hozzájuk legközelebb eső postahivatal távolságának összege minimális legyen.
Írj programot, amely a falvak koordinátája és a postahivatalok száma alapján kiszámolja a fenti minimális össztávolságot és megadja a felépítendö postahivatalok koordinátáját!
Bemenet:
A POST.IN állomány elsö sorában két egész szám van: a falvak száma (V, 1 < = V < = 300); a postahivatalok száma (P, 1 < = P < = 30, P < = V). A második sorban V darab egész szám van növekvő sorrendben, az egyes falvak koordinátája. Minden X koordinátára igaz, hogy 1 < = X < = 10000.Kimenet:A POST.OUT állomány első sorába a fenti módon kiszámolt minimális össztávolságot, a második sorba a P darab postahivatal koordinátáját (ami azonos a postahivatalt tartalmazó falu koordinátájával) kell írni növekvő sorrendben. Ha több megoldás is van, akkor csak egyet kell kiírni.Példa:Részpontszámok:
POST.IN POST.OUT 10 5
1 2 3 6 7 9 11 22 44 509
2 7 22 44 500 pontot kapsz, ha a postahivatalok általad megadott koordinátájából kiszámított össztávolság nem azonos az általad kiszámolt minimális össztávolsággal. Az alábbi táblázatban S jelöli az általad meghatározott minimumot, Smin pedig a várt értéket, ezek arányában kapsz pontot:
q=S/Smin q=1.0 1.0<q<=1.1 1.1<q<=1.15 1.15<q<=1.2 1.2<q<=1.25 1.25<q<=1.3 1.3<q c 10 5 4 3 2 1 0
Egy klubnak az egyes városokban legfeljebb 1 tagja lakik. A tagok valamelyik
körzetben (nem városban!) akarnak találkozni egymással. A városokat el
kell kerülniük, így esetleg át kell mászniuk a falakon. Azt a körzetet
keressük, ahova a lehető legkevesebb falmászással juthatnak el.
 |
 |
| 1.ábra | 2.ábra |
N város és M körzet van, a városokat 1-töl N-ig, a körzeteket 1-töl M-ig sorszámozzuk. Az 1. ábrán a csomópontok a városokat, a vonalak a nagy falakat jelölik. Ha pl. 3 klubtag laik a 3., a 6. és a 9. városban, akkor a keresett körzetet (és az oda vezetö utakat) a 2. ábra mutatja. A falmászások száma 2: a 9. városból induló tagnak a 2. és 4. városok közötti falon, a 6.-ból indulónak pedig a 4. és 7. városok közötti falon kellett átjutnia.
Írj programot, amely a városok, a körzetek és a klubtagok lakóhelyének ismeretében megadja a falmászások minimális számát és a keresett körzet sorszámát!
A WALLS.IN állomány első sorában egy egész szám van: a körzetek száma (M, 2 < = M < = 200). A második sorbeli egész szám: a városok száma (N, 3 < = N < = 250). A harmadik sorban álló egész szám: a klubtagok száma (L, 1 < = L < = 30, L < = N). A negyedik sorban L darab, egymástól különbözö egész szám van, a klubtagok lakóhelyének sorszáma (a város sorszáma) növekvő sorrendben.Kimenet:A következő 2*M sor páronként írja le az M darab körzetet: a párok elsö sorában a körzetet határoló városok száma, a másodikban pedig ezek sorszáma van az óramutató járása szerinti sorrendben. Kivétel az utolsó körzet, amely az ország falakon kívüli része: itt a városok az óramutató járásával ellentétes sorrendben vannak felsorolva. A körzet sorszámát a felsorolás alapján kell meghatároznod.
A WALLS.OUT állomány első sorába a falmászások minimális számát, a második sorba pedig a találkozóhely (körzet) sorszámát kell írni. A feladatnak több megoldása is lehet, de csak egyet kell kiírni.Példa:
| WALLS.IN | WALLS.OUT |
| 10
10 3 3 6 9 3 1 2 3 3 1 3 7 4 2 4 7 3 3 4 6 7 3 4 8 6 3 6 8 7 3 4 5 8 4 7 8 10 9 3 5 10 8 7 7 9 10 5 4 2 1 |
2
3 |
