diff options
author | Jack Sangdahl <[email protected]> | 2025-02-20 09:40:31 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-02-20 09:40:31 -0700 |
commit | 91491fa92ae64f36e8277849d0943d20b82093bc (patch) | |
tree | a10a045d910f43413cf32f2ce253c35cd93652a0 | |
parent | 5b765ce70d76f1c3e56b24694c832bd938d33816 (diff) | |
download | cses-91491fa92ae64f36e8277849d0943d20b82093bc.tar.gz cses-91491fa92ae64f36e8277849d0943d20b82093bc.zip |
2431. digit queries
-rw-r--r-- | introductory_problems/digit_queries.cpp | 32 | ||||
-rw-r--r-- | introductory_problems/readme.md | 7 |
2 files changed, 39 insertions, 0 deletions
diff --git a/introductory_problems/digit_queries.cpp b/introductory_problems/digit_queries.cpp new file mode 100644 index 0000000..008d3f5 --- /dev/null +++ b/introductory_problems/digit_queries.cpp @@ -0,0 +1,32 @@ +// 2431. Digit Queries +#include <bits/stdc++.h> +using namespace std; + +long long pow10(int x) { + long long res = 1; + for (int i = 0; i < x; i++) + res *= 10; + return res; +} + +int solve(long long n) { + if (n < 9) + return (int)n + 1; + int len = 1; + while (pow10(len - 1) * len * 9 < n) { + n -= 9 * pow10(len - 1) * len; + len++; + } + string s = to_string(pow10(len - 1) + n / len); + return (int)(s[n % len] - '0'); +} + +int main() { + static int q; + static long long k; + scanf("%d", &q); + for (int i = 0; i < q; i++) { + scanf("%lld", &k); + printf("%d\n", solve(k - 1)); + } +} diff --git a/introductory_problems/readme.md b/introductory_problems/readme.md index 3adac29..0046f00 100644 --- a/introductory_problems/readme.md +++ b/introductory_problems/readme.md @@ -90,3 +90,10 @@ A gray code is a list of `2^n` bit strings of length `n`, where any two successi **Input**: The only input line has an integer `n`. (Example: 2) **Output**: Print `2^n` lines that describes the gray code. You can print any valid solution. (Example: 00 01 11 10) + +### Digit Queries +Consider an infinite string that consists of all positive integers in increasing order: 12345678910111213141516171819202122232425... Your task is to process `q` queries of the form: what is the digit at position `k` in the string? + +**Input**: The first input line has an integer `q`: the number of queries. After this, there are `q` lines that describe the queries. Each line has an integer `k`: a 1-indexed position in the string. (Example: 3 7 19 12) + +**Output**: For each query, print the corresponding digit. (Example: 7 4 1) |