Cho 1 dãy tăng vô hạn tìm chữ số tại vị trí k

#1

mn cho mình ý tưởng làm bài này vợi ạ

#2

Từ 1 đến 9, 99, 999, … có bao nhiêu chữ số?

3 Likes
#3

9 * pow(10,i-1) i là chữ số

#4

b có ý tưởng nào ko nói luôn cho mình biết với

#5 
 123...89|101112...9899|100101102...998999|10001001...9999|...
 9 chữ số  2*90 chữ số   3*(999-100+1) cs   4*(9999-1000+1)
    9cs        180cs        2700cs            36000cs
0       9           189               2889           38889

từ 0 tới 9 có 9 chữ số
từ 0 tới 99 có 189 chữ số
từ 0 tới 999 có 2889 chữ số
từ 0 tới 9999 có 38889 chữ số

bây giờ cho k = 3000, thấy ngay số ở vị trí k phải là số có 4 chữ số (999 < x <= 9999) vì 2889 < k < 38889. Biết là số có 4 chữ số rồi thì tìm dễ dàng. Ví dụ số 1000 sẽ có vị trí thứ 2890 tới 2893, số 1001 có vị trí 2894 tới 2897 vậy số ở vị trí 3000 lấy 3000 - (2889 + 1) = 110 rồi lấy 110 chia 4 lấy phần nguyên = 27, tức là số 1027 sẽ chiếm vị trí 3000. Số nào trong 1027 thì lấy 110 chia 4 lấy phần dư là 2, tức là 10[2]7 là số 2 :V

vd

  • k = \bold{5}, k nằm trong khoảng (\textcolor{red}0, 9], là khoảng chứa số có \textcolor{grey}1 chữ số và bắt đầu bằng số \textcolor{magenta}1, lấy \bold{5} - (\textcolor{red}0 + 1) = \textcolor{green}4, lấy \textcolor{green}4 chia \textcolor{grey}1 = \textcolor{blue}4 dư \textcolor{gold}0, vậy đó là chữ số ở index \textcolor{gold}0 của số \textcolor{magenta}1 + \textcolor{blue}4 = 5, là chữ số \boxed{5}
  • k = \bold{10}, k nằm trong khoảng (\textcolor{red}9, 189], là khoảng chứa số có \textcolor{grey}2 chữ số và bắt đầu bằng số \textcolor{magenta}{10}, lấy \bold{10} - (\textcolor{red}9 + 1) = \textcolor{green}0, lấy \textcolor{green}0 chia \textcolor{grey}2 = \textcolor{blue}0 dư \textcolor{gold}0, vậy đó là chữ số ở index \textcolor{gold}0 của số \textcolor{magenta}{10} + \textcolor{blue}0 = 10, là chữ số \boxed{1}
  • k = \bold{54}, k nằm trong khoảng (\textcolor{red}9, 189], là khoảng chứa số có \textcolor{grey}2 chữ số và bắt đầu bằng số \textcolor{magenta}{10}, lấy \bold{54} - (\textcolor{red}9 + 1) = \textcolor{green}{44}, lấy \textcolor{green}{44} chia \textcolor{grey}2 = \textcolor{blue}{22} dư \textcolor{gold}0, vậy đó là chữ số ở index \textcolor{gold}0 của số \textcolor{magenta}{10} + \textcolor{blue}{22} = 32, là chữ số \boxed{3}

edit cho màu mè hơn =]]

5 Likes
#6

ôi cảm ơn b , b giải thích rõ lắm mình đã hiêu ý tưởng làm bài rồi

1 Like
#7

số ở vị trí 3000 lấy 3000 - (2889 + 1) = 110 rồi lấy 110 chia 4 lấy phần nguyên = 27, tức là số 1027 sẽ chiếm vị trí 3000
vậy là số 1 ở vị trí 2998 , 0 ở vị trí 2999 , 2 ở vị trí 3000 , 7 ở vị trí 3001 đúng ko ạ

#8

ờm :V

viết chương trình tạo chuỗi s tới n = 1100 rồi kiểm tra s[3000-1] gì cho chắc =]

1 Like
#9

số ở vị trí 3000 lấy 3000 - (2889 + 1) = 110 rồi lấy 110 chia 4 lấy phần nguyên = 27, tức là số 1027 sẽ chiếm vị trí 3000
110 là tổng số chữ số từ vị trí bắt đầu của số có 4 chữ số đến chữ số đang cần tìm nên muốn biết số đó thì lấy 110 / 4 = 27 ==> số có chứa vị trí k = 3000 là 1000 + 27 = 1027 đúng ko ạ

#10

là sao ô , ô có thể ghi rõ đc ko

#11

ví dụ cho hàm index(k) thì viết 1 hàm tạo chuỗi ví dụ

s = empty string
for i = 1 to 10000  do s = s + to_string(i)

rồi check s[k-1] == index(k) là được :V s[k-1] là vì s bắt đầu ở index 0 còn bài toán cho là từ index 1 :V

vd python nè:

s = ''
for i in range(1, 10001): s += str(i)
print(s[3000-1])        # in ra 2
print(s[2998-1:3002-1]) # in ra 1027
#12

vậy có bị TLE ko nhỉ vì k đề bài cho giới hạn đến 10^9 lận

#13

cái đó là để mình tự kiểm tra logic tính toán của mình có đúng hay ko thôi chứ có phải là code nộp đâu :V :V

3 Likes
#14

à ok tôi đọc thiếu cmt của ô

#16

vô daynhauhoc discord hỏi nè: https://discordapp.com/invite/jHwsRAN

hên xui bài dễ còn có người trả lời còn bài khó thì thôi :innocent:

1 Like
#17

As requested

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?