Nemzetközi Informatikai Diákolimpia 1993

Mendoza, Argentína


1. napi 1. feladat (20 pont)
Egy nyakláncban n (n<=100) gyöngy van. A gyöngyszemek piros, kék vagy fehér színűek, és véletlenszerűen vannak felfűzve a nyakláncba. A következő két ábra (a és b) n=29 esetre mutat egy-egy példát. Az ábrán "o" jelöli a piros gyöngyöt, "x" a kéket, "#" a fehéret. (Az 1 és 2 szám az első illetve a második gyöngyöt jelöli.)
 
1 2
o x x o
o x
o o
o o
x o
x x
x x
x x
o o
x o
x o
o o
o x o
a) ábra
1 2
x o o x
x x
x o
# o
# #
o o
x x
o x
x o
o o
o o
o x
o o #
b) ábra

Az a) ábrán látható elrendezés az alábbi karaktersorozattal írható le: "brbrrrbbbrrrrrbrrbbrbbbbrrrrb", ahol "b" (blue) jelöli a kék és "r" (red) a pirosat.

Tegyük fel, hogy elvágjuk a láncot, egy egyenes mentén lerakjuk az asztalra, majd az egyik végétől elindulva felszedjük az egymás mellett fekvő, egyforma színű gyöngyöket (vagyis addig szedjük fel a gyöngyszemeket, amíg eltérő színűhöz nem érünk), majd ugyanezt tesszük a másik végéről elindulva (ezek persze más szinűek is lehetnek, mint az előzőek).

Határozd meg azt a pontot, ahol a láncot el kell vágni ahhoz, hogy a lehető legtöbb gyöngyszemet szedjük össze.

Például az a) ábrán bemutatott nyakláncból 8 gyöngy vehető fel, ha a láncot a 9. és a 10. vagy a 24. és a 25. gyöngy között vágjuk el.

Egyes nyakláncokban fehér gyöngyszemek is vannak, amint az a b) ábrán látható. Amikor a gyöngyöket gyűjtjük, a fehér gyöngyöket pirosnak is, kéknek is vehetjük szükség szerint (mintha átfestenénk őket a megfelelő színre). Az ilyen elrendezést leíró karaktersorozatokban "r", "b" és "w" betűk lehetnek.

Írj programot az alábbi részfeladatok elvégzésére!

Bemenet:

A NECKLACE.DAT állomány soronként egy-egy elrendezést ír le.
Kimenet:
A NECKLACE.SOL állományba a gyöngyöt meghatározó sor alá a felszedhető gyöngyök maximális számát (M-et) és a hozzá tartozó vágási pontot pontot kell írni. Ha valamely M-hez több vágási pont is van, elég közülük egyet kiírni! A különböző elrendezésekhez tartozó megoldásokat egy-egy üres sorral kell elválasztani.
Példa:
 
NECKLACE.DAT NECKLACE.SOL
brbrrrbbbrrrrrbrrbbrbbbbrrrrb
bbwbrrrwbrbrrrrrb		 brbrrrbbbrrrrrbrrbbrbbbbrrrrb
8 between 9 and 10

bbwbrrrwbrbrrrrrb
10 between 16 and 17

1. napi 2. feladat (30 pont)
Egyes vállalatok más vállalatoknak résztulajdonosai lehetnek, ha megszerezték összes részvényeik egy részét. Például a Ford 12%-ban tulajdonosa a Mazdának. Az "A" vállalat akkor irányítja "B"-t, ha az alábbi feltételek valamelyike teljesül:
a) A=B
b) A több, mint 50%-ban tulajdonosa B-nek.
c) van k (k>=1) olyan C(1), ..., C(k) vállalat, amelyeket A irányít, és minden egyes C(i) vállalat x(i)%-ban tulajdonosa B-nek, ahol 1<=i<=k és x(1)+...+x(k)>50%.
Feladat:
Adott az (i,j,p) hármasok sorozata, ahol a hármasok azt jelentik, hogy az i vállalat p%-ban tulajdonosa a j vállalatnak. (A vállalatok száma legfeljebb 100 lehet.) Állítsd elő az összes olyan (h,s) párt, amelyben h vállalat irányítja az s vállalatot.
Bemenet:
A COMPANY.DAT állományban szerepelnek az (i,j,p) hármasok sorozatai, ahol i, j és p pozitív egész számok! Egy-egy sorozat egy-egy vállalatcsoportot ír le. Az egyes sorozatokat üres sor választja el egymástól.
Kimenet:
A COMPANY.SOL állományba az összes olyan megtalált (h,s) párt kell írni, ahol h<>s. A (h,s) párokat egymás utáni sorokbanm h szerint növekvő sorrendben kell kiírni. A különböző vállalatcsoportokhoz tartozó megoldásokat egy-egy üres sorral kell elválasztani.
Példa:
 
COMPANY.DAT COMPANY.SOL
2 3 25
1 4 36
4 5 63
2 1 48
3 4 30
4 2 52
5 3 30

1 2 30
2 3 52
3 4 51
4 5 70
5 4 20
4 3 20

 4 2
4 3
4 5

2 3
2 4
2 5
3 4
3 5
4 5

1. napi 3. feladat (50 pont)
N darab különböző színű téglalapot helyezünk egy fehér lapra úgy, hogy átfedhetik egymást. A fehér lap a cm széles és b cm hosszú (a és b 30-nál nem nagyobb, pozitív páros számok). A téglalapok két-két oldala párhuzamos a fehér lap megfelelő oldalaival. A téglalapok nem lóghatnak ki a fehér lapról. Végül különböző színű alakzatokat láthatunk. Két azonos színű téglalaprészlet ugyanahhoz az alakzathoz tartozik, ha legalább egy (matematikai értelemben vett) közös pontjuk van; egyébként különböző alakzatoknak tekintjük őket.

Feladat:

Számítsd ki az összes előálló alakzat területét! A koordinátarendszer origója a fehér lap közepe, tengelyei párhuzamosak a fehér lap széleivel.
Bemenet:
A RECTANG.DAT állományban különféle adatsorozatok vannak. Az adatsorozatokat üres sorok választják el egymástól. A téglalapokat az állományban megadott sorrendben helyezzük a fehér lapra.
Kimenet:
A RECTANG.SOL állományba az összes előálló alakzat színét és területét kell kiírni. Az alakzatokat leíró adatokat színek szerint növekvő sorrendben kell kiírni, soronként egyet! Az egyes adatsorozatokhoz tartozó eredményeket egy-egy üres sorral kell elválasztani egymástól.
Példa:
 
RECTANG.DAT RECTANG.SOL
20 12 5
-7 -5 -3 -1 4
-5 -3 5 3 2
-4 -2 -2 2 4
2 -2 3 -1 12
3 1 7 5 1

30 30 2
0 0 5 14 2
-10 -7 0 13 15

 1 172
2 47
4 12
4 8
12 1

1 630
2 70
15 200