27ος ΠΔΠ Καμπ (seniors)
Χαρούμενοι αριθμοί (happy)
Έστω ένας φυσικός αριθμός \(N\). Ξεκινάμε από αυτόν και εφαρμόζουμε την ακόλουθη διαδικασία. Αθροίζουμε τα τετράγωνα όλων των ψηφίων του αριθμού, αντικαθιστούμε τον αριθμό με το αποτέλεσμα, και επαναλαμβάνουμε τη διαδικασία. Αν μετά από κάποια βήματα το αποτέλεσμα γίνει ίσο με \(1\) (και επομένως παραμείνει εκεί), τότε λέμε ότι ο αριθμός \(N\) είναι χαρούμενος. Αντίθετα, αν η διαδικασία επαναλαμβάνεται επ’ άπειρον χωρίς ποτέ να προκύπτει ο αριθμός \(1\), τότε λέμε ότι ο αριθμός \(N\) είναι λυπημένος.
Για παράδειγμα, ο αριθμός \(7\) είναι χαρούμενος γιατί η διαδικασία που περιγράφηκε παραπάνω οδηγεί στα ακόλουθα βήματα: \(7\), \(49\), \(97\), \(130\), \(10\), \(1\), \(1\), \(1\ldots\). Αντίθετα, ο αριθμός \(42\) είναι λυπημένος γιατί η διαδικασία οδηγεί σε μία άπειρη ακολουθία \(42\), \(20\), \(4\), \(16\), \(37\), \(58\), \(89\), \(145\), \(42\), \(20\), \(4\), \(16\), \(37 \ldots\).
Θέλουμε να μπορούμε να απαντάμε σε ερωτήματα της μορφής: πόσοι χαρούμενοι αριθμοί υπάρχουν στο διάστημα μεταξύ των αριθμών \(A\) και \(B\) (συμπεριλαμβανομένων).
Αρχεία Εισόδου (happy.in):
Η πρώτη γραμμή της εισόδου θα περιέχει ένα φυσικό αριθμό \(K\), το πλήθος των ερωτημάτων που θα γίνουν. Κάθε μία από τις επόμενες \(K\) γραμμές της εισόδου θα περιέχει δύο φυσικούς αριθμούς \(A\) και \(B\) χωρισμένους μεταξύ τους με ένα κενό διάστημα: τα όρια του διαστήματος που αντιστοιχεί σε ένα ερώτημα.
Αρχεία Εξόδου (happy.out):
Η έξοδος πρέπει να αποτελείται από \(K\) γραμμές, κάθε μία από τις οποίες θα περιέχει έναν μόνο φυσικό αριθμό: το πλήθος των χαρούμενων αριθμών που είναι η απάντηση στο αντίστοιχο ερώτημα.
Παράδειγμα Αρχείου Εισόδου - Εξόδου:
| happy.in | happy.out |
|---|---|
| 7 8 10 34 43 13 28 17 17 27 41 0 42 1 1 |
1 0 4 0 3 9 1 |
Εξήγηση παραδείγματος: Οι χαρούμενοι αριθμοί μέχρι το \(50\) είναι οι \(1\), \(7\), \(10\), \(13\), \(19\), \(23\), \(28\), \(31\), \(32\), \(44\), \(49\).
Περιορισμοί
- \(1 \leq K \leq 1.000\).
- \(0 \leq A \leq B \leq 1.000.000.000\).
- Όριο χρόνου εκτέλεσης: \(1\) sec.
- Όριο μνήμης: \(64\) MB.