Balkáni Informatikai Olimpia 2000

Clement a halász, N darab halat fogott, s elvitte azokat egy halüzletbe. A halboltban súlyuk alapján csomagolták. Minden csomag egy vagy több halat tartalmazott.

Feladat:

Tegyük fel, hogy te vagy az első vásárló és választhatsz a különböző súlyú csomagok közül. Hány különböző súlyú csomag állítható össze N halból?

Feltételek:

N a halak száma (N <= 500)
t_i az i-edik hal súlya (t_i <= 1000)

Bemenet:

A bemeneti állomány (MARKET.IN) első sorában a halak N száma áll. A következő N sor mindegyikében egy szám, az i-edik hal súlya olvasható.

Kimenet:

A kimeneti állomány (MARKET.OUT) egyetlen számot tartalmaz, amely megadja a halakból összeállítható különböző súlyú csomagok számát.

Példa:
 

MARKET.IN	MARKET.OUT
5 800 200 354 18 182	27

Clement arról tanult az iskolában, hogyan lehet egy geometriai alakzat fraktál-dimnezióját kiszámítani. A cél elérése érdekében rajzol egy egész koordinátájú rácsozatot. Aztán ebbe berajzolt egy N csúcsú alakzatot. Az N csúcs meghatározott egy nem feltétlenül konvex alakzatot, amelynek oldalai nem metszik egymást. Aztán megszámolta a belső rácsnégyzeteket (K1 darab ilyen van). Belső rácsnégyzet alatt azt értjük, hogy a négyzetnek van olyan pontja, amely az alakzat belső pontja. Ezután kitörölte a páros x koordinátájú és a páros y koordinátájú rácsokat, és így is meghatározta a belső rácsnégyzetek számát (K2 darab van). A fraktál dimnezióját K1 és K2 értékéből ki lehet számítani. Clement a ar Ohrid tó fraktál-dimenzióját akarta meghatározni.

Feladat:

Határozd meg K1 és K2 értékét!

Feltételek:

A csúcspontok száma N (2<N<1000)
Minden csúcspont leírható egy x_i, y_i számpárral (-32000<= x_i, y_i <=32000).
Minden csúcs az előtte lévőhöz kapcsolódik, az első csúcs pedig az utolsóval van összeközve.

Bemenet:

A bemeneti állomány (FRACTAL.IN) első sorában a csúcspontok N száma olvasható, az ezt követő N sorban pedig két-két egész szám, az x_i, y_i értéke található.

Kimenet:

A kimeneti állomány (FRACTAL.OUT) első sora két egész számot, a K1 és a K2 értékét tartalmazza.

Példa:

FRACTAL.IN	FRACTAL.OUT
4 0 0 10 0 20 10 10 10	110 30

Ohrid-ban évente búvártanfolyamot szerveznek. A tanfolyamon különböző feladatokat kell megoldani. Ezek egyike, hogy egy szikla egyik oldaláról a víz alatt át kell kelni a másik oldalára. A tanfolyami csoport N tagúl, de csak egy oxigén-palackuk van, amelyet egyszerre legfeljebb két személy használnat. Minden búvár eltérő sebességgel mozog, így a párosok sebességét a lassabb búvár sebessége adja. A tanfolyami résztvevők között van M pár, akik ki nem állhatják egymást, s nem akarnak együtt merülni.

Feladat:

Keresd meg azt a  párosítást a csoporton belül, amelyhez minimális átkelési idő tartozik!

Feltételek:

A csoporttagok száma legfeljebb N (N<=6000)
A csoporttagokat számok azonosítják. (1, 2, ..., N)
M páros nem hajlandó egymással merülni (M<=6000)
A t_i érték adja meg az i-edik búvár számára a út megtételéhez szükséges időt.
Az oxigénpalackot csak merüléssel lehet egyik helyről a másikra vinni. Az oxigénpalack kapacitása végtelen.
A tesztadatokra mindig van megoldás.

Bemenet:

A bemeneti állomány (DIVING.IN), első sorában az N és az M értékét tartalmazza. A következő N sorban a t_i idők szerepelnek. Az ezt követő M sor mindegyike két egész számot tartalmaz, megmutatva, hogy mely búvárok nem merülnek együtt.

Kimenet:

A kimenet első sora egy egész számot tartalmaz, amely megadja a feladat véfrehajtásához szükséges minimális időt. A következő sorok a minimális időhöz tartozó egyik lehetséges megoldást adják meg. Minden sor egy mozgást ír le egy vagy két számmal, amelyek az oxigénpalackot éppen használó tanfolyami hallgatókat azonosítják.

Példa:
 

DIVING.IN	DIVING.OUT
4 2 1 2 1 2 3 4 2 3	6 3 1 1  4 2 3 3 1