Fişierul intrare/ieşire:easychoice.in, easychoice.outSursăSummer Challenge 2009, Runda 3
AutorDin FolclorAdăugată destef2nStefan Istrate stef2n
Timp execuţie pe test0.7 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.ineasychoice.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content