A U2 1996 novemberében koncertet ad Nicosiában. Egyetlen pénztárnál n (<=200) U2-rajongó állt sorba jegyre várva. Mindegyikük egyetlen jegyet akart venni, de a pénztáros legfeljebb 2 jegyet adhat el személyenként.Feltételezzük, hogy a pénztáros ti időt tölt el az i-edik rajongó (1<=i<=n) kiszolgálásával. Egyszer csak két egymást követő rajongó (például a j. és a (j+1), ahol 1<=j<=n-1) megegyezik, hogy egyikük a sorban marad, másik kiáll sorból. Az ottmaradónak a pénztáros rj idő alatt szolgálja ki a két jegyet, amely kevesebb idő, mint tj+tj+1. Ezért, spórolva a pénztáros idejével, s sorbanállók mindegyike megpróbál tárgyalni az előtte és a mögötte állóval, hogy a kiszolgálás idejét lerövidítsék.
Adott a kiszolgálandő személyek száma (n), az egyenkénti, valamint a páros kiszolgálási idők (ti, illetve rj). Próbálj párokat készíteni az optimális megoldás érdekében. Megjegyzendő, hogy nem szükséges minden személyt párba állítani.
Bemenet:
A bemeneti állomány (INPUT:TXT) 3 sort tartalmaz:Kimenet:
- az első sor az n értékét tartalmazza
- a második sor a ti várakozási időket foglalja magába, szóközökkel elválasztva
- a harmadik sorban a párba sorolt vásárlók kiszolgálásához szükséges idők találhatók.
A kimeneti állomány (OUTPUT.TXT) első sora tartalmazza a minimális kiszolgálási időt. Minden ezt követő sor egy vagy két számot tartalmaz, utóbbi esetben + jellel elválasztva. Pontosabban minden sor tartalmaz egy i értéket, ha a rajongót egyedül szolgálják ki és az i+(i+1), ha a két rajongót párban szolgálják ki.Példa:
INPUT.TXT OUTPUT.TXT 7
5 4 3 2 1 4 4
7 3 4 2 2 414
1
2+3
4+5
6+7
Néhány műholdat akarunk Föld körüli pályára állítani. Két műhold kommunikálhat egymással közvetlenül vagy közvetett úton (egy vagy több másik műhold segítségével), de előfordulhat, hogy nem tudnak adatokat cserélni. Két műholdat szomszédosnak nevezünk, ha közvetlenül kommunikálnak egymással.Adott a műholdak n száma és egy n elemű számhalmaz, amely megadja, hogy az egyes műholdaknak hány szomszédja van. Ennek alapján meg kell állapítanod, hogy
Bemenet:
- létezik-e a műholdaknak olyan elhelyezkedése, amelyben megadott számú szomszédjuk van
- ha az előző kérdésre YES a válasz, írj le egy konkrét elhelyezést
- küldhető-e adat bármely műholdról bármely műholdra.
A bemenetet tartalmaző INPUT.TXT állomány szóközökkel elválasztott egészeket tartalmaz. Az első szám az n (<=20) értéke, megadja a pályán lévő műholdak számát adja meg. A következő n egész adja meg, hogy az egyes műholdaknak hány szomszéddal kell rendelkeznie. Megjegyzendő, hogy az n szám sorrendje nem számít.Kimenet:A kimentet az OUTPUT.TXT állományba kell írni. Az első sorban az (a) kérdésre adott választ (YES / NO) kell írni. Ha a válasz NO, akkor további sorokat nem kell írni. Ha a válasz YES, akkor a következő n sor 1 és 0 számjegyeket tartalmaz szóközzel elválasztva, nxn-es mátrix formájaában. Ha az (i, j) helyen álló érték 1, akkor az i. és a j. műhold szomszédos, ha az érték 0, akkor nem szomszédosak. A kimenet (n+2). sorába a (c) kérdésre adott választ (YES / NO) kell írni.Példa:
INPUT.TXT OUTPUT.TXT 6 4 3 1 4 2 0 NO 7 4 3 1 5 4 2 1 YES
0 1 1 1 1 1 0
1 0 1 0 0 0 0
1 1 0 1 0 1 0
1 0 1 0 0 1 0
1 0 0 0 0 0 0
1 0 1 1 0 0 1
0 0 0 0 0 1 0
YES6 2 3 1 1 2 1 YES
0 1 0 1 0 0
1 0 1 1 0 0
0 1 0 0 0 0
1 1 0 0 0 0
0 0 0 0 0 1
0 0 0 0 1 0
NO
Feladat:
Bemenet:Kimenet:Példa:
HEX.IN HEX.OUT