ACM

A gyorsétteremlánc tulajdonos McBurger néhány étterme a főútvonal mentén van. Nemrég elhatározták, hogy a főútvonal mentén építenek néhány raktárat. Mindegyiket egy étterem mellett helyezik el, s onnan néhány másik éttermet is ellátnak a szükséges hozzávalókkal. Természetesen a raktárakat úgy kell elhelyezni, hogy a raktáraknak a hozzájuk kapcsolódó éttermektől mért átlagos távolsága minimális legyen! Írj programot, amely meghatározza az optimális helyét a raktáraknak. A precízebb munka érdekében McBurger menedzsmentje a következő előírást adta: megkapod a főútvonal menti n darab étterem központtól mért távolságát, ezek a d₁<d₂<...<d_n egész számok. (A központ is a főútvonal mentén van.) Továbbá megadják a k számot, amely az építendő raktárak száma. A k értéke természetesen nem nagyobb n-nél. A k raktárat k különböző étteremnél kell felépíteni. Minden éttermet a legközelebbi raktárhoz rendelünk, onnan kapja majd az alapanyagokat. A szállítási költségek minimalizálása érdekében a teljes távolságnak (amelynek definíciója

természetesen a lehető legkisebbnek kell lennie.

Feladat:

Írj programot, amely úgy határozza meg a raktárak helyét, hogy a fenti összeg minimális értéket vesz fel.

Bemenet:

A bemeneti állomány N étteremlánc adatait tartalmazza. Az első sor csak ezt az egy pozitív N értéket foglalja magában. Ezt követik az étteremláncok leírásai. Minden leírás első sorában két egész szám szerepel, a n és a k. (1<=n<=200, 1<=k<=30, k<=n) Az ezt követő n sor soronként egy egészet tartalmaz, amelyek az éttermek di pozícióit adják növekvő rendben.

Kimenet:

A kimeneti állomány első sora az étteremlánc bemeneti állományban elfoglalt helyét adja. Ezt az optimálisan elhelyezett raktárak adatai követik. Minden raktár külön sorba kerül, megjelölve, hogy melyik étterem mellé épül, valamint, hogy mely intervallumba eső éttermeket szolgál ki. Ha több optimális elhelyezése lehetséges a raktáraknak, akkor elegendő egyet megadnod. A raktárak adatait követő sorban tüntesd fel, hogy mekkora a feladat szövegében jelzett össztávolság. Minden tesztesetet egy üres sornak kell követnie.

Példa:
 

food.in	food.ans
1 6 3 5 6 12 19 20 27	Chain 1 Depot 1 at restaurant 2 serves restaurants 1 to 3 Depot 2 at restaurant 4 serves restaurants 4 to 5 Depot 3 at restaurant 6 serves restaurant 6 Total distance sum = 8