Közép-európai Informatikai Olimpia 1997

 ,



Egész intervallumok - 1. Nap, 1. feladat (  pont, időlimit:   mp)
Egész számok egy [a,b] intervalluma, ahol  a<b, az a és b közötti  egész számok halmazát jelenti, beleértve a-t és b-t is.

Feladat:

Írj olyan programot, amely
Bemenet:
Az INT.IN első sora az intervallumok n számát tartalmazza (1<=n<=10000). A következő n sor mindegyikében az intervallumok a, b végpontjai vannak (0<=a<b<=10000). Az a és b egész számokat pontosan egy szóköz választja el.
Kimenet:
A program egyetlen egész számot ír az INT.OUT állomány első sorába. Ez a szám a legszűkebb, egész számokat tartalmazó halmaz elemszáma, amelynek az intervallumok mindegyikével legalább két közös eleme van.
Példa:
 
INT.IN INT.OUT
4
3 6
2 4
0 2
4 7
4


Barlang - 1. Nap, 2. feladat (  pont, időlimit:   mp)
Byteland országban sok barlang van. Egynek a térképe látható az ábrán.

Tudjuk, hogy Byteland barlangjaira biztosan igazak a következő állítások:

Meg akarjuk nyitni a barlangokat a látogatók számára. Ki akarunk jelölni egy olyan utat, amely minden termen pontosan egyszer halad át. Ez alól természetesen kivétel a bejárati terem, amit pontosan kétszer érintünk, az út elején és a végén. Azt akarjuk, hogy az út a lehető legkevesebb nehezen járható járaton vezessen keresztül.

Példa:

Tekintsük az ábrán látható barlangot. A bejárat az 1. terem. Szaggatott vonallal jelöljük a nehezen járható járatokat.
Az 1, 5, 4, 6, 8, 7, 2, 3 út nem tartalmaz nehezen járható járatot. Az úton utolsóként érintett (a bejárattal azonos) termet nem szabad még egyszer kiírni.
Feladat:
Írj olyan programot, amely
Bemenet:
A CAV.IN állomány első sora az n és a k egész számokat tartalmazza egy szóközzel elválasztva. Az  n (3<n<=500) a barlang termeinek száma, a k (k>=3) pedig a külső termek száma. A termeket 1-től n-ig számozzuk. A külső termek az 1-től k-ig sorszámozottak, de nem feltétlenül körbejárási sorrendben (lásd az ábrát). Az 1-es számú a bejárati terem.

A következő 3n/2 sor a járatok leírását tartalmazza. Minden sorban három szám van: a, b, c, egy-egy szóközzel elválasztva. Az a és a b annak a két teremnek a sorszáma, amelyet a járat összeköt. A  c értéke 0, ha a járat könnyen járható, és 1, ha nehezen.

Kimenet:
A program a CAV.OUT állomány első sorába n számot ír. Az első szám 1 (a bejárati terem sorszáma),  a következő  n-1 szám pedig azon termek sorszáma a bejárás sorrendjében, amelyeken keresztül az út halad.
Példa:
 
CAV.IN CAV.OUT
8 5
1 3 0
3 2 0
7 3 1
7 2 0
8 7 0
1 8 0
6 8 0
6 4 0
6 5 1
5 4 0
2 4 0
5 1 0
1 5 4 6 8 7 2 3


Hexadecimális számok - 1. Nap, 3. feladat (  pont, időlimit:   mp)
A hexadecimális számrendszer alapszáma a 16. Ennek a számrendszernek a számjegyei a követ-kezők: 0,1,...,9,A,B,C,D,E,F. A nagy A,..,F betűk a  10,..,15 értékeket jelölik. Például a CF2 hexa-decimális szám a 12*162 + 15*16 + 2 = 3314 tizes számrendszerbeli számot jelöli.
Jelölje  X az olyan pozitív egész számok halmazát, amelyek felírhatók olyan, legfeljebb 8 jegyű hexadecimális számként, amelyben nem szerepel ugyanaz a szám-jegy többször. A legnagyobb helyiértékű számjegy biztosan nem nulla. Az X halmaz legnagyobb eleme hexadecimális számrendszerben  FEDCBA98. A második legnagyobb FEDCBA97, a harmadik FEDCBA96, és így tovább.

Feladat:

Írj programot, amely
Bemenet:
A HEX.IN állomány első sorában az n egész szám van decimálisan.
Kimenet:
A program az X halmaz n-edik legnagyobb elemét írja a HEX.OUT állomány első sorába, mint szöveget hexadecimálisan.
Példa:
 
HEX.IN HEX.OUT
11 FEDCBA87