25ος ΠΔΠ Καμπ (juniors)
Ο Τάσος και η Γκόλφω (golfo)

Έστω μία ακολουθία αποτελούμενη από \(N\) διαφορετικούς ανά δύο ακέραιους αριθμούς \(x_1, x_2, \ldots , x_N\). Έστω το πολυσύνολο (multiset) που αποτελείται από όλες τις μη αρνητικές διαφορές ζευγών στοιχείων της ακολουθίας:

\[A = \lbrace x_i − x_j \vert i \neq j \text{ και } x_i > x_j \rbrace\]

Έστω \(K\) ένας φυσικός αριθμός. Ζητείται να βρεθεί το \(K\)-οστό μικρότερο στοιχείο του πολυσυνόλου \(A\).

Αρχεία Εισόδου (golfo.in):

Η είσοδος θα αποτελείται από δύο γραμμές. Η πρώτη γραμμή θα περιέχει δύο φυσικούς αριθμούς \(N\) και \(K\), χωρισμένους μεταξύ τους με ένα κενό διάστημα. Η δεύτερη γραμμή θα περιέχει τους \(N\) ακέραιους αριθμούς \(x_1, x_2, \ldots, x_N\), χωρισμένους ανά δύο με ένα κενό διάστημα.

Αρχεία Εξόδου (golfo.out):

Η έξοδος πρέπει να αποτελείται από μία γραμμή που να περιέχει μόνο έναν φυσικό αριθμό: το \(K\)-οστό μικρότερο στοιχείο του πολυσυνόλου \(A\).

Παραδείγματα Αρχείων Εισόδου - Εξόδου:

1^o

golfo.in	golfo.out
10 1 1 2 5 -3 7 4 -6 8 0 3	1

Εξήγηση 1^ου παραδείγματος: Στο 1^ο παράδειγμα, ζητείται η ελάχιστη διαφορά μεταξύ στοιχείων της ακολουθίας. Αυτή είναι η \(1 = 5−(4)\).

2^o

golfo.in	golfo.out
6 11 1 2 3 4 5 6	3

Εξήγηση 2^ου παραδείγματος: Στο 2^ο παράδειγμα, ζητείται η 11η μικρότερη διαφορά. Το πολυσύνολο \(A\) περιέχει τα εξής στοιχεία:

\[\begin{matrix} 2−1 = 1, & 3−1 = 2, & 4−1 = 3, & 5−1 = 4, & 6−1 = 5, \\ & 3−2 = 1, & 4−2 = 2, & 5−2 = 3, & 6−2 = 4, \\ & & 4−3 = 1, & 5−3 = 2, & 6−3 = 3, \\ & & & 5−4 = 1, & 6−4 = 2, \\ & & & & 6−5 = 1. \end{matrix}\]

δηλαδή \(A = \lbrace 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, \underline{3}, 3, 4, 4, 5 \rbrace\). Άρα το 5ο μεγαλύτερο στοιχείο του είναι το (υπογραμμισμένο) \(3\).

Περιορισμοί:

• \(1 \leq N \leq 300.000\).
• \(1 \leq K \leq N (N−1) / 2\).
• \(1.000.000.000 \leq x_i \leq 1.000.000.000\).
• Όριο χρόνου εκτέλεσης: \(1\) sec.
• Όριο μνήμης: \(64\) MB.
• Προσοχή: Ο αριθμός \(K\) μπορεί να είναι μεγαλύτερος από \(2^{32}\).