| Fişierul intrare/ieşire: | easychoice.in, easychoice.out | Sursă | Summer Challenge 2009, Runda 3 |
| Autor | Din Folclor | Adăugată de |  Stefan Istrate •stef2n |
| Timp execuţie pe test | 0.35 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Easy Choice
Anul acesta, colonelul James a primit sarcina de a recruta soldaţi pentru armata ţării sale. La recrutare se prezintă N candidaţi, fiecare fiind caracterizat prin înălţimea sa (număr natural). Colonelul James vrea sa formeze R divizii, fiecare cu câte C soldaţi, iar restul de candidaţi să fie refuzaţi. În cadrul unei divizii, definim "dezechilibrul" ca fiind maximul dintre diferenţele înălţimilor a 2 soldaţi. "Dezechilibrul" întregii armate reprezintă maximul dintre dezechilibrele celor R divizii. Din motive de performanţă, colonelul doreşte să recruteze soldaţii astfel încât armata să aibă dezechilibrul minim. Ajutaţi-l să işi îndeplinească sarcina!
Date de intrare
Fişierul de intrare easychoice.in conţine pe prima linie numerele N, R şi C separate prin câte un spaţiu, având semnificaţiile de mai sus. Pe linia a doua se vor găsi N numere reprezentând înălţimile candidaţilor.
Date de ieşire
În fişierul de ieşire easychoice.out se va scrie un singur număr natural reprezentând dezechilibrul minim obţinut la recrutarea soldaţilor.
Restricţii
- 1 ≤ N ≤ 1.000.000
- 1 ≤ R x C ≤ N
- Înălţimea H a unui candidat respectă restricţia 1 ≤ H ≤ 1.000.000.000. Trebuie făcut ceva împotriva meselor bogate în calorii.
- Pentru 50% din teste, N ≤ 1.000.
Exemplu
| easychoice.in | easychoice.out |
|---|---|
| 8 2 3 183 218 238 203 273 143 238 173 | 30 |
Explicaţie
Se pot alege următorii soldaţi:
- Divizia 1: 238 218 238 (dezechilibru 20)
- Divizia 2: 173 203 183 (dezechilibru 30)
Dezechilibrul armatei este max(20, 30) = 30.
