CSES - Digit Queries | Truy vấn chữ số - LQDOJ: Le Quy Don Online Judge

CSES - Digit Queries | Truy vấn chữ số

Tác giả:

Flower_On_Stone , SPyofgame , CatTuong

Dạng bài

Điểm: 1400 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một xâu dài vô hạn chứa tất cả các số nguyên dương theo trình tự tăng dần:

\(12345678910111213141516171819202122232425 \ldots\)

Nhiệm vụ của bạn là xử lí \(q\) truy vấn trả lời cho câu hỏi: số nào nằm ở vị trí thứ \(k\) trong xâu?

Input

Dòng đầu tiên chứa một số nguyên duy nhất \(q\): số lượng truy vấn.
Sau đó gồm \(q\) dòng tiếp theo biểu diễn các truy vấn, mỗi dòng là một số nguyên \(k\): vị trí của kí tự cần tìm trong xâu (xâu được đánh số từ \(1\)).

Output

Với mỗi truy vấn, in ra kết quả tương ứng trên từng dòng.

Constraints

\(1 \le q \le 1000\)
\(1 \le k \le 10^{18}\)

Example

Sample input

Sample output

7
4
1

Bình luận

def digit_at_position(k):
    d = 1
    while k > d * 9 * 10**(d - 1):
        k -= d * 9 * 10**(d - 1)
        d += 1

    num_offset = (k - 1) // d
    digit_offset = (k - 1) % d

    num = 10**(d - 1) + num_offset

    digit = int(str(num)[digit_offset])

    return digit

q = int(input())
for i in range(q):
    t = int(input())
    print(digit_at_position(t))

5

huyhau6a2 8:18 p.m. 10 Tháng 8, 2022

memory bé quá admin ơi!

2 phản hồi