ACM

ELTE csapatverseny
2000



Pénzérme (Coin) /tesztadatok/
Az Aranyrúd bank megbízható forrásból értesült róla, hogy a legutóbbi szállítmány M darab pénzérméiből pontosan egy hamis, tömege eltér a többitől. (A többi mind egyező tömegű.) A gazdasági válság után nekik egyetlen kétkarű mérlegük maradt. Ezt a mérleget használva egy méréssel meghatározhatjuk, hogy a bal serpenyőben súlysorozat a nehezebb vagy könnyebb, mint a jobb serpenyőben lévő.

A keresés érdekében a bank alkalmazottai megsorszámozták az érméket 1-től M-ig, így minden pénzérméhez egyértelműen egy egész számot rendeltek. Ezt követően mérni kezdik a pénzérmék azonos számú csoportjait. A használt érméket és a mérési eredményt gondosan feljegyezték.

Feladat:

Írj programot, amely a mérési eredmények ismeretében segít a bank alkalmazottainak meghatározni a hamis érme sorszámát.
Bemenet:
A bemeneti állomány N tesztesetet tartalmaz. A N értéke, amely pozitív egész, az állomány első sorába van bejegyezve. Ezt követik a tesztesetek. Minden tesztesethez tartozó első sor az M és a K egészeket foglalja magában egy szóközzel elválasztva, ahol M (2<=M<=10000) a pénzérmék száma, K (1<=K<=10000) pedig a mérések száma. A következő 2K sor a méréseket írja le. Két sor tartozik minden méréshez. Az első sor első száma Pi (1<=Pi<=M/2), amely megadja, hogy hány érmét helyezünk a mérleg egy-egy serpenyőjébe. A sor következő Pi száma megadja a bal, az azt követő Pi száma pedig a jobb serpenyőben lévő érmék sorszáma. A számokok szóközök választják el egymástól. A teszteset második sorában egy karakter szerepel a <, >, = jelek közül.
Kimenet:
Minden tesztesethez ki kell írni a hamis érme sorszámát, vagy a 0 értéket, ha a mérések alapján ez nem állapítható meg.
Példa:
 
coin.in coin.ans
2
5 3
2 1 2 3 4
<
1 1 4
=
1 2 5
=
6 4
3 1 2 3 4 5 6
<
1 1 2
=
2 1 3 4 5
<
2 4 5 2 6
>
3
0


Oszthatóság (Divisibility) /tesztadatok/
Tekintsünk egy egészekbők álló számsort. A számok közé a + és - jelet tehetjük. A műveleti jelek választásától függően számtalan végeredményt állíthatunk elő.

A 17, 5, -21, 15 számokat tekintve az alábbi eredményre juthatunk.

17 + 5 + -21 + 15 = 16
17 + 5 + -21 - 15 = -14
17 + 5 - -21 + 15 = 58
17 + 5 - -21 - 15 = 28
17 - 5 + -21 + 15 = 6
17 - 5 + -21 - 15 = -24
17 - 5 - -21 + 15 = 48
17 - 5 - -21 - 15 = 18
Egy ilyen számsort D-vel oszthatónak nevezünk, ha van olyan műveletsor, amelynek eredménye D-vel osztható. A fenti számsor ennek megfelelően osztható 7-tel, de nem osztható 5-tel.

Feladat:

Írj programot, amely megállapítja, hogy egy számsor osztható-e egy adott számmal.
Bemenet:
A bemeneti állomány N tesztesetet tartalmaz. Az állomány első sorában az N értéke kap helyet. A tesztesetek első sorában két egész szám található egyetlen szóközzel elválasztva, a K és a D. (1<=K<=10000, 2<=D<=100). A teszteset második sorában K darab egész szám szerepel, köztük szóközök vannak. Minden egész 10000-nél nem nagyobb abszolútértékű.
Kimenet:
A kimeneti állományba tesztesetenként egyetlen szót kell írni: "Divisible", ha a végeredmények közül bármelyik osztható D-vel, illetve "Not divisible", ha a végeredmények közül egyetlen szám sem osztható D-vel.
Példa:
 
div.in div.ans
2
4 7
17 5 -21 15
4 5
17 5 -21 15
Osztható
Nem osztható


Horgászat (Fishing) /tesztadatok/
John horgászni indul télvíz idején. Erre összesen H órányi ideje van (1<=H<=16), ezalatt L darab léket látogathat meg (2<=L<=25) a megadott sorrendben. Az 1. sorszámú léktől indul, s léktől lékig vándorol. Nem kell minden léknél megállnia, de nem szükséges minden lékhez eljutnia. Minden i=1, …, L-1 számhoz kapcsolunk egy ti értéket, amely az i-edik és az (i+1)-ik lék közötti út bejárásához szükséges időt fejezi ki 5 perces időegységekben. (0<ti<=192). Ha t3=4, akkor a 3. és 4. lék közötti út 20 percbe telik.

Az út megtervezéséhez egyéb információink is vannak. Minden egyes léknél az első 5 percben várhatóan fi darab hal akad horogra. (fi>=0). Ezt követően minden 5 percben a fogható halak mennyisége di-vel csökken. (di>=0) Ha a fogható halak mennyisége eléri a di-t, vagy az alá csökken, akkor a következő 5 perces időszak végére egyetlen halunk sem marad.

Feladat:

Írj programot, amely segít megtervezni a horgásztúrát olyan módon, hogy John a lehető legtöbb halad fogja.
Bemenet:
A bemeneti állomány N darab tesztesetet tartalmaz. Minden eset a lékek számát tartalmazó sorral kezdődik. A következő sorban a rendelkezésre álló idő, azaz a H értéke szerepel. A következő sor az fi, az azt követő a di értékeket foglalja magában, majd a harmadikban (L-1) szám, a ti értékek szerepelnek.
Kimenet:
A kimeneti állományban fel kell Minden tesztesetnél fel kell tüntetni az egyes lékeknél időt vesszővel elválasztva. A következő sorba a kifogott halak számát kell bejegyezni.
Példa:
 
fish.in fish.ans
3
2
1
10 1
2 5
2
4
4
10 15 20 17
0 3 4 3
1 2 3
4
4
10 15 50 30
0 3 4 3
1 2 3
45, 5
Number of fish expected: 31

240, 0, 0, 0
Number of fish expected: 480

115, 10, 50, 35
Number of fish expected: 724



Metszéspont (Intersection) /tesztadatok/
Azt mondjuk, hogy egy szakasz metsz egy téglalapot, ha van legalább egy közös pontjuk. A téglalaphoz tartozik a négy határoló szakasz és a közöttük lévő terület. Bár a bemenet csak egész számokat tartalmaz, a metszéspontnak nem kell egész koordinátájúnak lennie.
Például az alábbi szakasz nem metszi a téglalapot.
A szakasz kezdőpontja: (4,9), végpontja: (11,2)
A téglalap bal felső sarka: (1,5), jobb alsó sarka: (7,1)

Feladat:

Írj programot, amely megállapítja, hogy az adott szakasz metszi-e az adott téglalapot!
Bemenet:
A bemenet első sora N értéket, a tesztesetek számát tartalmazza. Minden további sor egy-egy tesztesetet foglal magában. A számok a következő sorrendben követik egymást: xstart, ystart, xend, yend, xleft, ytop, xright, ybottom, ahol xstart, ystart a szakasz kezdő, xend, yend a szakasz végpontjai, az xleft, ytop a téglalap bal felső, xright, ybottom pedig a jobb alsó sarka. A számokat szóköz választja el egymástól. A bal felső és a jobb alsó kifejezés nem utal a koordináták sorrendjére.
Kimenet:
A kimeneti állományban tesztesetenként egyetlen sornak kell szerepelnie, benne a T-nek, ha ven metszéspont, illetve az F-nek, ha nincs metszéspont.
Példa:
 
intersect.in intersect.ans
1
4 9 11 2 1 5 7 1
F


Fa (Tree) /tesztadatok/
A jól ismert adatstruktúra, amely lehet üres vagy halmaza egy vagy több pontnak, amelyek élekkel kapcsolódnak egymáshoz, kielégítve az alábbi feltételeket. Például tekintsük az alábbi illusztrációt, amelyen a csúcsokat körök, az éleket pedig nyilak helyettesítik. Az első kettő fa, a harmadik nem az.

Feladat:

Írj programot, amely a csúcsok és a köztük lévő irányított élek ismeretében megadja, hogy a struktúra definíció szerint fa vagy sem.
Bemenet:
A bemeneti állomány N tesztesetet tartalmaz. Az első sorban az N értéke szerepel. Minden teszteset első sorában egy K pozitív egész áll. A következő sorban K darab számpár talalálható, amelyek mindegyike egy-egy irányított élet reprezentál. A számpár első tagja azt a csúcsot adja meg, amelyből az él indul, a másik szám pedig azt, amelybe mutat. A csúcsok száma minden esetben nullánál nagyobb.
Kimenet:
Minden tesztesetre a "Case k is a tree" vagy a "Case k is not a tree" üzenetek közül a megfelelőt kell írni a kimeneti állományba, ahol k a teszteset sorszámát jelenti.
Példa:
 
tree.in tree.ans
3
5
6 8 5 3 5 2 6 4 5 6 

8
8 1 7 3 6 2 8 9 7 5 7 4 7 8 7 6

6
3 8 6 8 6 4 5 3 5 6 5 2

Case 1 is a tree.
Case 2 is a tree.
Case 3 is not a tree.