Metro signalo klaida – Gabių vaikų ugdymas

Pradinių duomenų failas:: metro.in
Rezultatų failas:: metro.out
Laiko apribojimas:: 2 s.
Atminties apribojimas:: 64 Mb.

Metro signalo klaida

Stokholme yra kelios metro linijos. Vienoje šių linijų dažnai įvyksta daug problemų sukelianti „signalo klaida“.

Metro liniją galima įsivaizduoti kaip dvejus lygiagrečius bėgius. Šiais bėgiais traukiniai važiuoja priešingomis kryptimis. Pasiekęs bėgių pabaigą, traukinys apsisuka ir važiuoja kitais bėgiais.

Kai eismas normalus, eismas vyksta tolydžiai – visi traukiniai juda vienodu pastoviu greičiu (1 ilgio vienetas per laiko vienetą). Traukiniai būna pasiskirstę tolygiai: kiekvienoje bėgių pozicijoje traukiniai pasirodo periodiškai. Laikysime, kad laikas, reikalingas traukiniui sustoti, keleiviams išlipti ir įlipti, o taip pat apsisukti linijos galuose yra santykinai labai mažas, ir į jį nekreipsime dėmesio.

Tačiau įvykus „signalo klaidai“, traukiniai išsidėstė netvarkingai. Jūsų kaip eismo reguliuotojo pareiga yra užtikrinti, kad traukiniai kaip įmanoma greičiau vėl išsidėstytų tolygiai. Parašykite programą, kuri pagal duotas traukinių pozicijas linijoje apskaičiuotų, kaip greitai tai gali būti padaryta. Jūs galite nurodyti traukiniams laikinai sustoti ir/ar apsisukti bet kurioje linijos vietoje. Jei traukinys apsisuka, jis peršoka ant gretimų bėgių.

Linijos bėgių ilgis yra 100. Viršutiniame paveiksle penki traukiniai išsidėstę pozicijose 5 (kryptis – į dešinę), 35 (į kairę), 46 (į dešinę), 75 (į kairę) ir 85 (į dešinę). Vienas būdas tolygiai išdėstyti traukinius būtų liepti traukiniui, esančiam pozicijoje 46, pavažiuoti 1 ilgio vienetą ir pakeisti kryptį (apatinis paveikslas). Tam būtų sugaištamas vienas laiko vienetas. Tačiau tai nėra optimalus sprendinys; žr. žemiau pateiktą pavyzdį.

Pradiniai duomenys

Pradiniai duomenys skaitomi iš standartinio įvesties įrenginio. Pirmoje eilutėje įrašyti du sveikieji skaičiai, atskirti tarpu: metro linijos bėgių ilgis m (100 ≤ m ≤ 100,000,000) ir traukinių toje linijoje skaičius n (1 ≤ n ≤ 100,000). Kitose n eilučių įrašytos traukinių pozicijos: sveikasis skaičius \(x_{i}\) (0 ≤ \(x_{i}\) ≤ m) ir kryptį žymintis simbolis (L – kairė, R – dešinė), atskirti tarpu.

Rezultatai

Jūsų programa į standartinį išvesties įrenginį turi išvesti vienintelį skaičių – mažiausią laiką, per kurį traukinius galima išdėstyti tolygiai. Programos pakeiktas atsakymas negali skirtis nuo tikrojo daugiau negu \(10^{-6}\).

Pavyzdžiai

Pradiniai duomenys	Rezultatai
100 5 5 R 35 L 46 L 75 L 85 R	0.5
100 8 9 L 15 R 41 L 33 L 81 R 33 R 100 L 97 R	15.500000