https://oj.luyencode.net/problem/HNX

[utterances-bot]

Tháp Hà Nội Xuôi - Luyện Code Online

https://oj.luyencode.net/problem/HNX

[giabaophudinhthcs]

Cho mình xin hướng dẫn bài này được không ạ. Mình cảm ơn ạ.

[giabaophudinhthcs]

Dạ cho mình xin chia sẻ lời giải cho bài này ạ. Khoảng 7 tháng trước thì mình có xin lời giải cho bài này, nhưng giờ mình đã AC bài này rồi nên mình chia sẻ lời giải cho những bạn còn làm bài này hoặc đang xem mà chưa hiểu bài này và làm chưa được ạ. Đầu tiên, đối với những bạn chưa biết về trò chơi Tháp Hà Nội thì mình giới thiệu sơ qua như sau: trò chơi này ta có n đĩa và 3 cột (mình quy ước 3 cột đó là A, B, C), n đĩa này có kích thước khác nhau và chúng xếp ở cột A với điều kiện là đĩa nhỏ hơn thì nằm ở trên. Mỗi lần ta chuyển 1 đĩa từ cột hiện tại sang cột khác sao cho thỏa điều kiện đĩa nhỏ hơn thì nằm ở trên. Mục tiêu của trò chơi này là chuyển hết n đĩa này từ cột A sang cột C. Trước khi mình hướng dẫn bài này (bài HNX) thì mình sẽ chỉ cách chơi trò này - cũng là cách tốt nhất và rất đơn giản: Khi ta cần chuyển x đĩa từ cột đầu sang cột đích: B1: Chuyển x-1 đĩa từ cột đầu sang cột trung gian. B2: Chuyển đĩa thứ x từ cột đầu sang cột đích. B3: Chuyển x-1 đĩa từ cột trung gian sang cột đích. Sau khi nắm được cách để chơi trò này thì ta xét bài toán HNCO. Link: https://oj.luyencode.net/problem/HNCO Ở bài này thì yêu cầu đếm số bước ít nhất để chuyển hết n đĩa từ cột A sang cột C. Ta nhận thấy rằng để chuyển x đĩa từ cột ban đầu bất kỳ sang cột đích nào đó đều có cùng cách thực hiện nên số bước để chuyển đĩa sẽ như nhau. Cho nên ta sẽ có cách giải quy hoạch động như sau: (các bạn có thể tham khảo về quy hoạch động trên vnoi wiki hoặc trên geeksforgeek, mình không tiện giải thích ở đây vì quy hoạch động khá dài và mình sợ mất thời gian nên mn thông cảm nhé). Ta gọi số cách chuyển x đĩa từ cột hiện tại sang một cột nào đó là dp[x]. Khi đó để chuyển 1 đĩa thì ta có dp[1] = 1. Ta nhìn vào cách chuyển ở phía trên thì ta thu được dp[x] = 2dp[x-1] + 1. Cho nên ta chỉ cần 1 vòng lặp để duyệt và tính từ dp[1] đến dp[n], kết quả là dp[n]. Độ phức tạp là O(n). Các bạn tự tham khảo thêm về độ phức tạp về thời gian luôn nhé tại vì định nghĩa này cũng khá dài dòng. Xét về độ phức tạp O(n) với n <= 500, đối với vòng lặp thì trong 1s trung bình chạy khoảng từ 310^7 cho đến 10^8 phép tính. Nhưng tốt nhất là khoảng 310^7 cho đến 510^7 nhé. Khi đó với giới hạn trong bài là 5ms thì số lượng phép tính tối đa lúc này là từ 150000 cho đến tầm 500000. Do đó với n <= 500 và độ phức tạp thời gian là O(n) thì quá là lý tưởng! (Mặc dù lâu lâu trình chấm troll một số test rằng mặc dù dưới 5ms nhưng bị TLE =))))) cho nên cứ nộp lại bài thôi). Nhưng nhớ là mod cho 10^9 + 7 nhé. Nhưng nếu muốn tối ưu thì ta thấy rằng dp[x] = 2*dp[x-1] + 1 và dp[1] = 1 là 1 dãy truy hồi. Nếu các bạn tìm công thức tổng quát này bằng phương pháp phân sai thì ta có dp[x] = 2^x - 1. Vậy đáp án là (2^x - 1) % (10^9 + 7). Phần lũy thừa thì ta dùng luỹ thừa Ấn Độ để giảm độ phức tạp thời gian còn O(log2(n)) (nhanh hơn so với cách trên) Ta quay lại bài HNX. Ta định nghĩa cột x “kề” với cột y là khi mà chuyển 1 đĩa ở trên cùng từ cột x có thể chuyển qua cột y chỉ trong 1 bước. Khi đó với cách di chuyển các đĩa như đề bài thì cột y sẽ không “kề” với cột x. Theo đề bài thì ta có A kề với B, B kề với C, C kề với A, B ko kề với A, C ko kề với B và A ko kề với C. Ta chia ra 2 trường hợp trong khi chuyển x đĩa từ cột m sang cột n: Gọi o là cột trung gian. TH1: cột m kề với cột n: (như trong trò chơi Tháp Hà Nội cổ điển mà mình có nói) B1: chuyển x-1 đĩa từ cột m sang cột o. B2: chuyển đĩa thứ x từ cột m sang n. B3: chuyển x-1 đĩa từ cột o sang cột n. TH2: cột m không kề với cột n: B1: chuyển x-1 đĩa từ cột m sang cột n. B2: chuyển đĩa thứ x từ cột m sang cột o. B3: chuyển x-1 đĩa từ cột n sang cột m. B4: chuyển đĩa thứ x từ cột o sang cột n. B5: chuyển x-1 đĩa từ cột m sang cột n.

[giabaophudinhthcs]

Khi đó ta thấy rằng trường hợp cột kề cột và cột không kề cột khác nhau về phương pháp chuyển đĩa -> số bước cũng khác nhau. Do đó ta có cách giải quy hoạch động như sau: gọi số cách chuyển x đĩa từ cột hiện tại sang một cột nào đó là dp[i][x], trong đó: i = 0: TH cột ban đầu kề kề với cột đích. i = 1: TH cột ban đầu không kề kề với cột đích. Khi đó ta có: dp[0][1] = 1; dp[0][x] = dp[1][x-1] + dp[1][x-1] + 1 dp[1][1] = 2; dp[1][x] = dp[1][x-1] + dp[1][x-1] + 2 + dp[0][x-1] Nhớ mod cho 10^9 + 7 Đáp án là dp[0][n]. Độ phức tạp: O(n) Với n <= 10^4 dư sức dưới 5ms. Chú ý là có thể bị troll nhé :))) Code AC để tham khảo; https://github.com/giabaophudinhthcs/CodingProblem/blob/main/HNX.cpp Phù... Vậy là luyencode.net sắp phải ngừng hoạt động rồi, cũng khá buồn nhỉ. Một hành trình sắp kết thúc và những hành trình khác lại bắt đầu ở các online judge khác. Nhưng mình cũng mong rằng các bạn sẽ vẫn luôn cố gắng hết mình để thành công trong sự nghiệp coding nhé. Chào các bạn! Chúc các bạn buổi tối vui vẻ.