| Fişierul intrare/ieşire: | orase1.in, orase1.out | Sursă | Lot Vaslui 2014 - Baraj 3 Juniori |
| Autor | Ionel-Vasile Pit-Rada, Mihail-Cosmin Pit-Rada | Adăugată de |  Alexandru Valeanu •AlexandruValeanu |
| Timp execuţie pe test | 0.125 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Orase1
Pe axa reală există N oraşe, numerotate cu numerele 1, 2, 3, …, N. Deşi într-o lume unidimensională lucrurile par a fi mult mai simple, totuşi majoritatea locuitorilor sunt nemulţumiţi de distanţele mari parcurse între oraşe în scopul rezolvării diferitelor probleme. Astfel, pentru o mai bună organizare, s-a supus la vot şi s-a decis promovarea a cel mult K oraşe la rangul de centru adminstrativ. Centrele trebuie amplasate într-un mod isteţ, în aşa fel încât distanţa maximă calculată dintre distanţele de la fiecare oraş la cel mai apropiat centru administrativ să fie cât mai mică. Întrucât costurile de administrare ale unui astfel de centru sunt ridicate, se doreşte să se amplaseze un număr cât mai mic de centre administrative astfel încât distanţa maximă să nu fie modificată.
Date de intrare
În fişierul orase1.in, pe prima linie se află separate prin spaţii numerele N şi K. Pe linia următoare se află N - 1 numere naturale nenule, separate prin spaţii, al i-lea număr reprezentând distanţa dintre oraşele i şi i + 1.
Date de ieşire
Fişierul orase1.out va trebui să conţină pe o singură linie, separate prin spaţiu, două numere naturale, reprezentând distanţa maximă corespunzătoare unei amplasări optime a centrelor, respectiv numărul oraşelor ce trebuie promovate.
Restricţii
- 2 ≤ N ≤ 106
- 1 ≤ K ≤ min(N, 1000)
- suma celor N-1 distanţe nu depăşeşte 2 000 000 000
- 30% dintre teste vor avea N ≤ 1 000
Exemplu
| orase1.in | orase1.out |
|---|---|
| 7 3 3 1 4 14 4 3 | 4 2 |
Explicaţie
O posibilitate de amplasare optimă a centrelor poate fi în oraşele 3 şi 6.
