summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-02-20 09:40:31 -0700
committerJack Sangdahl <[email protected]>2025-02-20 09:40:31 -0700
commit91491fa92ae64f36e8277849d0943d20b82093bc (patch)
treea10a045d910f43413cf32f2ce253c35cd93652a0
parent5b765ce70d76f1c3e56b24694c832bd938d33816 (diff)
downloadcses-91491fa92ae64f36e8277849d0943d20b82093bc.tar.gz
cses-91491fa92ae64f36e8277849d0943d20b82093bc.zip
2431. digit queries
-rw-r--r--introductory_problems/digit_queries.cpp32
-rw-r--r--introductory_problems/readme.md7
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)