Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: lmio_2018_3e2_plaukimo_varzybos_vyr.in

Rezultatų failas: lmio_2018_3e2_plaukimo_varzybos_vyr.out

Jei norite pateikti savo sprendimą - prisijunkite.

Plaukimo varžybos

Užduotis

Lietuvos atvirosiose mokinių plaukimo varžybose gali dalyvauti visi norintys mokiniai. Kadangi išankstinė registracija nėrabūtina, organizatoriai niekada nežino, kiek gali sulaukti norinčiųjų varžytis.

Nors baseine yra 500000 plaukimo takeliai, šį kartą mokinių atvyko mažiau nei buvo tikėtasi, todėl organizatoriai nusprendė juos paskirstyti į mažesnes grupes po ne mažiau nei A ir ne daugiau nei B vienoje.

Taip pat organizatoriai siekia, kad kiekvienas plaukimas būtų kuo įdomesnis ir jame dalyvautų kuo panašesnio pajėgumo sportininkai.

Parašykite programą, kuri suskirstytų atvykusius mokinius į plaukimus taip, kad absoliutus skirtumas tarp bent kuriame plaukime dalyvaujančių lėčiausio ir greičiausio plaukikų vidutinių distancijos įveikimo laikų būtų kuo mažesnis.

Pradiniai duomenys

Pirmojoje eilutėje pateikti trys skaičiai atskirti tarpu: į varžybas atvykusių dalyvių skaičius (N) bei minimalus (A) ir maksimalus (B) viename plaukime galinčių dalyvauti plaukikų skaičius.

Tolimesnėse N eilučių didėjimo tvarka pateikti laikai ti, per kurį vidutiniškai kiekvienas plaukikas įveikia distanciją (t_i\\leqt_i+1).

Pradiniai duomenys visada bus tokie, kad sprendinys egzistuos.

Rezultatai

Jums reikia išvesti vieną skaičių – didžiausią laiko skirtumą tarp vieno plaukimo lėčiausio ir greičiausio dalyvių.

Pavyzdžiai

Pradiniai duomenys Rezultatai Paaiškinimas 
5 2 4
1
1
3
3
4
 
1
 
Pirmas plaukimas: 1 1. Abiejų plaukikų laikai vienodi (skirtumas – 0).
Antras plaukimas: 3 3 4. Skirtumas tarp greičiausio ir lėčiausio – 1.
Jei būtų skirstoma taip: 1 1 3 3 4 Tada skirtumas tarp pirmo plaukimo dalyvių būtų 2.
 
8 3 5
1
1
1
5
8
8
8
10
 
4
 
Optimalus paskirstymas:
1 1 1 1 5
8 8 8 10

Ribojimai

2\\leqN\\leq1000000

2\\leqA\\leqB\\leq500000

1\\leqt_i\\leq1000000