Lucky Numbers and Quiz Answer Sequences

There are two independent tasks in this problem:

Task A. Lucky Numbers

A positive integer is called a lucky number (by Little Blue) if it has an even number of digits and the sum of the first half of the digits is equal to the sum of the last half. For example, 2314 is a lucky number because it has 4 digits and 2+3 = 1+4.

Your task is to count how many lucky numbers exist between 1 and 100,000,000 (inclusive). Note that numbers with an odd number of digits do not satisfy the definition.

Task B. Quiz Answer Sequences

Little Blue is taking part in a live quiz show with 30 questions. For each question, he either answers correctly or incorrectly. A correct answer gives him 10 points while an incorrect answer resets his score to 0. He may decide to stop answering at any moment and claim the prize corresponding to his current score. However, as soon as his score reaches 100 (i.e. after 10 consecutive correct answers) he stops automatically.

It is known that, at the end, Little Blue obtained the prize corresponding to 70 points. Assuming he must answer questions in order (and may stop at any point, even before reaching 100), count the number of distinct ways (answer sequences) he could have proceeded.

Note: For Task B, the score is formed by the number of consecutive correct answers after the most recent wrong answer (or from the beginning if no wrong answer has occurred). In particular, to obtain 70 points the final block of consecutive correct answers must have length exactly 7, and if there is any question before this final block then its last answer must be a wrong (so that the score resets before the 7‐correct streak begins). Also, any sequence in which a block of 10 consecutive correct answers appears is invalid because Little Blue would have automatically stopped at 100 points.

The two answers should be printed on one line separated by a space. The first number is the count for Task A and the second number is the count for Task B.

Formulas:

For Task A, if we consider a number with 2k digits (k = 1, 2, 3, 4), let

[ \text{left}(k, s) = #{(d_1, d_2, \dots, d_k): d_1\in{1,\dots,9},, d_i\in{0,\dots,9} \text{ for } i\ge2, ;\sum_{i=1}^{k} d_i = s} ]

and

[ \text{right}(k, s) = #{(d_1, d_2, \dots, d_k): d_i\in{0,\dots,9}, ;\sum_{i=1}^{k} d_i = s}. ]

Then the number of lucky numbers with 2k digits is

[ L_k = \sum_{s} \Bigl(\text{left}(k, s)\times \text{right}(k, s)\Bigr), ]

and the final answer for Task A is

[ \text{Answer}_A = L_1 + L_2 + L_3 + L_4. ]

For Task B, let A(n) be the total number of valid sequences of length n (answers for some initial questions) that do not contain 10 consecutive correct answers. For n < 10, A(n) = 2^n and for n ≥ 10 the recurrence holds:

[ A(n) = 2,A(n-1) - A(n-11)\quad (n\ge10). ]

Since a valid answer sequence that ends with a wrong answer can always append a wrong answer without danger (resetting the consecutive correct count), the number of sequences of length m that end in a wrong answer is A(m-1) (for m ≥ 1). To obtain a final score of 70, the answer sequence must end with 7 consecutive correct answers and (if m > 0) the answer immediately preceding that streak must be wrong. Therefore the total number of valid answer sequences for Task B is:

[ \text{Answer}B = 1 + \sum{m=1}^{23} A(m-1), , ]

where the 1 accounts for the case when the quiz had exactly 7 questions all answered correctly. (The total number of answered questions cannot exceed 30.)

The output should print the two numbers: <Answer_A> <Answer_B>

inputFormat

This problem does not require any input.

outputFormat

Output two integers separated by a space. The first integer is the number of lucky numbers between 1 and 100,000,000. The second integer is the number of valid quiz answer sequences leading to a final prize corresponding to 70 points.

sample

3284292 8335366