Koniec kola: 1. november 2021 23:59
5 dní
Počet bodov:
Popis:  12b
Program:  8b

V základnej škole Kráľa Svätopluka Prvého majú obrovskú knižnicu. Je to veľká kruhová miestnosť, v ktorej je pozdĺž stien nad sebou umiestnených \(n\) dlhých políc. Každá polica je kruhová a ide kolom dokola celej miestnosti. (Samozrejme, sú tam aj dvere, takže nejde úplne dokola, ale tie pre túto úlohu nie sú zaujímavé.) Každú policu si teda môžeme predstaviť ako kružnicu.

Na každú policu sa vojde \(s\) kníh, pre jednoduchosť majú všetky rovnakú šírku. Na každej z nich je zároveň práve jedna (špeciálna) červená kniha. Medzi inými je tam aj Červená algebra, no sú tam aj knihy, ktoré sú červené len preto, že ich obaly nespolušní žiaci zafarbili voskovkami.

Úloha

Knihovníkovi sa nepáči, ako sú červené knihy na náhodných miestach a nepríjemne to bije do očí. Bol by rád, keby sa všetky červené knihy nachádzali nad sebou v jednom stĺpci. Zároveň by chcel, aby sa knihy presunuli o čo najmenšiu celkovú vzdialenosť.

Vzdialenosť meriame po polici popri stene (teda nie krížom cez miestnosť). Knihy nie je možné meniť medzi policami (každá kniha musí ostať vo svojeje polici). Celkovú vzdialenosť dostaneme tak, že sčítame vzdialenosť, o ktorú sa posunula kniha na každej polici. Knihovník si môže vybrať, ktorým smerom chce knihu posúvať (doľava alebo doprava).

Pozície, na ktorých sú knihy, si môžeme očíslovať od \(0\) do \(s-1\), pričom susedné pozície sú vždy \(i\) a \(i+1\), ale aj \(0\) a \(s-1\) (police sú kruhové). Ak napríklad máme policu s dĺžkou na \(s=16\) kníh a chceme premiestniť červenú knihu z pozície \(4\) na pozíciu \(13\), môžeme ju posunúť v smere rastu čísel (doprava) o \(9\) pozícií (\(13-4=9\)). Lepšie je však posunúť ju opačným smerom, takto prekoná vzdialenosť iba \(7\) pozícií (vzdialenosť \(4\) na pozíciu \(0\) a \(16-13=3\) na pozíciu \(13\)).

Pomôžte knihovníkovi nájsť optimálny spôsob premiestnenia kníh.

Formát vstupu

Na prvom riadku dostanete čísla \(n\) a \(s\) – počet políc v knižnici a veľkosť jednej police.

Na druhom riadku sa nachádza \(n\) celých čísel z rozsahu od \(0\) do \(s-1\) – pozície červenej knihy v jednotlivých policiach.

Formát výstupu

Vypíšte jedno číslo – najmenšiu celkovú vzdialenosť, o ktorú je potrebné červené knihy presunúť. Nezabudnite na znak konca riadka.

Hodnotenie

Sú štyri sady vstupov. Platia v nich nasledovné obmedzenia:

Sada 1 2 3 4
\(1 \leq n \leq\) \(8\) \(1000\) \(100\,000\) \(100\,000\)
\(1 \leq s \leq\) \(16\) \(2000\) \(100\,000\) \(10^{9}\)

Príklad

Input:

5 5
0 1 2 3 4

Output:

6

Knižnica má \(5\) políc, každá má veľkosť \(5\). Rozmiestnenie kníh vyzerá takto (X je červená kniha):

|X....|
|.X...|
|..X..|
|...X.|
|....X|

Police sú kruhové, teda pravý okraj je napojený na ľavý. Jedno možné riešenie je presunúť všetky knihy do stĺpca (na pozície) \(2\), v jednotlivých riadkoch teda vykonáme presuny o \(2\), \(1\), \(0\), \(1\) a \(2\) pozície, dokopy je to \(6\). V tomto prípade sme kruhovosť nevyužili, ale rovnako dobre ju využiť vieme a na \(6\) krokov presunúť všetky knihy do stĺpca \(0\) či ktoréhokoľvek iného.

Input:

3 10
0 0 8

Output:

2

Knihu v tretej polici posunieme o dve pozície vpravo, čím sa dostane z pozície \(8\) cez pozíciu \(9\) na pozíciu \(0\).

|X.........|
|X.........|
|........X.|

Input:

2 5
2 3

Output:

1

Knihy sú v susedných stĺpcoch, stačí jednu presunúť k druhej.

|..X..|
|...X.|

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.