[C++] [CSES] Digit Queries (Introductory Problems)

CSES의 열 여덟번째 문제입니다.

이렇게 자릿수를 세고 몫 나머지가 어떻고 하는 문제가 간단해 보이지만 굉장히 어려운 것 같습니다.

 

Task

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 11-indexed position in the string.

Output

For each query, print the corresponding digit.

Constraints

• 1≤q≤1000
• 1≤k≤1e18

Example

Input:
3
7
19
12

Output:
7
4
1

 

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll q, k;
ll find(ll k){
    ll ja = 1, num = 9, tmp = 1;
    while (k > ja * num){
        k -= ja * num;
        ja++;
        num *= 10;
        tmp *= 10;
    }
    ll div = (k - 1) / ja;
    ll mod = (k - 1) % ja;
    string cur = to_string(tmp + div);
    return cur[mod] - '0';
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> q;
    while (q--){
        cin >> k;
        cout << find(k) << "\n";
    }
}

생각해야 하는 것

• 자릿수가 같은 수의 개수는 9(1 ~ 9) -- 90(10 ~ 99) -- 900(100 ~ 999) ... 순으로 9에 10을 곱해주는 규칙이 있음을 알 수 있습니다.
• 저는 k를 받았을 때 몇 자릿수의 숫자에서 몇번째인지, 그 수에서 몇번째 숫자인지 구하는 방향으로 함수를 작성했습니다.
• 예를 들어 k = 19인 경우, 19 - 1*9 = 10 < 2*90 이므로 19번째에 있는 수는 10부터 시작하는 두 자릿수 숫자 구간의 어떤 숫자임을 알 수 있습니다.
• 1 0 1 1 1 2 1 3 1 4 1 5 .... 9 9 이 구간(두 자릿수 구간)에서 10번째 수를 구하면 됩니다.
• 10번째 숫자가 4임을 눈으로 알 수 있지만, 그것을 일반화하는 과정은 다음과 같습니다.
• (k - 1) / 자릿수(2) 연산을 하면 ---> 1 0 -- 0, 1 1 -- 1, 1 2 -- 2...의 꼴로 첫 수 + 연산결과를 한 경우에 해당하는 숫자를 알 수 있습니다.
• 예를 들어 (10 - 1) / 2 = 9 / 2 = 4 ---> 10 + 4 = 14라는 숫자 중 어느 한 부분임을 알 수 있습니다.
• 14라는 숫자를 문자열로 바꾼 후 나머지 연산을 하면 (10 - 1) % 2 = 1이므로 "14"[1] = '4'를 구할 수 있습니다.