A lift without fours
In a tall building the floors are numbered in a row, but numbers containing the digit 4 or the digits 1 and 3 next to each other are skipped: 12 is followed by 15, 112 by 115, and 130–139 do not exist at all. The first floor is 1. For each query N, say what number is written on the button of the N-th floor in order.
Input
The first line holds q (1 ≤ q ≤ 10⁵), then q numbers N (1 ≤ N ≤ 10¹⁵), one per line.
Output
For each query, the number on the button, on a separate line. It is less than 10¹⁶.
Examples
Example 1
6 1 3 4 12 13 100
1 3 5 15 16 123
Example 2
4 10 11 30 31
11 12 35 36
Limits
- Time · Python
- 7000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 7 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
How many good numbers are there among all strings of L digits? It depends only on L and on whether a one stood before them.
2Hint 2
Knowing how many good numbers begin with 0, with 1, with 2, …, you can choose the first digit of the N-th one: skip whole batches until N lands inside one. Then the same with the next digit.
3The idea
Digit DP with a descent. f[L][s] is how many strings of L digits have no fours and no “13”, given that a one stood before them (s = 1) or not (s = 0). Leading zeros do no harm: strings of length L are the numbers from 0 to 10L − 1, and such a string contains a forbidden combination exactly when the number itself does.
4Walkthrough
Number the good numbers from zero: 0 is number 0, 1 is number 1, … Then the answer is the good number with index N. The length L is the smallest for which f[L][0] > N. Then position by position: go through the digits in increasing order, except 4 and except 3 after a one; if the batch with this digit (f[remaining][whether it is a one]) is no larger than the remaining index, subtract it and go to the next digit, otherwise put this digit.
4+Solution
5Complexity
The table is 20 × 2 numbers. A query is at most 17 positions of 10 digits.
6Common mistakes
- Counting floors one by one. This is
wrong.py: it still gets to the millionth floor, but there are a hundred thousand queries, and in the fourth test time runs out, while floor number 10¹⁵ has sixteen digits. - Forgetting “13” at the joint. The state “was there a one” is needed both for the digit being placed and for the first digit of the batch after it: 113 is forbidden, although neither 11 nor 3 is bad on its own.
- Numbering from one. Zero among the good numbers has index 0; counting from one shifts the answer by one floor.
- Binary search on the answer is also correct, but it is 50 passes over the digits per query instead of one descent; in Python with a hundred thousand queries this is noticeable.