31ος ΠΔΠ Γ' Φάση
Τι πληρώνει το λαχείο (lottery)

Σε μία λαχειοφόρο αγορά, έστω ότι έχουν διατεθεί \(N\) λαχνοί, καθένας από τους οποίους είναι ένας φυσικός αριθμός \(X_i\) αποτελούμενος από ακριβώς \(K\) δεκαδικά ψηφία (οι λαχνοί επιτρέπεται να ξεκινούν και με το ψηφίο \(0\)). Kληρώνεται ένας τυχερός αριθμός \(Y\). Βάσει αυτού του αριθμού, κάθε λαχνός κερδίζει ένα χρηματικό ποσό ως εξής: αν τα \(M\) τελευταία ψηφία του λαχνού \(X_i\) είναι τα ίδια με τα \(M\) τελευταία (λήγοντα) ψηφία του τυχερού αριθμού \(Y\), τότε ο κάτοχος του λαχνού κερδίζει \(2^M−1\) ευρώ.

Για παράδειγμα, αν \(K = 6\), \(X_i = 391742\) και \(Y = 421742\), τότε ο λαχνός \(X_i\) έχει \(M = 4\) κοινά λήγοντα ψηφία με τον τυχερό αριθμό \(Y\) (δηλαδή και οι δύο λήγουν σε \(1742\)) και ο κάτοχός του κερδίζει \(2^4−1 = 15\) ευρώ.

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

Πρόβλημα

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

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

Το αρχείο εισόδου με όνομα lottery.in είναι αρχείο κειμένου με την εξής δομή. Η πρώτη γραμμή του περιέχει τρεις ακέραιους αριθμούς \(K\), \(N\), και \(Q\), χωρισμένους ανά δύο με ένα κενό διάστημα: \(K\) είναι το πλήθος των δεκαδικών ψηφίων των λαχνών, \(N\) είναι το πλήθος των λαχνών που έχουν διατεθεί και \(Q\) το πλήθος των εναλλακτικών τυχερών αριθμών. Kάθε μία από τις επόμενες \(N\) γραμμές θα περιέχει έναν ακέραιο αριθμό \(X_i\) με ακριβώς \(K\) ψηφία, που παριστάνει έναν λαχνό που έχει διατεθεί. Kάθε μία από τις επόμενες \(Q\) γραμμές θα περιέχει έναν ακέραιο αριθμό \(Y_i\) με ακριβώς \(K\) ψηφία, που παριστάνει έναν εναλλακτικό τυχερό αριθμό.

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

Το αρχείο εξόδου με όνομα lottery.out είναι αρχείο κειμένου με την εξής δομή. Έχει ακριβώς \(Q\) γραμμές. Kάθε μία από αυτές αντιστοιχεί κατά σειρά σε έναν εναλλακτικό τυχερό αριθμό \(Y_i\) και περιέχει δύο ακέραιους αριθμούς \(C_i\) και \(S_i\) χωρισμένους με ένα κενό διάστημα: \(C_i\) είναι το πλήθος των λαχνών που κερδίζουν και \(S_i\) το υπόλοιπο της ακέραιας διαίρεσης (modulo) του συνολικού ποσού που κερδίζουν όλοι οι λαχνοί με τον αριθμό \(10^9+7\).

1^o

lottery.in	lottery.out
6 1 1 391742 421742	1 15

Εξήγηση: Υπάρχει ένας λαχνός (\(391742\)) και ένας εναλλακτικός τυχερός αριθμός (\(421742\)). Το παράδειγμα αυτό εξηγείται παραπάνω στην εκφώνηση.

2^o

lottery.in	lottery.out
4 6 3 3581 2619 4904 8859 3919 4964 4904 8933 3419	2 16 0 0 3 7

Εξήγηση: Υπάρχουν έξι λαχνοί (\(3581\), \(2619\), \(4904\), \(8859\), \(3919\), \(4964\)) και τρεις εναλλακτικοί τυχεροί αριθμοί (\(4904\), \(8933\), \(3419\)). Αν κληρωθεί ο πρώτος (\(4904\)) τότε θα κερδίσει \(15\) ευρώ ο λαχνός \(4904\) (που συμπίπτει με τον τυχερό αριθμό) και \(1\) ευρώ ο \(4964\). Αν κληρωθεί ο δεύτερος (\(8933\)) τότε δεν κερδίζει κανένας λαχνός. Αν κληρωθεί ο τρίτος (\(3419\)) τότε οι λαχνοί \(2619\) και \(3919\) κερδίζουν από \(3\) ευρώ καθένας και ο \(8859\) κερδίζει \(1\) ευρώ.

Περιορισμοί

• Για περιπτώσεις ελέγχου συνολικής αξίας 20%, θα είναι: \(1 \leq K \leq 9\), \(1 \leq N \leq 1000\), \(1 \leq Q \leq 1000\), \(0 \leq S_i \leq 10^9\)
• Για περιπτώσεις ελέγχου συνολικής αξίας 40%, θα είναι: \(1 \leq K \leq 30\), \(1 \leq N \leq 1000\), \(1 \leq Q \leq 1000\), \(0 \leq S_i \leq 10^9\)
• Για περιπτώσεις ελέγχου συνολικής αξίας 100%, θα είναι: \(1 \leq K \leq 100\), \(1 \leq N \leq 1.000.000\), \(1 \leq Q \leq 1.000.000\) \((N+Q)\cdot K ≤ 1.000.000\)

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

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

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