trang chủ / đề bài / icpcwf24_k

Tháp Nội Hà

Đề bài

Mô tả

Lucas tin rằng cậu con trai sáu tuổi của mình đã sẵn sàng học vài thuật toán cơ bản. Để bắt đầu, anh chọn một trong những kỹ thuật đẹp nhất: đệ quy, và để minh hoạ, anh chọn trò chơi đệ quy nổi tiếng: Tháp Hà Nội.

Tháp Hà Nội là một trò chơi toán học gồm ba cọc và một số đĩa có đường kính khác nhau, các đĩa có thể trượt vào bất kỳ cọc nào. Lúc bắt đầu, các đĩa được xếp chồng trên cọc thứ nhất theo thứ tự kích thước, đĩa nhỏ nhất ở trên cùng, tạo thành gần giống một hình nón. Mục tiêu của trò chơi là chuyển toàn bộ chồng đĩa sang cọc cuối cùng, tuân theo các quy tắc sau:

  • Mỗi lần chỉ được di chuyển một đĩa.
  • Mỗi bước di chuyển là lấy đĩa trên cùng của một cọc và đặt nó lên trên cùng của một cọc khác hoặc lên một cọc trống.
  • Không được đặt một đĩa lên trên một đĩa nhỏ hơn nó.

Lucas biết rằng số bước tối thiểu để giải trò chơi Tháp Hà Nội là 2n−1, với n là số đĩa. Hơn nữa, dãy bước tối ưu là duy nhất, nghĩa là n cùng với số bước đã thực hiện xác định duy nhất trạng thái hiện tại của trò chơi, với điều kiện các đĩa luôn được di chuyển một cách tối ưu.

Lucas đang chỉ cho con trai cách giải trò chơi từng bước một. Anh đã thực hiện k bước tối ưu đầu tiên. Vì vẫn còn lâu mới xong, anh nghỉ một chút để đi lấy đồ ăn vặt. Không may, khi anh quay lại, cậu con trai nghịch ngợm đã thực hiện một "bước" lớn: biết rằng mục tiêu là chuyển mọi đĩa từ cọc thứ nhất sang cọc cuối cùng, cậu bé đã chuyển đúng theo nghĩa đen "mọi đĩa từ cọc thứ nhất sang cọc cuối cùng" chỉ trong một bước: nhấc nguyên chồng đĩa đang có trên cọc thứ nhất và đặt lên trên cùng của cọc cuối cùng (giữ nguyên thứ tự của chúng).

Ví dụ với n=5 đĩa (đánh số 1 đến 5 theo kích thước tăng dần) và k=2: trước bước lớn, cọc thứ nhất có các đĩa 5,4,3 (từ dưới lên), cọc thứ hai có đĩa 2, cọc cuối cùng có đĩa 1. Sau bước lớn, cọc thứ nhất trống, cọc thứ hai vẫn có đĩa 2, còn cọc cuối cùng có các đĩa 1,5,4,3 (từ dưới lên).

Lucas tin rằng anh vẫn có thể biến chuyện này thành một bài học. Anh quyết định tiếp tục giải trò chơi nhưng chỉ dùng các bước "hợp lệ". Tuy nhiên, anh tự hỏi bây giờ cần tối thiểu bao nhiêu bước để giải xong trò chơi. Vì còn bận trông con, anh cần bạn giúp!

Lưu ý rằng một bước "hợp lệ" vẫn được định nghĩa rõ ràng ngay cả khi trạng thái hiện tại không hợp lệ: mỗi lần chỉ được di chuyển một đĩa trên cùng, và không được đặt nó lên trên một đĩa nhỏ hơn nó. Đặc biệt, được phép đặt một đĩa kích thước a lên một cọc có chứa đĩa kích thước b (b<a) nếu đĩa trên cùng của cọc đó có kích thước c với a<c.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên n (1≤n≤200000), số đĩa của trò chơi.

Dòng thứ hai chứa số nguyên k (0≤k≤2n−1), số bước tối ưu Lucas đã thực hiện trước bước lớn. Lưu ý rằng k được cho ở hệ nhị phân.

Dữ liệu ra

In ra một số nguyên ở hệ nhị phân: số bước tối thiểu cần thực hiện để giải xong trò chơi.

Ràng buộc

  • 1≤n≤200000.
  • 0≤k≤2n−1, k được viết ở hệ nhị phân không có chữ số 0 thừa ở đầu.

Ví dụ

Input Output Giải thích
3
0
0 Chưa có bước nào, cả 3 đĩa nằm ở cọc thứ nhất; bước lớn chuyển nguyên chồng sang cọc cuối, trò chơi đã xong.
3
10
110 k=2: trước bước lớn, cọc thứ nhất có đĩa 3, cọc thứ hai có đĩa 2, cọc cuối có đĩa 1. Sau bước lớn, cọc cuối có các đĩa 1,3 (từ dưới lên). Cần 6 bước.
5
11011
11 k=27: cần 3 bước.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0