Giúp ý tưởng bài tập đếm số lượng số có k chữ số liên tiếp giống nhau

This post was flagged by the community and is temporarily hidden.

Dùng for a đến b
Mỗi vòng lặp thì kiểm tra và ghi nhận kết quả thôi
Số thú vị là số có k chữ số liên tiếp giống nhau, kiểm tra bằng cách đếm thôi

3 Likes

làm vậy ko chạy đc từ 1->10^9

Hm, đề bài chỉ nói trong khoảng từ 1 tới 109 thôi mà cậu? :smile:

2 Likes

10^9 đấy bạn. Mình ko bt có cách nào tối ưu hơn hơn ko

10^9 vẫn trong range của int cậu ạ. Mặt khác, tớ không nghĩ việc duyệt như vậy tốn quá nhiều thời gian đâu.
Sao cậu không thử code đơn giản như @kisuluoibieng đã chỉ trước, và chạy thử xem có mất tới vài giây không? :smile: (đừng in gì ra màn hình trong vòng lặp nhé cậu, chỉ in vào file thôi).

4 Likes

minh code đơn giản như @kisuluoibieng nx vẫn ko chạy đc test lớn

1 Like

Mình nhìn qua đề bài thì thấy bài này không thể đếm bằng cách duyệt thông thường mà phải sử dụng quy hoạch động để đếm.

Bạn đã học dạng bài quy hoạch động chữ số chưa?

3 Likes

mình học quy hoạch động rồi
Mong bạn giúp m xin idea

Mình nói quy hoạch động chữ số, không phải quy hoạch động nói chung.

Gọi f(pos, eq_high, eq_low, digit_freq) đếm số lượng số thoả mãn trong khoảng [a, b]. Nói đến đây nếu bạn thấy quen thuộc thì đáp án chính là f(0, 1, 1, {}).

Mình đoán đây là 1 bài cấp tỉnh hoặc chọn đội tuyển HSGQG, có phải không? :smile:

3 Likes

ko phải đâu đây là bài tập chuyên thôi. Bạn có thể nói roz thuật toán hơn ko. Mình chx từng gặp quy hoạch động chữ số này

chúc mừng bạn, đây là kết quả mình mong đợi, mắc dù đoạn code này có hơi cồng kềnh nhưng đó cũng không phải là vấn đề

đoạn code trên, hiển nhiên sẽ bị timeout khi a và b cách nhau lên tới 1 tỷ, tuy nhiên, muốn tiến bộ thì phải tự cảm nhận được cái chưa tốt của mình, nên mình vẫn khuyên các bạn làm với giải pháp “cùi bắp nhất”

trở lại với vấn đề tối ưu bài này.
đếm từng số không được thì mình đếm hàng loạt. cùng phân tích một chút với một bộ
a = 678, b = 123456799, k = 5

ta viết lại như sau
a = 000000678 // cũng không có gì, chỉ là thêm padding cho nó bằng số chữ số với b
b = 144444799
k = 5

với k = 5, thì số thú vị phải sẽ chứa các số 00000 hoặc 11111 hoặc …
như vậy, gắn thêm đầu với đuôi bất kì (kể cả 0 chữ số) thì nó đều sẽ là số thú vị

để xét thử trong tất cả số có 8 chữ số thì sẽ có bao nhiêu số thú vị, với k = 5, thì chúng ta còn lại 3 vị trí để gắn 3 số bất kì (mà không chen và 5 chữ số k liên tục)
tạm viết là như thế này xkkkkky (x và y có thể gồm từ 0 đến 3 chữ số)
như vậy số lượng chữ số của x/y có thể rơi vào trường hợp 0/3 1/2 2/1 3/0

  • trương hợp 0 - 3: kkkkk yyy, (viết cách ra cho dễ nhìn)
    k: có 9 case (11111, 22222, …, 99999, loại 00000 vì k đứng trước)
    y: 1000c ase (từ 000 đến 999)
    tổng số case: 9 * 1000 = 9000

  • trường hợp 1 - 2: x kkkkkk yy
    x: 9 trương họp (1 - 9, loại trường hợp x = 0 vì nó đứng trước, số 0 ở đầu chữ số không ý nghĩa)
    k: 10 trường hợp (00000, 11111…99999)
    y: 2 chữ số, 100 trường hợp
    tổng số case: 910100 = 9000

  • trường hợp 2 - 1: xx kkkkk y
    x: 90 case (chạy từ 10 -> 99, nó phải đảm bảo được là có 2 chữ số)
    k: vẫn là 10 case
    y: 10 case
    kết quả: 90 * 10 * 10 = 9000 (ồ, nó vẫn là 9000)

  • trường hợp 3 - 0: xxx kkkkk
    x: 900 trường hợp (100 - > 999)
    k: vẫn là 10
    kết quả: vẫn là 9000

oh, I see something…
số case nó bằng nhau, và nó là 910^(d - k)(d-k+1), với d là số lượng chữ số của số đang xét (ví dụ trên là xét tất cả số có 8 chữ số, nên d = 8)

gắn vô bài này 9 * 10^(8-5) * (8-5+1) = 9 * 10^3 * 4 = 3600

bạn tự nghĩ các case còn lại
và case mà không đủ , ví dụ như ở trên, xét số 9 chữ số thì chỉ xét
100000000 -> 144444799 (chứ không xét tới 999999999)
đoạn này chịu khó suy nghĩ để đưa ra công thức hợp lý, hoặc đếm với ý tưởng tương tự (cũng theo cách có biến đổi để ra công thức chứ không for như trên nhé)

5 Likes

Bài tập chuyên thì cũng như vậy thôi bạn à :stuck_out_tongue:

Bước đầu tiên luôn là chèn thêm các chữ số 0 vào đầu số a để cho 2 số có các chữ số bằng nhau.

Tiếp tục với bước khai báo hàm f trên:

  • pos là vị trí chữ số đang xét (0-based index)

  • eq_low là 1 biến bool kiểm tra xem các chữ số đã tạo trước đó của x có bằng với cận dưới (= a) hay không. Ví dụ, ta đã tạo được x = 123xxxx, a = 1234494, pos = 3 thì eq_low = true.

  • eq_high là 1 biến bool kiểm tra xem các chữ số đã tạo trước đó của x có bằng với cận trên hay không, tương tự như eq_high.

  • digit_freq là 1 mảng đánh dấu các chữ số & số lượng liên tiếp. Ví dụ, digit_freq = {(3, 2), (1, 2)} thì số đã tạo được là 3311. Ta cần mảng này vì ta cần cẩn thận với trường hợp {(1, 2), (3, k), (2, 1), (4, k)} - đây cũng là 1 khả năng hợp lệ để đếm.

Các khả năng cho chữ số d ở vị trí pos nằm trong đoạn [low, high].

  • nếu eq_low = true -> low = a[pos], ngược lại low = 0.
  • nếu eq_high = true -> high = b[pos], ngược lại high = 9.

Suy ra giá trị eq_low mới và eq_high mới phụ thuộc vào giá trị eq_low, eq_high cũ và low, high hiện tại.

Xét tiếp digit_freq. Ta kết nạp thêm chữ số d mới bằng cách xét giá trị cuối cùng có bằng d hay không.

  • Nếu có thì tăng số lượng đếm của d trong digit_freq thêm 1.
  • Nếu không thì thêm 1 cặp (d, 1) vào digit_freq.

Vậy tại mỗi bước pos ta có

f(pos, eq\_low, eq\_high, digit\_freq) = \sum_{d=low}^{high} f(pos+1, eq\_low', eq\_high', digit\_freq')

Đây là bước đầu cho 1 bài quy hoạch động chữ số cơ bản. Các bước tiếp theo là tối ưu bộ nhớ. Ta còn cần suy nghĩ thêm nên lưu digit_freq ở dạng gì để phục vụ bước lưu lại trạng thái (pos, eq_low, eq_high, digit_freq) để giảm thiểu thời gian đệ quy. Bước lưu lại trạng thái mới thực sự là quy hoạch động.

Gợi ý: a, b \le 10^9 nên a, b chỉ có tối đa 10 chữ số. Nếu ta xét riêng trường hợp n = 10^9 (không đếm trường hợp 10^9 qua hàm f), vậy digit_freq có tối đa bao nhiêu phần tử và mỗi phần tử có giá trị tối đa là bao nhiêu?

4 Likes

Câu hỏi cho bạn chủ thớt:

4 Likes

b có thể cho mình xin file bt đc kh

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