Dingilville városában szokatlan módon működnek a közlekedési lámpák. Bármely két csomópontot legfeljebb egy (kétirányú) utca köt össze egymással. Nincs olyan utca, amely egy csomópontot önmagával kötne össze. Minden csomópontban egyetlen közlekedési lámpa van, amelyik vagy kéket (B, blue), vagy pirosat (P, purple) mutat. A lámpák színe periodikusan vált; a kék és a piros jelzés ideje különböző lehet. Egy jármű csak akkor indulhat el az egyik csomópontból a másikba, ha az elindulás pillanatában mindkét csomópontban azonos színű a lámpa. Ha egy jármű a váltás pillanatában érkezik egy csomópontba, akkor a továbbhaladáshoz már a lámpa új színét kell figyelembe venni. A jármű a csomópontoknál várakozhat. A várostérkép a következőket tartalmazza:Határozd meg a (közlekedés megindulásától számított) legrövidebb ideig tartó utat (csomópontok sorozataként) adott kezdő és célcsomópont esetén.
- az áthaladáshoz szükséges időt az egyes utcákban (egész számként, mindkét irányban ugyanaz),
- a kék és piros jelzés időtartamát az egyes csomópontokban (egész számként),
- a lámpák színét a kezdőállapotban és az első színváltásig eltelő időt (egész számként) az egyes csomópontokban.
Ha több megoldás van, közülük csak egyet kell megadni.Feltételek:
Bemenet:
- 2 <= N <= 300, ahol N a csomópontok száma. A csomópontokat 1-től N-ig sorszámozzuk.
- 1 <= M <=14.000, ahol M az utcák száma.
- 1 <= lij <= 100, ahol lij az i-edik csomópont és a j-edik csomópont közötti utcán való áthaladás időtartama.
- 1 <= tic <= 100, ahol tic a c szín időtartama az i-edik csomópontban. A c index vagy B a kék (blue), vagy P a piros (purple) esetén.
- 1 <= ric <= tic, ahol ric a kezdőszín váltásáig eltelő idő az i-edik csomópontban.
A lights.inp szöveges állomány tartalma:Kimenet:
- Első sora a kezdő és a célcsomópont sorszáma.
- A második sor a csomópontok N és az utcák M száma.
- A következő N sorban vannak a csomopontok adatai. Az állomány (i+2)-edik sora az i-edik csomóponthoz tartozó Ci, ric, tiB, tiP adatokat tartalmazza, ahol Ci vagy a 'B', vagy a 'P' karakter: a lámpa színe a kezdőállapotban.
- A következő M sor az utcákat írja le. Az egyes sorok tartalma: i, j, lij egy-egy szóközzel elválasztva, ahol i és j az utcát határoló két csomópont sorszáma.
A lights.out szöveges állomány tartalma:Példa:ha van út a kezdő és a célcsomópont között:
ha nincs út a kezdő és a célcsomópont között:
- az első sorban legyen a minimális idő, amely alatt el lehet jutni a kezdő csomópontból a célcsomópontba.
- a második sorban a legrövidebb ideig tartó út csomópontjainak sorszámát sorold fel az utcákon való áthaladás sorrendjében. Azaz a sorozat első száma a kezdő-csomópont sorszáma, az utolsó szám a célcsomópont sorszáma legyen.
- az állomány egyetlen sorában 0 legyen
LIGHTS.IN LIGHTS.OUT 1 4
4 5
B 2 16 99
P 6 32 13
P 2 87 4
P 38 96 49
1 2 4
1 3 40
2 3 75
2 4 76
3 4 77127
1 2 4
Egy játékban N oszlopban egymásra rakunk korongokat (ld. az 1. ábrát). Egy mozgatást az oszlop p sorszámával és egy k számmal adunk meg. Ez azt jelenti, hogy a p-edik oszlopról k db korongot teszünk át a szomszédos (p-1)-edik és (p+1)-edik oszlopra, ha 1 < p < N-1. Az 1. oszlopról csak a 2.-ra teszünk át k db korongot, az N-edikről pedig csak az (N-1)-edikre, ugyancsak k db korongot (ld. az 2. ábrát). A művelet csak akkor végezhető el, ha az adott oszlopon elegendő számú korong van, azaz legalább 2k, ha az oszlopnak két szomszédja van, egyébként k.
5 oszlop 0, 7, 8, 1 és 4 koronggal Ugyanazok a p=2, m=2 mozgatás után A játék célja az, hogy minden oszlopra azonos számú korong kerüljön minél kevesebb mozgatással.
Feltételek:
Bemenet:
- Biztos, hogy a feladat megoldható, mégpedig legfeljebb 10.000 mozgatással..
- 2 <= N <= 200
- 0 <= Ci <= 2000, ahol Ci az i-edik oszlopon lévő korongok száma a játék kezdetén
A flat.inp szöveges állomány két sort tartalmaz:Kimenet:
- az első sorban a korongok N száma van,
- a második sorban N db egész szám van, ahol a sorban az i-edik szám az i-edik oszlopon lévő korongok száma a játék kezdetén.
A flat.out állomány első sorába a mozgatások M számát kell írni. A további M db sor mindegyikébe egy-egy mozgatást leíró két egész szám (p, k) kerüljön, mégpedig a mozgatások végrehajtásának sorrendjében.Példa:
Értékelés:
FLAT.INP FLAT.OUT 5
0 7 8 1 45
5 2
3 4
2 4
3 1
4 2A megoldásra akkor jár tesztesetenként a teljes pontszám (A), ha a mozgatások száma (x) nem haladja meg az elviselhető minimumot (B). (Megjegyzés: nem biztos, hogy B az optimum. B értéke tesztesetenként változik, és az értéke két dologtól függ: egyrészt egy egyszerű stratégiát alkalmazó kiegyenlítéshez szükséges mozgatások redundancia-mentes számától, másrészt a korongok kezdeti eloszlásától.) A pontszámot kerekítéssel határozzuk meg az alábbi képlet szerint:A, ha x <= B
2A*(1,5*B–x)/B, ha B < x < 1,5*B
0, ha x >= 1,5*B
Dingilville városa repülőteret épít. Az építésre kijelölt terület térképe téglalap alakú négyzetrács, amely a mezők tengerszint feletti magasságát is feltünteti. A mezőket vízszintes (kelet-nyugati irányú) x és függőleges (észak-déli irányú) y koordinátájuk azonosítja.Határozd meg azt a legnagyobb, azaz a legtöbb mezőt tartalmazó téglalap-alakú területet, amelyre az alábbi két feltétel teljesül:
a) a legmagasabban és a legalacsonyabban fekvő mező tengerszint feletti magasságának különbsége nem haladja meg a C korlátot,Feltételek:
b) a téglalap oldalának hossza kelet-nyugati irányban legfeljebb 100 egység.Bemenet:
- 1 <= U <= 700, 1 <= V <= 700, ahol U a térkép vízszintes (kelet-nyugati irányú) és V a függőleges (észak-déli irányú) oldalának a hossza,
- 0 <= C <= 10
- -30.000 <= Hxy <= 30.000 , ahol Hxy az (x, y) koordinátájú mező tengerszint feletti magassága, 1 <= x <= U, 1 <= y <= V.
- A térkép délnyugati sarkának koordinátája (1,1), északkeleti sarkáé pedig (U,V).
A land.inp állományKimenet:
- első sora az U, V és C egész számokat tartalmazza,
- a következő V db sor mindegyikében U db egész szám van (Hxy), ahol Hxy az x-edik szám az állomány (V-y+2)-edik sorában.
A land.out szöveges állomány egyetlen sorába négy egész számot kell írni, ahol az első két szám a téglalap-alakú terület délnyugati, a második kettő pedig az északkeleti sarkán fekvő mező (x,y) koordinátája.Példa:
LAND.INP LAND.OUT 10 15 4
41 40 41 38 39 39 40 42 40 40
39 40 43 40 36 37 35 39 42 42
44 41 39 40 38 40 41 38 35 37
38 38 33 39 36 37 32 36 38 40
39 40 39 39 39 40 40 41 43 41
39 40 41 38 39 38 39 39 39 42
36 39 39 39 39 40 39 41 40 41
31 37 36 41 41 40 39 41 40 40
40 40 40 42 41 40 39 39 39 39
42 40 44 40 38 40 39 39 37 41
41 41 40 39 39 40 41 40 39 40
47 45 49 43 43 41 41 40 39 42
42 41 41 39 40 39 42 40 42 42
41 44 49 43 46 41 42 41 42 42
45 40 42 42 46 42 44 40 42 414 5 8 11
41 40 41 38 39 39 40 42 40 40 39 40 43 40 36 37 35 39 42 42 44 41 39 40 38 40 41 38 35 37 38 38 33 39 36 37 32 36 38 40 39 40 39 39 39 40 40 41 43 41 39 40 41 38 39 38 39 39 39 42 36 39 39 39 39 40 39 41 40 41 31 37 36 41 41 40 39 41 40 40 40 40 40 42 41 40 39 39 39 39 42 40 44 40 38 40 39 39 37 41 41 41 40 39 39 40 41 40 39 40 47 45 49 43 43 41 41 40 39 42 42 41 41 39 40 39 42 40 42 42 41 44 49 43 46 41 42 41 42 42 45 40 42 42 46 42 44 40 42 41