Naum hazatért falujába, Elshaniba külföldről, ahol sok pénzt keresett. Elshani lakói nap mint nap dolgoni jártak a két szomszédos faluba, Peshtaniba és Lagadinba. Céljukhoz sok út vezetett a hegyen át. Segítségképpen Naum Lmax hosszú hidat akart építeni, hogy lerövidítse az utat.Feladat:
Keresd meg, hol kell felépítni a hidat, hogy megfeleljen a következő kritériumoknak:Feltételek:
- Az új út Elshaniból Peshtaniba rövidebb legyen, mint a jelenlegi legrövidebb út.
- Az új út Elshaniból Lagadinba rövidebb legyen, mint a jelenlegi legrövidebb út.
- Az új utak hosszának összege minimális legyen.
A pontok száma N (3 <= N <= 2000), pozitív egész.Bemenet:
A pontokat az 1, 2, ..., N számok jelölik, ahol 1 a kezdőpont (Elshani) 2 az egyik cél (Peshtani), 3 a másik cél (Lagadin) sorszáma. Két pontot csak egy úttal kötünk össze. Az utak hossza a legrövedebb távolság két összekötött pont között. Mindegyik pontból legfeljebb 20 út indul.
Az xi, yi pontpár adja meg az i-edik pont helyét. (-32000 <= xi, yi <= 32000)
M a meglévő utak, azaz az összekötött pontpárok számát jelöli. (M<=5000)
Lmax, amely pozitív valós szám, az építhető maximális hosszú híd hosszát adja meg.
Ha van megoldás, akkor csak egy van.A bemeneti állomány (BRIDGE.IN) első sorában az N és M egész számok állnak és az Lmax valós szám. A következő N sor mindegyikében két egész, az xi, yi számok kapnak helyet, amelyek az i-edik pont helyét jelölik. Az ezt követő M sorban az összeköttetésben lévő pontpárok sorszáma található.Kimenet:Ha van megoldás, akkor annak a két pontnak a sorszámát kell bejegyezni, amelyek között híd épük.Példa:
Ha nem építhető a feltételeket kielégítő híd, akkor az első sorba a 0 0 számpárt kell írni, a következő sorba pedig két valós számot, amelyek közül az első az 1 és 2 pontok, a második az 1 és 3 pontok közötti legrövidebb út hosszát adja meg.
BRIDGE.IN BRIDGE.OUT 6 5 40
0 0
100 0
100 100
45 20
55 20
25 50
1 4
4 6
5 2
5 3
6 34 5
A pók és a bogár egy L*M*N méretű üvegdobozban volt. A pók és a bogár a doboz felületén mozog. Nem tudnak repülni, de nem is esnek le a falról.Feladat:
Keress stratégiát, amellyel a pók a legkevesebb lépésben megfogja a bogarat.Feltételek:
Programod egy unittal játszik majd. A programod a pók mozgását adja, a unit a bogár mozgásával válaszol.Az L, M, N számok centiméterben adják meg a doboz méreteit. (L, M, N <= 10000).Bemenet:
1. ábra
2. ábra 3. ábra
- A dobozt egy térbeli koordinátarendszerbe helyeztük be, a kocka élei a tengelyekkel párhuzamosak.
- A pók és a bogár csak egész koordinátájú pontokban lehet. (Lásd 1. ábra)
- A pók a 2. ábra szerint mozoghat.
- A bogár a 3. ábra szerint mozoghat.
- A pók megfogja a bogarat, ha ugyanabba a pozícióba kerül, mint ahol a bogár van.
A bemeneti állomány (SPIDER.IN) első sora három egész számot tartalmaz, az L, M, N számokat. A második sor a pók kiindulási helyének koordinátáit (xp, yp, zp) adja meg. Az utolsó sorban található három szám a bogár kiindulási pozícióját (xb, yb, zb) tartalmazza.Kimenet:A Finish eljárás meghívásával készül el a kimeneti állomány. Programodnak nem szabad írnia a kimeneti állományba. Ha sikerült a problémát megoldani, az állomány tartalmazza a lépések számát, egyébként a hiba okát.Értékelés:A teszt nem értékelhető, haMegjegyzések:T a minimális lépésszám, amellyel a feladat megoldható. S a programod által meghatározott lépésszám.
- két egymást követő póklépés (movespider)
- két egymást követő bogárlépés (movebug)
- érvénytelen póklépés
Ha
- S<T+3, akkor 10 pontot kapsz,
- T+3 <= S < 1,2*T, 8 pont a jutalmad,
- 1,2*T <= S < 1,4*T, 5 pont jár.
Pascal:Példa:
A USpider.tpu nevű Unitot használhatod. A programod elejére be kell írnod: uses USpider;C:
A unit 4 eljárást tartalmaz Init; MoveSpider, Movebug és Finish.Procedure Init;
Az init eljárást a programod elején kell meghívnod.Procedure MoveSpider(xns, yns, zns : integer);
A MoveSpider eljárás segítségével a pók lépését követő új pozíciót állíthatjuk be.Procedure MoveBug(var xnb, ynb, znb: integer);
A MoveBug eljárás a számítógép stratégiája alapján megadja a bogár új pozícióját.Procedure Finish;
A Finish eljárást kell meghívni, ha a pók megfogta a bogarat. Ez az eljárás befejezi a programot.A programod kezdetén az Init eljárást kell meghívni, majd felváltva kell MoveSpider és MoveBug eljárást alkalmazni. Ha a MoveSpider eljárás a bogár koordinátát állítja be a pók számára, meg kell hívnod a Finish eljárást.
Használhatod az USpider.obj állományt és az USpider.h állományt.Mielőtt megoldod a feladatot, nyitnod kell egy új projectet. A projectet Spider.prj-nek kell nevezned, két állományt kell tartalmaznia: USpider.obj és a programodat.
Programod elején a következő sornak kell szerepelnie:
#include "USpider.h" or #include <Uspider.h>Az obj állomány 4 függvényt tartalmaz: Init, movespider,movebug és Finish.
void Init();
Az Init függvényt programod elején kell meghívnod.void movespider(int xns, int yns, int zns);
A movespider eljárás segítségével a pók lépését követő új pozíciót állíthatjuk be.void movebug(int *xnb, int *ynb ,int *znb);
A movebug eljárás a számítógép stratégiája alapján megadja a bogár új pozícióját.void Finish();
A Finish eljárást kell meghívni, ha a pók megfogta a bogarat. Ez az eljárás befejezi a programot.A programod kezdetén az Init eljárást kell meghívni, majd felváltva kell MoveSpider és MoveBug eljárást alkalmazni. Ha a MoveSpider eljárás a bogár koordinátát állítja be a pók számára, meg kell hívnod a Finish eljárást.
SIDER.IN Programod A bogár helye 5 4
0 1 2 3
3 2 1 4
4 1 2 1
1 4 3 2
2 3 4 0Init;
movespider(9,12,2);
movebug(xb, yb, zb);
movespider(7,12,1);
movebug(xb, yb, zb);
movespider(5,12,0);
movebug(xb, yb, zb);
movespider(3,11,0);
movebug(xb, yb, zb);
movespider(1,10,0);
Finish;(4, 12, 1)
(3, 12, 0)
(2, 11, 0)
(1, 10, 0)
Naum, a halász N darab halat fogott. A parton megmérte őket. Naum egy halászati társaságnál dolgozott és szerződése szerint joga volt hazavinni T gramm halat. Szerette volna azokat a halakat hazavinni, amelyeknek az összsúlya (L) legjobban megközelíti T-t. (L<=T)Feladat:
Határozd meg, mely halakat viheti haza Naum.Feltételek:A halak száma N (N <= 500000).Bemenet:
A maximálisan hazavihető súly T (T <= 7000).
Az i-edik hal súlya ti (ti <= 35000).A bemeneti állomány (FISH.IN) első sorában az N és a T értéke található. A következő N sor mindegyikében egy szám, az i-edik hal ti súlya található.Kimenet:Ha nincs olyan megoldás, amely pont a T értékét adja, akkor a hazavihető legnagyobb L súlyra kell megoldást adni. A kimeneti állomány (FISH.OUT) első sorába a hazavitt halak K számát kell írni, a következő K sorba pedig egy-egy egész számot, a hazavitt halak súlyát.Példa:
FISH.IN FISH.OUT 10 280
300
10
30
80
200
20
20
60
10
1002
200
80
