Egy iskolai számítógépteremben a munkaállomások hosszú sorban helyezkednek el. Elhatározták, közülük pontosan M darabból átjárót készítenek, amely közvetlenül kapcsolódik az Internet gerincvezetékre. A többi munkaállomást a hozzá legközelebb eső átjáróhoz kapcsolják. A hatékonyság érdekében az átjárókat úgy kell megválasztani, hogy a munkaállomás - legközelebbi átjáró távolságok legnagyobbika a lehető legkisebb legyen. A munkaállomásokat egy egyenes mentén képzeljük el, pozíciójukat így egyetlen koordinátával megadhatjuk. Két munkaállomás távolsága az őket jellemző koordináták különbségének abszolút értéke.
Feladat:
Készíts programot, amely megadja az munkaállomás-átjáró távolságok maximumát és az átjáróként használt munkaállomások pozícióját.
Bemenet:
A bemeneti állomány néhány teszt adatsort tartalmaz. Az állomány első sorában lévő (T) egész szám a tesztesetek számát adja meg. Minden tesztesethez két sor tartozik. Az első sorban két egész szám, az N és az M található. Az N (1<=N<=100) a munkaállomások, M (1<=M<=N) pedig az átjárók számát adja meg. Az adott tesztesethez tartozó következő sorban N darab pozitív egész szám van, növekvő sorrendben, megadva a munkaállomások pozícióját. A pozíciót megadó X koordináta a [0;30000] intervallumban van.
Kimenet:
A kimeneti állomány tesztesetenként két sort tartalmaz. Az első sor egyetlen egész szám, a D, amely a munkaállomás - legközelebbi átjáró távolságok legnagyobbika az ideális elrendezés esetén. A második sor pontosan M darab egészet, az átjárók pozícióját tartalmazza. Ha több lehetséges pozíciósor van, a kimeneti állományba csak az egyiket kell írni.
Példa:
|
gate.in |
gate.out |
|
2 |
5 |
(ACM SZTE csapatverseny 2000)