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

Chuỗi giai thừa chữ số

Đếm các số bắt đầu có chuỗi giai thừa chữ số gồm đúng một số lượng phần tử phân biệt cho trước.

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

  • Đi theo chuỗi cho đến khi một giá trị lặp lại
  • Tính độ dài chuỗi bên trong và trước vòng lặp
  • Dùng lại các độ dài đã lưu

Đề bài

Xem bản gốc (English)

Thay một số bằng tổng giai thừa các chữ số của nó: 145 cho 1! + 4! + 5! = 145, vẫn là chính nó, còn 69 cho 6! + 9! = 363600. Lặp lại phép biến đổi này thì sớm muộn cũng rơi vào một vòng lặp. Chuỗi của một số bắt đầu gồm các số hạng cho tới lần lặp lại đầu tiên: 69, 363600, 1454, 169, 363601 rồi lại 1454, nên 69 có 5 số hạng phân biệt. Hãy đếm các số bắt đầu từ 1 đến limit có chuỗi gồm đúng length số hạng phân biệt.

Hãy viết digit_factorial_chains(limit, length).

Nhiều chuỗi đi qua cùng những số giống nhau. Hãy lưu lại độ dài chuỗi của mỗi số khi đã biết và dùng lại.

Đầu vào

limit: Số bắt đầu lớn nhất.

length: Số số hạng phân biệt cần có, tính cả số bắt đầu.

Đầu ra

Trả về số lượng số bắt đầu n với 1 ≤ n ≤ limit có chuỗi gồm đúng length số hạng phân biệt.

Ràng buộc

1 ≤ limit ≤ 100,000; 1 ≤ length ≤ 70

Ví dụ

Ví dụ 1
Đầu vào:
limit = 2
length = 1

Kết quả mong đợi:
expected = 2
Đầu vào:
long long limit = 2;
long long length = 1;

Kết quả mong đợi:
long long expected = 2;
Đầu vào:
long limit = 2;
long length = 1;

Kết quả mong đợi:
long expected = 2;

Giải thích

1! = 1 và 2! = 2, nên 1 và 2 đều biến thành chính nó và có chuỗi 1 số hạng. Đáp án là 2.

Ví dụ 2
Đầu vào:
limit = 10
length = 2

Kết quả mong đợi:
expected = 1
Đầu vào:
long long limit = 10;
long long length = 2;

Kết quả mong đợi:
long long expected = 1;
Đầu vào:
long limit = 10;
long length = 2;

Kết quả mong đợi:
long expected = 1;

Giải thích

3 cho 6, rồi 720, 5043, ... nên chuỗi rất dài. 10 cho 1! + 0! = 2 rồi lại 2: hai số hạng. Chỉ có 10 có đúng 2 số hạng, nên đáp án là 1.

Hướng tiếp cận

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

Gợi ý 1

Tính trước 0! đến 9! một lần.

Gợi ý 2

Ghi lại bước mà mỗi giá trị xuất hiện trong chuỗi hiện tại; khi gặp lại một giá trị, bạn biết vòng lặp bắt đầu ở đâu.

Gợi ý 3

Mọi giá trị trong vòng lặp đều có độ dài bằng độ dài vòng lặp, còn mỗi giá trị đứng trước vòng lặp có độ dài hơn giá trị kế tiếp đúng 1.

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

thời gian O(limit × log limit) khi có ghi nhớ, bộ nhớ phụ O(limit)

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.