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.

Code mẫu

#include <bits/stdc++.h>

using namespace std;

#define fo(i, a, b) for(int i = a; i <= b; i++)
#define _fo(i, a, b) for(int i = a; i >= b; i--)
#define foa(i, a) for (auto &i : a)
#define sz(a) ((int) a.size())
#define all(a) begin(a), end(a)
#define fi first
#define se second
#define pb(x) push_back(x)
#define mk(x, y) make_pair(x, y)

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int MAX = (1<<10);
const int LOG = 20;
const int MOD = 1e9+7;
const ll INF = 1e7+5;

int q, k;
int cnt[9], a[9];
int lg[MAX], bcnt[MAX], dist[9], f[MAX];
map<int, int> result;

void precompute() {
    fo(i, 2, MAX-1) lg[i] = lg[i/2]+1;    
    fo(i, 1, MAX-1) bcnt[i] = bcnt[i^(i&-i)]+1;

    int pt = 0, cnt = 0;
    fill(dist, dist+8, 100);
    while(dist[pt] == 100) {
        dist[pt] = cnt;
        pt = (pt+k) % 8;
        cnt++;
    }
}

int solve() {
    int goal = (1<<8)-1;
    fo(i, 1, goal) {
        f[i] = 100;
        int temp = i;
        while(temp > 0) {
            int curr = temp&-temp, d = abs(lg[curr]-a[bcnt[i]]);
            f[i] = min(f[i], f[i^curr]+min(dist[d], dist[8-d]));
            temp -= curr;
        }
    }
    return f[goal];
}

int get(int val) {
    while(val > 0) {
        cnt[val % 10]++;
        val /= 10;
    }
    int nval = 0, p = 0;
    fo(i, 1, 8) {
        while(cnt[i] > 0) {
            p++;
            a[p] = i;
            nval = nval*10+i;
            cnt[i]--;
        }
    }

    if(result.count(nval)) return result[nval];
    int temp = solve();
    if(temp == 100) temp = -1;
    result.insert(mk(nval, temp));
    return temp;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);   
    cin >> q >> k;
    precompute();
    while(q--) {
        int val;
        cin >> val;
        cout << get(val) << "\n";
    }
}