Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: lmio_2018_3e2_plaukimo_varzybos_jau.in

Rezultatų failas: lmio_2018_3e2_plaukimo_varzybos_jau.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 8 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\\leq500000

2\\leqA\\leqB\\leq8

1\\leqt_i\\leq1000000