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

Egy számítógép rögzíti a rajta futó alkalmazások kezdési és befejezési idejét századmásodpercben. A napi statisztika (a, b) párok halmazából áll, ahol 0<a<=b<8640000. Az (a, b) pár azt jelenti, hogy a program az a pillanatban kezdődik és a b pillanatban fejeződik be. Az a és b időpillanatok hozzátartoznak a foglalt időintervallumhoz. Egy időben több program is futhat párhuzamosan. Írj egy programot, amely kiszámítja

• a, a leghosszabb zárt (a, b) intervallum (b-a+1) hosszát, melyben a számítógép szabad
• b, a leghosszabb zárt (c, d) intervallum (c-d+1) hosszát, melyben a számítógép legalább egy programot futtat. A t időpillanat csak akkor tartozik a szabad intervallumhoz, ha ebben a pillanatban egyetlen program sem fut a gépen.

Bemenet:

A DAY1A.DAT szövegállomány első sora az intervallumok számát tartalmazza (1<=N<=1000). A hátralévő N sor mindegyikében két nemnegatív egész található, a program kezdési és befejezési idejével.

Kimenet:

A DAY1A.SOL szövegállomány a következő két egész számot tartalmazza ebben a sorrendben:
a, a leghosszabb (a, b) időervallum (b-a+1) hosszát, melyben a számítógép szabad
b, a leghosszabb (c, d) időervallum (c-d+1) hosszát, melyben a számítógép legalább egy programot futtat.

Példa:
 

DAY1A.DAT	DAY1A.SOL
9 30000 35000 10000 20000 15000 16000 40000 44000 77000 220000 13000 41000 60000 67000 50000 55000 65000 70000	8419999 143001

Egy osztály diákjai elhatározták, hogy riadóláncot alkotnak. Minden diák választ magának egyetlen társat (szomszédot), akinek a hozzá beérkező üzenetet közvetlenül továbbítja. Amikor egy diák megkap egy üzenetet, továbbítja szomszédjának.
Riadóláncnak azt a hozzárendelést nevezzük, melyre a következők teljesülnek: Tegyük fel, hogy valaki elküld egy üzenetet a szomszédjának, aki a következő lépésben továbbítja azt, és így tovább. Az üzenet egy idő után minden diákhoz, köztük az üzenet küldőjéhez is megérkezik.
Természetesen nem minden hozzárendelés riadólánc. Írj programot amely kiszámítja, hogy minimálisan hány módosítás szükséges az input hozzárendelés riadólánccá változtatásához.

Bemenet:

A DAY1B.DAT első sorában a tanulók száma található (1<=N<256). A következő N sorban egy egy név páros következik. A két nevet '>' karakter választja el. A második név után sorvég jel következik. A nevek legfeljebb 20 karakter hosszúak. Az A>B sor jelentése: Az A tanuló szomszédja B, azaz A a beérkező üzenetet közvetlenül B-nek továbbítja.

Kimenet:

A DAY1B.SOL állományba egy egész szám kerüljön, a minimálisan szükséges változtatások száma.

Példa:

 

DAY1B.DAT	DAY1B.SOL
10 Anita>Peter Andrew>Julia David>Andrew Natalie>Gabriella Edith>David Peter>Anita Gabriella>Julius Adam>David Julia>Gabriella Julius>Julia	4

Két testvér, Alan és Bob ajándékokon osztozkodnak. Minden egyes ajándékot vagy Alan vagy Bob kap, egy ajándékot elosztani nem lehet. Minden ajándéknak egy pozitív egész értéke van.
Jelölje A és B az Alan és Bob által kapott ajándékok értékét. A cél az, hogy A és B különbségének abszolútértéke minimális legyen. Írj programot, amely kiszámítja A-t és B-t.

Bemenet:

A DAY1C.DAT szövegállomány első sora az ajándékok számát tartalmazza (1<=N<=100). Az állomány további részében az ajándékok értéke következik. Minden érték <=200.

Kimenet:

A DAY1C.SOL állományba az A és B egész számok kerüljenek.

Példa:
 

DAY1C.DAT	DAY1C.SOL
7 28 7 11 8 9 7 27	48 49