PROG0288 - The correct digit
Suppose you would write all successive natural numbers one after the other, starting with the number 1. This would give you an infinite series of digits, that starts as follows (for the sake of clarity we have put spaces in between numbers).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 …
We will not interpret this series as a series of numbers, but as a series of digits. The question that we then try to answer is what digit we will find on a given position $n$. From this example series, it is easy to verify that the sixteenth position holds the digit 1. But what is the digit that we find on position 2147483646 ?
Input
The first line of the input contains a number $t$ ($1 \leq t \leq 1000$) that specifies the number of tasks. After this, each of the $t$ tasks is described. A single task is described by a single line that contains the number $k \in \mathbb{N}_0$ ($1 \leq k \leq 2^{31} - 1$).
Output
For each task, write the $k$-th digit from the series of natural numbers that was described above.
Hint:If you try to generate the series of successive natural numbers with the aim to find the correct digit in it, this approach will be so slow that you'll exceed the time limit set for this programming task for large values of $k$. Try to find a better solution by making use of the observation that the first 9 natural numbers have a single digit, the next 90 natural number have two digits, the next 900 natural numbers have three digits, and so on.
Example
Input:
4 15 2022 1410169200 2147483646
Output:
2 0 1 2
Stel dat je alle opeenvolgende natuurlijke getallen achter elkaar uitschrijft, te beginnen met het getal 1. Dan krijg je een oneindige lange rij, die op de volgende manier begint (voor de duidelijkheid zetten we hierbij spaties tussen de verschillende getallen.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 …
We bekijken deze rij echter niet als een rij van getallen, maar als een rij van cijfers. De vraag die we dan proberen te beantwoorden is wat het cijfer is dat in deze rij voorkomt op positie $n$. Het is bijvoorbeeld makkelijk na te gaan dat het zestiende cijfer in bovenstaande rij het cijfer 1 is. Maar wat is het cijfer op positie 2147483646?
Invoer
De eerste regel van de invoer bevat een getal $t$ ($1 \leq t \leq 1000$) dat het aantal opgaven voorstelt. Daarna volgen $t$ opgaven. Elke opgave wordt beschreven door een regel die een getal $k \in \mathbb{N}_0$ ($1 \leq k \leq 2^{31} - 1$) bevat.
Uitvoer
Schrijf voor elke opgave het $k$-de cijfer uit de rij van de natuurlijke getallen die hierboven wordt beschreven.
Tip: Indien je probeert om de rij van opeenvolgende natuurlijke getallen te genereren om daarin het juiste cijfer op te zoeken, dan zal je zeker de vooropgestelde tijdslimiet overschreiden voor grote waarden van $k$. Probeer daarom een slimmere oplossing te zoeken door gebruik te maken van de observatie dat de eerste 9 getallen bestaan uit 1 cijfer, de volgende 90 getallen uit 2 cijfers, de volgende 900 getallen uit 3 cijfers, enzovoort.
Voorbeeld
Invoer:
4 15 2022 1410169200 2147483646
Uitvoer:
2 0 1 2
| Added by: | Peter Dawyndt |
| Date: | 2012-09-17 |
| Time limit: | 10s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | PY_NBC |
| Resource: | None |
RSS