עבור רב־קבוצה $S=\{x_0,x_1,\ldots,x_{m-1}\}$ בגודל $m$, נסמן את איבריה לאחר מיון מהגדול לקטן ב־$y_0\geq y_1\geq\cdots\geq y_{m-1}$. נגדיר את החציון שלה $Median(S)$ כאיבר ה־$\lceil m/2\rceil$ בגודלו, כלומר $Median(S)=y_{\lceil m/2\rceil-1}$. שימו לב: הגדרת החציון בשאלה זו עשויה להיות שונה מההגדרה המקובלת.

נתונים סדרה באורך $n$, $[a_0,a_1,\ldots,a_{n-1}]$, ומספר שלם חיובי $k$, כאשר $k\leq n$. נגדיר חלוקה כך: בוחרים סדרת אינדקסים עולה באורך $k-1$, $0<b_1<\cdots<b_{k-1}<n$, המחלקת את הסדרה ל־$k$ קטעים שטווחי האינדקסים שלהם הם $[0,b_1),[b_1,b_2),\ldots,[b_{k-1},n)$, לפי הסדר.

נגדיר את מידת האיזון של חלוקה: מחשבים את חציון רב־הקבוצה של איברי כל קטע, ואז חציון רב־הקבוצה של $k$ החציונים האלה הוא מידת האיזון. באופן פורמלי, עבור החלוקה $b_1,\ldots,b_{k-1}$ נסמן $b_0=0$, $b_k=n$. אם חציון איברי הקטע ה־$i$, כאשר $0\leq i<k$, הוא $c_i=Median(\{a_{b_i},a_{b_i+1},\ldots,a_{b_{i+1}-1}\})$, אז מידת האיזון של החלוקה היא $Median(\{c_0,\ldots,c_{k-1}\})$.

מצאו את מידת האיזון המרבית מבין כל החלוקות.

פרטי מימוש

אין צורך, וגם אין לממש, פונקציית main.

קובץ המקור שתגישו חייב לכלול את הכותרת median.h. כלומר, יש להוסיף בתחילתו:

#include "median.h"

עליכם לממש בקובץ המקור median.cpp את שתי הפונקציות הבאות:

void init(int c, int t);

• $c,t$ מציינים בהתאמה את מספר מקרה הבדיקה ואת מספר קבוצות הנתונים. הערך $c=0$ מציין דוגמה.
• עבור כל מקרה בדיקה, תוכנית הבדיקה תקרא לפונקציה בדיוק פעם אחת בתחילת ריצת התוכנית.

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

• $n,k,a$ מציינים בהתאמה את אורך הסדרה, את מספר הקטעים בחלוקה ואת הסדרה הנתונה.
• הפונקציה צריכה להחזיר את מידת האיזון המרבית.
• עבור כל מקרה בדיקה, תוכנית הבדיקה תקרא לפונקציה בדיוק $t$ פעמים.

הקובץ template_median.cpp שבתיקיית השאלה הוא קוד לדוגמה. אפשר להיעזר בו כדי לממש את הקוד שלכם.

בדיקת התוכנית

אפשר להריץ בתיקיית השאלה את הפקודה הבאה כדי להדר קובץ הרצה:

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

עבור קובץ ההרצה median שהתקבל:

• הוא יקרא מהקלט התקני נתונים בפורמט הבא:

  • השורה הראשונה מכילה שני מספרים שלמים אי־שליליים $c,t$.

  • לאחר מכן מופיעות קבוצות הנתונים לפי הסדר. עבור כל קבוצה:

    • השורה הראשונה מכילה שני מספרים שלמים חיוביים $n,k$.
    • השורה השנייה מכילה $n$ מספרים שלמים חיוביים $a_0,a_1,\ldots,a_{n-1}$.

• הוא יכתוב לפלט התקני נתונים בפורמט הבא:

  • לכל קבוצת נתונים, שורה אחת ובה מספר שלם חיובי המציין את מידת האיזון המרבית.

דוגמאות

קלט 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

פלט 1

9
8

הערה

עבור קבוצת הנתונים הראשונה, חלוקה אחת בעלת מידת איזון מרבית היא $b_1=3,b_2=5,b_3=7$. היא מחלקת את הסדרה לארבעה קטעים $[6,5,1],[9,2],[3,10],[7,4,8]$, שחציוניהם הם $5,9,10,7$, בהתאמה. לכן מידת האיזון היא $Median(\{5,9,10,7\})=9$.

עבור קבוצת הנתונים השנייה, חלוקה אחת בעלת מידת איזון מרבית היא $b_1=2,b_2=4,b_3=6,b_4=8$. היא מחלקת את הסדרה לחמישה קטעים $[5,7],[3,10],[8,2],[9,1],[6,4]$, שחציוניהם הם $7,10,8,9,6$, בהתאמה. לכן מידת האיזון היא $Median(\{7,10,8,9,6\})=8$.

דוגמה 2

ראו את הקבצים median/median2.in ו־median/median2.ans בתיקיית המתחרה.

דוגמה זו מקיימת את המגבלות של מקרה בדיקה $6$.

דוגמה 3

ראו את הקבצים median/median3.in ו־median/median3.ans בתיקיית המתחרה.

דוגמה זו מקיימת את המגבלות של מקרה בדיקה $9$.

דוגמה 4

ראו את הקבצים median/median4.in ו־median/median4.ans בתיקיית המתחרה.

דוגמה זו מקיימת את המגבלות של מקרה בדיקה $14$.

דוגמה 5

ראו את הקבצים median/median5.in ו־median/median5.ans בתיקיית המתחרה.

דוגמה זו מקיימת את המגבלות של מקרי הבדיקה $18\sim20$.

מגבלות

נסמן ב־$N$ את סכום ערכי $n$ על פני כל קבוצות הנתונים במקרה בדיקה אחד. לכל קבוצות הנתונים מתקיים:

• $1\leq t\leq20$;
• $5\leq n\leq10^6$, $2\leq k\leq n$, $N\leq10^6$;
• לכל $0\leq i<n$, מתקיים $1\leq a_i\leq n$.

תכונה מיוחדת A: לכל $0\leq i<n$ מתקיים $a_i\leq2$.