Subtask 1:

Nếu biểu diễn cách xếp cờ bằng ~1~ chuỗi có ~8~ ký tự như trong đề thì với mọi cách xếp cờ thỏa mãn chuỗi này luôn là ~1~ hoán vị của các số từ ~1 → 8~.

Sinh mọi hoán vị của các số từ ~1 → 8~ rồi đếm số thao tác ít nhất để xếp bàn cờ thành ~1~ trong ~8!~ hoán vị

Độ phức tạp: ~O(8! \times 8 \times q)~.

Subtask 2:

• k = 1

Gọi ~cnt_i~ là số con xe nằm ở hàng ~i~.

Mỗi lượt di chuyển của một con xe tương ứng với chuyển từ ~cnt_i~ sang ~cnt_{i-1}~ hoặc ~cnt_i~ sang ~cnt_{i+1}~ đúng ~1~ đơn vị ( Chú ý nếu ~i=1~ thì chuyển qua trái sẽ là chuyển tới ~cnt_8~, tương tự ~i=8~ chuyển qua phải sẽ là ~cnt_1~ )

Xem các quân xe là cục đá, lúc này, bài toán trở thành cho một vòng tròn có độ dài ~8~, ô thứ ~i~ có ~cnt_i~ cục đá. Mỗi lần có thể chọn ~i~ bất kì, chuyển ~1~ cục đá qua trái hoặc phải của ~i~ trên vòng tròn. Tính số bước ít nhất để ~cnt_i = 1 (1 \leq i \leq 8)~

Giả sử, bài toán ở trên một dãy chứ không phải vòng tròn. Ta sẽ có thuật tham lam như sau:

Nhận xét: để ~cnt_1 = 1~, thì nếu ~cnt_1 = 0~, thì ~cnt_1~ chỉ có thể nhận đá ở những ô bên phải. Nếu ~cnt_1 > 1~ thì phải chuyển đi ~cnt_1 - 1~ cục đá đang ở ô này qua các ô sau.

Từ nhận xét trên, ta duyệt ~i~ từ ~1~ đến ~8~:

• Ta lưu biến ~num~ là tượng trưng cho số đá đang ở ~i~ cần di chuyển. Nếu ~num < 0~ nghĩa là cần chuyển từ phải sang, ngược lại là cần chuyển từ trái sang. Gọi ~ans~ là kết quả, ta có:

~num = num + cnt_i - 1~

~ans = ans + |num|~

Đó là thực hiện trên dãy, còn trên vòng tròn thì sao ?

Với những bài thao tác trên vòng tròn, ta sẽ nghĩ tới việc cắt vòng tròn ra và thực hiện trên một dãy. Ta sẽ duyệt ~i~ từ ~1~ đến ~8~ thể hiện cho mình sẽ không được chuyển qua trái ở thằng ~i~. Và bài toán lại trở thành bài trên dãy, ta sẽ tính và lấy min kết quả.

Độ phức tạp: ~O(Q \times 8^2)~

Subtask 3:

Sử dụng quy hoạch động trạng thái:

Vì bàn cờ tương đối nhỏ, chúng ta có thể sử dụng bitmask để biểu diễn các quân xe, nếu dòng ~i~ có quân xe thì bit thứ ~i = 1~, ngược lại nếu dòng i trống thì bit thứ ~i = 0~.

Gọi ~dp[n][mask]~ là số thao tác tối thiểu để xếp lại ~n~ cột đầu tiên của bàn cờ sao cho:

• Không quân xe nào cùng dòng trong ~n~ cột đầu tiên.
• bitmask biểu diễn ~n~ cột đầu tiên = mask.

Dễ thấy ~n~ bằng số bit bật của mask nên trong thực tế chúng ta có thể vứt chiều này đi, đáp án sau cùng là ~dp[2^8-1]~. Thuật này chạy trong khoảng ≈ ~1024~ phép tính.

Ta tiến hành loại bỏ trường hợp thừa: vì số query lên tới ~1000000~, nếu sử dụng dp bitmask cho mọi query thì không thể đảm bảo chương trình chạy trong ~1~ giây.

• Nhận xét: ~2~ chuỗi biểu diễn bàn cờ mà là hoán vị của nhau thì đáp án luôn giống nhau (ví dụ : ~12121212~ và ~22112211~, ~12345672~ và ~12234567~,...).
• Do mọi chuỗi đều có thể xếp thành một chuỗi không giảm (ví dụ : ~12121212~ thành ~11112222~, ~12345672~ thành ~12234567~,...) nên ta chỉ xét các chuỗi không giảm khác nhau, bằng công thức chia kẹo ta biết có khoảng ~6500~ chuỗi như thế.

Vậy từ các nhận xét trên ta có thể:

• Duy trì ~1~ map ( STL của C++ ) để lưu kết quả của các truy vấn cũ.
• Với mỗi truy vấn, xếp lại chuỗi thành một chuỗi không giảm, gọi chuỗi này là ~S~.
• Nếu ~S~ chưa từng xuất hiện trong map ta chạy dp bitmask rồi nhét kết quả vào map theo dạng key = ~S~ và value = ~dp[2^8-1]~, thao tác này phải chạy tối đa ~6500~ lần.
• Nếu ~S~ đã từng xuất hiện, ta lấy value kết quả tương ứng với key = ~S~ trong thời gian tối đa là ~\log_2{(6500)}~.

Độ phức tạp: ~O(6500 \times 1024 + \log_2{(6500)} \times q)~.

Sử dụng tham lam:

• k ~\leq~ ~10^9~

Xét các ô từ ~0~ đến ~7~

Nhận thấy từ phần tử ~i~ thì ta sẽ đi được tới ~(i + k) \% 8~, ~(i + 2 * k) \% 8~, ~\dots~, cho tới khi quay lại ô ~i~.

Ta sẽ tách các dãy như trên ra thành một số dãy độc lập với nhau. Và mỗi dãy làm thuật giống với với subtask 2: k = 1.

Lưu ý:

• Để tăng tốc độ xử lý, vì mọi chuỗi có ~8~ ký tự trong khoảng từ ~1 → 8~, bạn nên chuyển chúng về dạng int trước khi lưu vào map.
• Bài toán có thể AC hoàn toàn bằng tham lam, quy hoạch động, BFS và meet in the middle.