26ος ΠΔΠ Καμπ (κοινά)
Διαδρομές αριθμών (numpath)

Έστω ένα σύνολο \(S = \lbrace x_1, x_2, \ldots, x_N \rbrace\), αποτελούμενο από \(N\) (διαφορετικούς ανά δύο) φυσικούς αριθμούς, καθένας από τους οποίους έχει ακριβώς \(K\) ψηφία. Επομένως, για κάθε στοιχείο \(x_i \in S\) ισχύει \(0 \leq x_i < 10^K\) και ας υποθέσουμε ότι οι αριθμοί μικρότεροι του \(10^{K−1}\) έχουν γραφεί με ακριβώς \(K\) ψηφία από τα οποία τα πρώτα είναι μηδενικά.

Έστω ότι ξεκινάμε από κάποιον από αυτούς τους αριθμούς και εφαρμόζουμε την εξής διαδικασία: επιλέγουμε ένα ψηφίο του και το αντικαθιστούμε με οποιοδήποτε μικρότερό του δεκαδικό ψηφίο θέλουμε, αρκεί να προκύψει ένας αριθμός που να ανήκει στο σύνολο \(S\). Επαναλαμβάνουμε αυτή τη διαδικασία όσες φορές θέλουμε (και μπορούμε), έστω \(M\).

Δεδομένων των \(N\), \(K\), και \(S\), ζητείται να βρεθεί το μέγιστο δυνατό \(M\) που μπορεί να προκύψει από αυτή τη διαδικασία.

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

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

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

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

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

1^o

numpath.in	numpath.out
9 3 123 991 323 321 329 121 921 125 999	4

Εξήγηση 1^ου παραδείγματος: Μπορούμε να ξεκινήσουμε από τον αριθμό \(999\) και να κινηθούμε ως εξής: \(99\underline{9} \to 9\underline{9}1 \to \underline{9}21 \to \underline{3}21 \to 121\), κάνοντας συνολικά τέσσερις αντικαταστάσεις ψηφίων (τα ψηφία που αντικαθίστανται είναι υπογραμμισμένα). Δεν υπάρχει άλλη μεγαλύτερη ακολουθία αντικαταστάσεων.

2^o

numpath.in	numpath.out
4 2 17 23 09 42	0

Εξήγηση 2^ου παραδείγματος: Από οποιονδήποτε αριθμό και αν ξεκινήσουμε, δεν μπορεί να γίνει καμία αντικατάσταση.

Περιορισμοί

• \(2 \leq N \leq 100.000\).
• \(1 \leq K \leq 18\).
• Όριο χρόνου εκτέλεσης: \(1\) sec.
• Όριο μνήμης: \(64\) MB.
• Προσοχή: Οι αριθμοί \(x_1, x_2, \ldots, x_N\) μπορεί να είναι μεγαλύτεροι από \(232\).