Fișierul intrare/ieșire | orase1.in, orase1.out | Sursă | Lot Vaslui 2014 - Baraj 3 |
---|---|---|---|
Autor | Ionel-Vasile Piț-Rada | Mihail-Cosmin Piț-Rada | Adăugată de | Tinca Matei • TincaMatei |
Timp de execuție pe test | 0.5 sec | Limită de memorie | 16384 KB |
Scorul tău | N/A | Dificultate | N/A |
Vezi soluțiile trimise | Statistici
Orase1 (Lot Juniori)
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.