Für eine Multimenge $S=\{x_0,x_1,\ldots,x_{m-1}\}$ der Größe $m$ seien ihre Elemente absteigend als $y_0\ge y_1\ge\cdots\ge y_{m-1}$ sortiert. Ihr Median $\operatorname{Median}(S)$ ist als das $\lceil m/2\rceil$-größte Element definiert, also $\operatorname{Median}(S)=y_{\lceil m/2\rceil-1}$. Beachte, dass die Mediandefinition dieser Aufgabe von der üblichen Definition abweichen kann.

Gegeben sind eine Folge $[a_0,a_1,\ldots,a_{n-1}]$ der Länge $n$ und eine positive ganze Zahl $k\le n$. Eine Aufteilung ist wie folgt definiert: Wähle eine streng wachsende Indexfolge $0<b_1<\cdots<b_{k-1}<n$ der Länge $k-1$. Dadurch wird die ursprüngliche Folge in $k$ Abschnitte mit den Indexintervallen $[0,b_1),[b_1,b_2),\ldots,[b_{k-1},n)$ aufgeteilt.

Die Ausgewogenheit einer Aufteilung definieren wir so: Berechne für jeden Abschnitt den Median der Multimenge seiner Elemente. Der Median der Multimenge dieser $k$ Mediane ist die Ausgewogenheit der Aufteilung. Formal setzen wir für die Aufteilung $b_1,\ldots,b_{k-1}$ die Grenzen $b_0=0$, $b_k=n$. Für Abschnitt $i$ mit $0\le i<k$ sei $c_i=\operatorname{Median}(\{a_{b_i},a_{b_i+1},\ldots,a_{b_{i+1}-1}\})$. Dann ist die Ausgewogenheit der Aufteilung $\operatorname{Median}(\{c_0,\ldots,c_{k-1}\})$.

Bestimme die größtmögliche Ausgewogenheit unter allen Aufteilungen.

Implementierungsdetails

Du musst und sollst keine Funktion main implementieren.

Stelle sicher, dass deine eingereichte Quelldatei den Header median.h einbindet. Füge dazu am Anfang die folgende Zeile ein:

#include "median.h"

In deiner eingereichten Quelldatei median.cpp musst du die folgenden beiden Funktionen implementieren:

void init(int c, int t);

• $c,t$ geben die Testfallnummer und die Anzahl der Testdatensätze an. $c=0$ bedeutet, dass es sich um einen Beispieltestfall handelt.
• Für jeden Testfall ruft das Bewertungsprogramm diese Funktion zu Beginn der Programmausführung genau einmal auf.

int median(int n, int k, std::vector<int> a);

• $n,k,a$ sind die Folgenlänge, die Anzahl der Abschnitte und die gegebene Folge.
• Die Funktion muss die größtmögliche Ausgewogenheit zurückgeben.
• Für jeden Testfall ruft das Bewertungsprogramm diese Funktion genau $t$ Mal auf.

Die Datei template_median.cpp im Aufgabenverzeichnis enthält Beispielcode, an dem du dich bei deiner Implementierung orientieren kannst.

Dein Programm testen

Im Aufgabenverzeichnis kannst du mit folgendem Befehl eine ausführbare Datei erzeugen:

g++ grader.cpp median.cpp -o median -O2 -std=c++14 -static

Für die erzeugte ausführbare Datei median gilt:

• Sie liest die Daten im folgenden Format von der Standardeingabe. Die erste Zeile enthält zwei nichtnegative ganze Zahlen $c,t$. Es folgen die einzelnen Testdatensätze. Für jeden Datensatz enthält die erste Zeile zwei positive ganze Zahlen $n,k$, die zweite $n$ positive ganze Zahlen $a_0,a_1,\ldots,a_{n-1}$.
• Sie schreibt die Daten im folgenden Format auf die Standardausgabe: Für jeden Datensatz wird eine Zeile mit einer positiven ganzen Zahl ausgegeben, der größtmöglichen Ausgewogenheit.

Beispiele

Eingabe 1

0 2
10 4
6 5 1 9 2 3 10 7 4 8
10 5
5 7 3 10 8 2 9 1 6 4

Ausgabe 1

9
8

Hinweis

Für den ersten Datensatz ist eine Aufteilung mit größtmöglicher Ausgewogenheit $b_1=3$, $b_2=5$, $b_3=7$. Sie teilt die Folge in die 4 Abschnitte $[6,5,1]$, $[9,2]$, $[3,10]$, $[7,4,8]$. Ihre Mediane sind der Reihe nach $5,9,10,7$. Daher ist die Ausgewogenheit dieser Aufteilung $\operatorname{Median}(\{5,9,10,7\})=9$.

Für den zweiten Datensatz ist eine Aufteilung mit größtmöglicher Ausgewogenheit $b_1=2$, $b_2=4$, $b_3=6$, $b_4=8$. Sie teilt die Folge in die 5 Abschnitte $[5,7]$, $[3,10]$, $[8,2]$, $[9,1]$, $[6,4]$. Ihre Mediane sind der Reihe nach $7,10,8,9,6$. Daher ist die Ausgewogenheit dieser Aufteilung $\operatorname{Median}(\{7,10,8,9,6\})=8$.

Beispiel 2

Siehe median/median2.in und median/median2.ans im Teilnehmerverzeichnis.

Dieses Beispiel erfüllt die Einschränkungen von Testfall $6$.

Beispiel 3

Siehe median/median3.in und median/median3.ans im Teilnehmerverzeichnis.

Dieses Beispiel erfüllt die Einschränkungen von Testfall $9$.

Beispiel 4

Siehe median/median4.in und median/median4.ans im Teilnehmerverzeichnis.

Dieses Beispiel erfüllt die Einschränkungen von Testfall $14$.

Beispiel 5

Siehe median/median5.in und median/median5.ans im Teilnehmerverzeichnis.

Dieses Beispiel erfüllt die Einschränkungen der Testfälle $18\text{–}20$.

Beschränkungen

$N$ sei die Summe aller Werte $n$ innerhalb eines einzelnen Testfalls. Für alle Testdaten gilt:

• $1\le t\le20$;
• $5\le n\le10^6$, $2\le k\le n$, $N\le10^6$;
• für jedes $0\le i<n$ gilt $1\le a_i\le n$.

Besondere Eigenschaft A: Für jedes $0\le i<n$ gilt $a_i\le2$.