29ος ΠΔΠ B' Φάση Γυμνασίου
Πολύχρωμη κορδέλα (colors)

Στη γάτα μου αρέσει να παίζει με μια πολύχρωμη κορδέλα. Η κορδέλα έχει μήκος \(N\) εκατοστά και κάθε εκατοστό της είναι χρωματισμένο με ένα χρώμα από \(K\) δυνατά χρώματα, αριθμημένα από το \(1\) έως και το \(K\).

Στο παραπάνω παράδειγμα, η κορδέλα έχει μήκος \(N=10\) εκατοστά και υπάρχουν \(K=3\) χρώματα: το κίτρινο (1), το πορτοκαλί (2) και το πράσινο (3). Όπως βλέπετε, κάθε εκατοστό της κορδέλας είναι χρωματισμένο με ένα από αυτά.

Η γάτα μου έχει καλλιτεχνικές τάσεις και αρνείται να παίξει με την κορδέλα, αν δεν έχει όλα τα χρώματα από το \(1\) έως και το \(K\). Αν όμως η κορδέλα είναι πολύ μακριά, τότε εύκολα μπερδεύεται και η γάτα μου εκνευρίζεται.

Βοηθήστε με να βρω και να της κόψω το μικρότερο δυνατό κομμάτι της κορδέλας που να περιέχει όλα τα χρώματα!

Πρόβλημα

Nα αναπτύξετε ένα πρόγραμμα σε μια από τις Γλώσσες του IOI (PASCAL, C, C++, Java) το οποίο, αφού διαβάσει το μήκος της κορδέλας, το πλήθος των χρωμάτων και τους κωδικούς των χρωμάτων με τα οποία είναι χρωματισμένο κάθε εκατοστό της κορδέλας, θα επιστρέφει το μήκος του ελάχιστου δυνατού κομματιού της κορδέλας που περιέχει όλα τα χρώματα.

Αρχεία εισόδου

Τα αρχεία εισόδου με όνομα colors.in είναι αρχεία κειμένου με την εξής δομή: Έχουν ακριβώς δύο γραμμές. Στην πρώτη γραμμή υπάρχουν δύο ακέραιοι αριθμοί χωρισμένοι μεταξύ τους με ένα κενό διάστημα: Tο μήκος της κορδέλας \(N\) (\(1 \leq N \leq 1.000.000\)) και το πλήθος των χρωμάτων \(K\) (\(1 \leq K \leq 100.000\)). Στη δεύτερη γραμμή υπάρχουν ακριβώς \(N\) ακέραιοι αριθμοί \(c\) (\(1 \leq c \leq K\)) χωρισμένοι μεταξύ τους με ένα κενό διάστημα. Οι αριθμοί αυτοί είναι οι κωδικοί των χρωμάτων με τα οποία είναι χρωματισμένο κάθε εκατοστό της κορδέλας, από τη μία άκρη μέχρι την άλλη.

Αρχεία εξόδου

Τα αρχεία εξόδου με όνομα colors.out είναι αρχεία κειμένου με την εξής δομή: Έχουν ακριβώς μία γραμμή με ακριβώς έναν ακέραιο αριθμό: το μήκος του μικρότερου δυνατού κομματιού της κορδέλας που περιέχει όλα τα χρώματα μεταξύ \(1\) και \(K\). Αν δεν υπάρχει τέτοιο κομμάτι (γιατί στην αρχική κορδέλα δεν υπήρχαν όλα τα χρώματα), τότε στην έξοδο πρέπει να γράφεται ο αριθμός \(0\) (μηδέν).

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

1^o

colors.in	colors.out
10 3 1 3 1 3 1 3 3 2 2 1	4

Το παράδειγμα αυτό αντιστοιχεί στην κορδέλα του σχήματος της προηγούμενης σελίδας. Υπάρχουν δύο κομμάτια που περιέχουν όλα τα χρώματα και έχουν μήκος \(4\):

2^o

colors.in	colors.out
10 4 2 1 4 4 4 1 1 1 4 3	10

Στο παράδειγμα αυτό πρέπει να κρατήσουμε ολόκληρη την κορδέλα.

3^o

colors.in	colors.out
10 5 1 2 2 5 1 3 1 2 1 3	0

Στο παράδειγμα αυτό λείπει το χρώμα \(4\) από την κορδέλα.

Παρατηρήσεις