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

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
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

3
7
19
12

Sample output
7
4
1

Bình luận


  • 1
    blinh    4:33 p.m. 31 Tháng 7, 2024 ← chỉnh sửa 4
    hint


    • -1
      Avocadorable    8:01 p.m. 19 Tháng 4, 2024 
      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))

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

        memory bé quá admin ơi!

        2 phản hồi