36ος ΠΔΠ Γ' Φάση
Bits με υπογραφή (bitsign)

Έστω μια ακολουθία αποτελούμενη από δυαδικά ψηφία (bits). Για τις ανάγκες αυτής της άσκησης, θα υπολογίζουμε την υπογραφή αυτής της ακολουθίας μετρώντας το πλήθος των διαδοχικών ψηφίων “1” (άσων) που εμφανίζονται σε αυτήν. Για παράδειγμα, έστω η ακολουθία:

\[\texttt{00{\color{red}111}0{\textcolor{red}{11}}000{\color{red}1111}0{\color{red}1}}\]

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

Προσέξτε ότι ακριβώς την ίδια υπογραφή έχει και η ακολουθία:

\[\texttt{\textcolor{red}{111}0000\textcolor{red}{11}0\textcolor{red}{1111}00000\textcolor{red}{1}0000}\]

Σας δίνεται μία ακολουθία αποτελούμενη από \(N\) δυαδικά ψηφία, κάποια από τα οποία είναι όμως σβησμένα: στη θέση τους υπάρχει το σύμβολο της τελείας. Για παράδειγμα:

\[\texttt{00.\textcolor{red}{11}.\textcolor{red}{11}0....\textcolor{red}{1}..\textcolor{red}{1}}\]

Σας δίνεται επίσης μία επιθυμητή υπογραφή, π.χ. \(3\), \(2\), \(4\), \(1\). Με πόσους διαφορετικούς τρόπους μπορείτε να συμπληρώσετε τις τελείες με δυαδικά ψηφία, έτσι ώστε η ακολουθία δυαδικών ψηφίων που θα προκύψει να έχει τη δοθείσα υπογραφή;

Πρόβλημα

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

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

Το αρχείο εισόδου με όνομα bitsign.in είναι αρχείο κειμένου με την εξής δομή. Η πρώτη γραμμή περιέχει έναν ακέραιο αριθμό \(T\), το πλήθος των ερωτημάτων που θα ακολουθήσουν. Ακολουθούν τα \(T\) ερωτήματα, που το καθένα περιγράφεται από τρεις γραμμές της εισόδου. Η πρώτη από αυτές θα περιέχει δύο ακέραιους αριθμούς \(N\) και \(M\), χωρισμένους μεταξύ τους με ένα κενό διάστημα: το πλήθος των ψηφίων της ακολουθίας και το πλήθος των αριθμών της υπογραφής. Η δεύτερη θα περιέχει μία συμβολοσειρά αποτελούμενη από \(N\) χαρακτήρες που καθένας μπορεί να είναι “0”, “1” ή “.” (τελεία). Η τρίτη θα περιέχει \(M\) θετικούς ακέραιους αριθμούς, χωρισμένους ανά δύο με ένα κενό διάστημα: την επιθυμητή υπογραφή.

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

Το αρχείο εξόδου με όνομα bitsign.out είναι αρχείο κειμένου με την εξής δομή. Θα πρέπει να περιέχει \(T\) γραμμές: μία γραμμή για κάθε ερώτημα, κατά σειρά. Κάθε γραμμή θα πρέπει να περιέχει έναν ακέραιο, την απάντηση στο αντίστοιχο ερώτημα. Επειδή οι απαντήσεις μπορεί γενικά να είναι πολύ μεγάλοι αριθμοί, εκτυπώστε το υπόλοιπο (modulo) της διαίρεσής τους με τον αριθμό \(1.000.000.007\).

Παράδειγμα αρχείου εισόδου – εξόδου

bitsign.in	bitsign.out
5 7 3 …0111 1 1 3 14 3 0..00..000.110 1 1 3 15 4 .1.1.1.1.1.1.1. 1 3 1 6 13 3 .0..0.0001000 4 1 1 12 3 .111…….. 3 2 1	1 4 1 0 10

Εξήγηση: Έχουμε \(T=5\) ερωτήματα.

• Στο πρώτο ερώτημα, μπορούμε να συμπληρώσουμε την ακολουθία μόνο με έναν τρόπο, έτσι ώστε να προκύψει η επιθυμητή υπογραφή (υπογραμμισμένα τα σβησμένα ψηφία που συμπληρώθηκαν): \(\texttt{\underline{\textcolor{red}{1}0\textcolor{red}{1}}0\textcolor{red}{111}}\)
• Στο δεύτερο όμως ερώτημα, για την ίδια υπογραφή, μπορούμε να συμπληρώσουμε την ακολουθία με τέσσερις διαφορετικούς τρόπους: \(\texttt{0\underline{\textcolor{red}{1}0}00\underline{\textcolor{red}{1}0}000\underline{\textcolor{red}{1}}\textcolor{red}{11}0}\), \(\texttt{0\underline{\textcolor{red}{1}0}00\underline{0\textcolor{red}{1}}000\underline{\textcolor{red}{1}}\textcolor{red}{11}0}\), \(\texttt{0\underline{0\textcolor{red}{1}}00\underline{\textcolor{red}{1}0}000\underline{\textcolor{red}{1}}\textcolor{red}{11}0}\) και \(\texttt{0\underline{0\textcolor{red}{1}}00\underline{0\textcolor{red}{1}}000\underline{\textcolor{red}{1}}\textcolor{red}{111}0}\)
• Στο τρίτο ερώτημα, υπάρχει πάλι μόνο ένας τρόπος να συμπληρώσουμε την ακολουθία για να προκύψει η επιθυμητή υπογραφή: \(\texttt{\underline{0}\textcolor{red}{1}\underline{0}\textcolor{red}{1}\underline{\textcolor{red}{1}}\textcolor{red}{1}\underline{0}\textcolor{red}{1}\underline{0}\textcolor{red}{1}\underline{\textcolor{red}{1}}\textcolor{red}{1}\underline{\textcolor{red}{1}}\textcolor{red}{1}\underline{\textcolor{red}{1}}}\)
• Στο τέταρτο ερώτημα, δεν υπάρχει κανένας τρόπος με τον οποίο να μπορεί να προκύψει η επιθυμητή υπογραφή, καθώς δεν μπορούν να προκύψουν τέσσερις συνεχόμενοι άσοι.
• Στο τελευταίο ερώτημα, η σωστή απάντηση είναι \(10\).

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

• \(1 \leq T \leq 10\),
• \(1 \leq N \leq 2.000\) και \(1 \leq M \leq 1.000\),
• Το άθροισμα των μηκών των ακολουθιών όλων των ερωτημάτων δε θα υπερβαίνει το \(3.000\).

Subtasks

• Για περιπτώσεις ελέγχου συνολικής αξίας 20%, θα είναι \(N \leq 15\).
• Για περιπτώσεις ελέγχου συνολικής αξίας 30%, το πλήθος των σβησμένων ψηφίων κάθε ακολουθίας δε θα υπερβαίνει το \(15\).
• Για περιπτώσεις ελέγχου συνολικής αξίας 50%, θα είναι \(N \leq 100\).

Προσοχή! Φροντίστε να διαβάζετε την είσοδο και να εκτυπώνετε την έξοδο αποδοτικά, ειδικά αν προγραμματίζετε σε C++ ή Java.

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