37ος ΠΔΠ B' Φάση
Μονοπάτι μανιταριών (shroompath)

Κάθε Δευτέρα, ο Τάκης πηγαίνει στο πασίγνωστο “Μονοπάτι Μανιταριών” της πόλης του, για να μαζέψει επαρκές απόθεμα μανιταριών για όλη την εβδομάδα. Το μονοπάτι περιέχει μανιτάρια δύο ειδών. Κάθε μανιτάρι του πρώτου είδους έχει βάρος \(X\) και κάθε μανιτάρι του δεύτερου είδους έχει βάρος \(Y\). Δημιουργός του μονοπατιού είναι ο φίλος του Τάκη, ο Ανδρέας. Έχοντας μια ιδιαίτερη αγάπη για τα μαθηματικά, δημιούργησε το μονοπάτι με τον εξής, παράξενο τρόπο.

Ξεκίνησε γράφοντας όλες τις συμβολοσειρές που αποτελούνται από τους χαρακτήρες \(A\) και \(B\), με μήκος \(1\), σε αλφαβητική σειρά, χωρίς κενά μεταξύ τους. Έπειτα, χωρίς να αφήσει κενό, έκανε το ίδιο για τις συμβολοσειρές μήκους \(2\), μήκους \(3\) και ούτω καθεξής.

Ας δούμε για παράδειγμα τους πρώτους χαρακτήρες που έγραψε ο Ανδρέας. Για μήκος \(1\), οι συμβολοσειρές είναι οι “A” και “B”, ενώ για μήκος \(2\), οι συμβολοσειρές είναι οι “AA”, “AB”, “BA” και “BB”. Έτσι, οι πρώτοι \(10\) χαρακτήρες που έγραψε είναι οι “ABAAABBABB”.

Στη συνέχεια, ξεκίνησε να καλλιεργεί μανιτάρια. Σε κάθε θέση όπου υπήρχε το γράμμα \(A\) τοποθέτησε ένα μανιτάρι του πρώτου είδους, ενώ σε αυτές με το γράμμα \(B\) τοποθέτησε ένα μανιτάρι του δεύτερου είδους.

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

Βοηθήστε τον Τάκη, βρίσκοντας σε ποια θέση θα έχει συγκεντρώσει για πρώτη φορά μανιτάρια συνολικού βάρους τουλάχιστον \(S\). Μιας και η απάντηση μπορεί να είναι μεγάλη, διαβάστε προσεκτικά παρακάτω το πως πρέπει να την τυπώνετε.

Πρόβλημα

Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες του ΠΔΠ (PASCAL, C, C++, Java) το οποίο θα διαβάζει τα δεδομένα εισόδου από το αρχείο shroompath.in και θα εκτυπώνει τα αποτελέσματα στο αρχείο shroompath.out.

Δεδομένα εισόδου (shroompath.in):

Η πρώτη γραμμή περιέχει τον αριθμό του υποπροβλήματος (βλ. παρακάτω). Η δεύτερη γραμμή περιέχει τρεις ακέραιους αριθμούς \(S\), \(X\) και \(Y\), χωρισμένους μεταξύ τους ανά δύο με ένα κενό διάστημα: το συνολικό βάρος μανιταριών που χρειάζεται ο Τάκης, το βάρος κάθε μανιταριού του πρώτου είδους και το βάρος κάθε μανιταριού του δεύτερου είδους.

Δεδομένα εξόδου (shroompath.out):

Πρέπει να περιέχει μία μόνο γραμμή με έναν ακέραιο αριθμό: την θέση του μονοπατιού όπου ο Τάκης θα έχει συγκεντρώσει για πρώτη φορά μανιτάρια συνολικού βάρους τουλάχιστον \(S\). Επειδή ο αριθμός αυτός μπορεί να είναι πολύ μεγάλος, ζητείται να τυπώσετε το υπόλοιπο της ακέραιας διαίρεσής του (modulo) με τον αριθμό \(10^9+7\).

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

shroompath.in	shroompath.out
1 13 5 3	5

Εξήγηση παραδείγματος: Οι πρώτες \(5\) θέσεις του μονοπατιού είναι οι “ABAAA”. Οι κινήσεις του Τάκη ανά θέση θα είναι οι παρακάτω:

Το καλάθι του είναι άδειο και αυτός απλά μαζεύει το μανιτάρι της θέσης. (Συνολικό βάρος: \(5\))
Το καλάθι περιέχει μανιτάρι διαφορετικού είδους από την θέση και για αυτό το αδειάζει. Έπειτα, μαζεύει το μανιτάρι της θέσης. (Συνολικό βάρος: \(3\))
Το καλάθι περιέχει μανιτάρι διαφορετικού είδους από την θέση και συνεπώς το αδειάζει και πάλι. Στη συνέχεια, μαζεύει το μανιτάρι της θέσης. (Συνολικό βάρος: \(5\))
Το μανιτάρι του καλαθιού δεν διαφέρει από αυτό της θέσης, άρα ο Τάκης δεν αδειάζει το καλάθι του, και μαζεύει κανονικά το μανιτάρι της θέσης του. (Συνολικό βάρος: \(10\))
Ομοίως, ο Τάκης μαζεύει και αυτό το μανιτάρι και πλέον το συνολικό βάρος που έχει συγκεντρώσει είναι \(15\). Αυτό σημαίνει ότι στην 5η θέση φτάνει για πρώτη φορά το ελάχιστο απαιτούμενο βάρος (τουλάχιστον \(13\)).

shroompath.in	shroompath.out
1 10 2 5	7

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

\(1 \leq S \leq 200.000\).
\(0 \leq X,Y \leq 9\).
\(X\neq 0\) ή \(Y\neq 0\).

Υποπροβλήματα:

(15 βαθμοί) \(S\leq 15\)
(28 βαθμοί) \(X\gt Y\)
(36 βαθμοί) \(X = 0\)
(21 βαθμοί) Δεν υπάρχουν περαιτέρω περιορισμοί

Παρατηρήσεις:
Μορφοποίηση: Στην είσοδο αλλά και στην έξοδο, κάθε γραμμή τερματίζει με έναν χαρακτήρα newline.
Μέγιστος χρόνος εκτέλεσης: 1 sec.
Μέγιστη διαθέσιμη μνήμη: 64 MB.