- 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ų.
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 |