28ος ΠΔΠ B' Φάση Γυμνασίου
Ο χαρταετός (kite)

Ο Κώστας ετοιμάζεται για την Καθαρή Δευτέρα. Έχει φτιάξει το χαρταετό του και του λείπει η καλούμπα (ο λεπτός σπάγκος με τον οποίο θα δέσει και θα κρατάει το χαρταετό). Δεν έχει χρήματα για να αγοράσει καινούργια από τον παντοπωλείο της γειτονιάς, αλλά ευτυχώς ο καλός παντοπώλης τού χαρίζει μια παλιά που την είχε για πέταμα. Υπάρχει όμως ένα πρόβλημα:

Η παλιά καλούμπα δεν είναι μονοκόμματη. Αποτελείται από \(N\) κομμάτια σπάγκου, διαφορετικών χρωμάτων, δεμένα μεταξύ τους δίπλα-δίπλα ώστε να σχηματίζουν ένα μεγάλο σπάγκο.
Ο Κώστας θέλει να χρησιμοποιήσει κάποια από αυτά τα κομμάτια για να φτιάξει μία καλούμπα με μήκος ακριβώς \(K\) μέτρα (ούτε μικρότερη, ούτε μεγαλύτερη).
Δεν έχει μαχαίρι ή ψαλίδι και δεν μπορεί να κόψει την καλούμπα στο σημείο που θα τον βόλευε για να πετύχει το σκοπό του.
Μπορεί να λύσει τους κόμπους που ενώνουν τα κομμάτια της καλούμπας, με μεγάλη όμως προσπάθεια γιατί είναι πολύ σφιχτοί, κι έτσι δε θέλει να λύσει περισσότερους από δύο. Επίσης, ο Κώστας δεν είναι καλός στο να δένει κόμπους κι έτσι δεν μπορεί μετά να ενώσει τα κομμάτια που έλυσε.

Κατόπιν όλων αυτών, ο Κώστας σκέφτεται ότι πρέπει να βρει μερικά διαδοχικά κομμάτια της παλιάς καλούμπας (στην αρχή, κάπου ενδιάμεσα ή και στο τέλος) που να έχουν συνολικό μήκος ακριβώς \(K\) μέτρα. Αν υπάρχουν πολλοί τρόποι για να το κάνει αυτό, θέλει να διαλέξει τα λιγότερα δυνατά κομμάτια, για να μην κοροϊδεύουν οι φίλοι του την πολύχρωμη καλούμπα του.

Π.χ., έστω ότι η καλούμπα αποτελείται από \(N=6\) κομμάτια ως εξής:

Rope

και έστω ότι ο Κώστας θέλει να φτιάξει μια καλούμπα με μήκος \(K=33\) μέτρα. Τότε, μπορεί να διαλέξει τρία κομμάτια, το πράσινο, το μωβ και το γαλάζιο, και να έχει συνολικά \(20+3+10=33\) μέτρα.

Μπορείτε να βοηθήσετε τον Κώστα να λύσει αυτό το πρόβλημα;

Πρόβλημα

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

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

Τα αρχεία εισόδου με όνομα kite.in είναι αρχεία κειμένου με την εξής δομή: Έχουν ακριβώς δύο γραμμές.

Η πρώτη περιέχει δύο ακέραιους \(N\) και \(K\) που χωρίζονται μεταξύ τους με ένα κενό διάστημα: το πλήθος των κομματιών της καλούμπας και το επιθυμητό μήκος (σε μέτρα).
Η δεύτερη γραμμή περιέχει ακριβώς \(N\) ακέραιους \(M_i\) που χωρίζονται μεταξύ τους με ένα κενό διάστημα. Ο ακέραιος \(M_i\) είναι το μήκος (σε μέτρα) του \(i\)-οστού κομματιού της καλούμπας.

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

Τα αρχεία εξόδου με όνομα kite.out είναι αρχεία κειμένου με την εξής δομή: Έχουν ακριβώς μία γραμμή που περιέχει ακριβώς έναν ακέραιο αριθμό, το ελάχιστο πλήθος διαδοχικών κομματιών που μπορεί να πάρει ο Κώστας ώστε να έχει το συνολικό μήκος που θέλει.

Αν το πρόβλημα δεν έχει λύση, δηλαδή αν αυτό που θέλει ο Κώστας δεν μπορεί να γίνει με κανέναν τρόπο, η μοναδική γραμμή της εξόδου θα πρέπει να περιέχει τον αριθμό \(0\) (μηδέν).

Όρια

\(1 \le N \le 2.000.000\),
\(1 \le K \le 1.000.000.000\),
\(1 \le M_i \le 1.000.000\), όπου \(1 \le i \le N\).
Ο ακέραιος \(M_i\) είναι το μήκος (σε μέτρα) του \(i\)-οστού κομματιού της καλούμπας.
Μπορείτε να θεωρήσετε ότι το άθροισμα όλων των \(M_i\) δε θα υπερβαίνει το \(2.000.000.000\).

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

1^o

kite.in	kite.out
6 33 1 4 20 3 10 5	3

Εξήγηση: Αυτό είναι ακριβώς το παράδειγμα της προηγούμενης σελίδας.

2^o

kite.in	kite.out
10 20 3 4 1 6 5 4 12 13 7 8	2