Tất cả thử thách
Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Chữ số của dãy Champernowne

Tìm chữ số ở các vị trí cho trước trong chuỗi 123456789101112... tạo bằng cách viết liền các số tự nhiên.

Bạn sẽ học được gì

  • Đếm số chữ số mà các số mỗi độ dài chiếm
  • Xác định số và chữ số từ một vị trí
  • Dùng số học 64 bit an toàn

Đề bài

Xem bản gốc (English)

Viết các số nguyên dương nối tiếp nhau: 123456789101112131415... Vị trí 1 là chữ số 1, vị trí 10 là chữ số 1 của số 10, vị trí 11 là chữ số 0 của số 10. Với mỗi vị trí được hỏi, hãy tìm chữ số ở đó. Các vị trí lớn hơn rất nhiều so với một chuỗi bạn có thể dựng được, nên hãy bỏ qua cả khối những số có cùng số chữ số (9 số có một chữ số, 90 số có hai chữ số, 900 số có ba chữ số, ...).

Hãy viết champernowne_digits(positions).

Đầu vào

positions: Các vị trí trong chuỗi chữ số, đếm từ 1.

Đầu ra

Trả về chữ số ở từng vị trí, theo đúng thứ tự của đầu vào. Đầu vào rỗng thì trả về danh sách rỗng.

Ràng buộc

0 ≤ positions.length ≤ 100; 1 ≤ position ≤ 10^15

Ví dụ

Ví dụ 1
Đầu vào:
positions = [1, 9, 10, 11]

Kết quả mong đợi:
expected = [1, 9, 1, 0]
Đầu vào:
std::vector<long long> positions = {1, 9, 10, 11};

Kết quả mong đợi:
std::vector<long long> expected = {1, 9, 1, 0};
Đầu vào:
long[] positions = new long[] {1, 9, 10, 11};

Kết quả mong đợi:
long[] expected = new long[] {1, 9, 1, 0};

Giải thích

Chuỗi bắt đầu bằng 1 2 3 4 5 6 7 8 9 1 0 1 1, nên các chữ số là [1, 9, 1, 0].

Ví dụ 2
Đầu vào:
positions = [15, 190]

Kết quả mong đợi:
expected = [2, 1]
Đầu vào:
std::vector<long long> positions = {15, 190};

Kết quả mong đợi:
std::vector<long long> expected = {2, 1};
Đầu vào:
long[] positions = new long[] {15, 190};

Kết quả mong đợi:
long[] expected = new long[] {2, 1};

Giải thích

Vị trí 15 là chữ số 2 của số 12. Các vị trí từ 10 đến 189 chứa các số từ 10 đến 99, nên vị trí 190 là chữ số đầu tiên của 100: [2, 1].

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Các số có d chữ số chiếm tổng cộng 9 × 10^(d − 1) × d vị trí.

Gợi ý 2

Trừ dần cả khối cho đến khi vị trí rơi vào bên trong một khối.

Gợi ý 3

Trong khối đó, (position − 1) / d cho biết là số nào và (position − 1) % d cho biết là chữ số nào.

Độ phức tạp mong đợi

thời gian O(m × log P) với m vị trí, bộ nhớ phụ O(m)

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.