Subtask 1:

Với giới hạn rất bé, ta có thể sinh tam phân hoặc quay lui. Nếu ta có thể rút gọn vòng duyệt ở cuối mỗi lần sinh hoặc đệ quy quay lui thì sẽ AC.

Đpt: ~O(3^n×t)~.

Subtask 2:

Ta sẽ duyệt hết các trường hợp xảy ra. Ban đầu, ta sẽ lấy ~k=a_2-a_1~. Xét các trường hợp như sau:

• ~a_1~ tăng, ~a_2~ giảm ~\rightarrow~ ~k'=(a_2-1)-(a_1+1)=a_2-a_1-2=k-2~.
• ~a_1~ tăng, ~a_2~ giữ nguyên ~\rightarrow~ ~k'=(a_2 )-(a_1+1)=a_2-a_1-1=k-1~.
• ~a_1~ tăng, ~a_2~ tăng ~\rightarrow~ ~k'=(a_2 )-(a_1 )=a_2-a_1=k~.
• ~a_1~ giảm, ~a_2~ tăng ~\rightarrow~ ~k'=(a_2+1)-(a_1-1)=a_2-a_1+2=k+2~.
• ~a_1~ giữ nguyên, ~a_2~ tăng ~\rightarrow~ ~k'=(a_2+1)-(a_1 )=a_2-a_1+1=k+1~.

…

Tất cả có ~9~ trường hợp, và thấy rằng, giá trị ~k~ cần tìm để hoàn thành dãy của ta chỉ có thể là một trong ~5~ số ~k-2, k-1, k, k+1, k+2~. Do đó, ta sẽ có thuật toán cho bài này là:

• Duyệt hết các giá trị k có thể có của dãy.
• Từ công thức ~a_i=a_(i-1)+k~, ta có thể suy ra được các giá trị ~a_2,…,a_n~ nếu biết ~2~ giá trị ~a_1~ và ~k~. Do đó, trong với mỗi giá trị ~k~, ta sẽ duyệt tất cả các giá trị ~a_1~ có thể có là ~a_1-1,a_1~, ~a_1+1~. Từ đó, ta có thể suy ra các giá trị tiếp theo, và kiểm tra xem chúng có thỏa mãn thao tác không, và đếm.

Đpt: ~O(n×t)~.

Code tham khảo

#include <bits/stdc++.h>
using namespace std;

#define task "dayso"

const int MAXN = 1e5 + 7;
const int INF = 1e9 + 7;

int T, N;
int A[MAXN];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    freopen(task".inp", "r", stdin);
    freopen(task".out", "w", stdout);

    cin >> T;

    while(T--){
        cin >> N;
        for(int i = 1; i <= N; i++)
            cin >> A[i];

        int temp = A[2] - A[1];
        int ans = INF;

        for(int dis = temp - 2; dis <= temp + 2; dis++)
            for(int start = A[1] - 1; start <= A[1] + 1; start++){
                int cnt = 0;
                int save = start;

                for(int i = 1; i <= N; i++){
                    if(abs(save - A[i]) <= 1)
                        cnt += abs(save - A[i]);
                    else{
                        cnt = INF;
                        break ;
                    }
                    save += dis;
                }
                ans = min(ans, cnt);
            }

        if(ans == INF)
            cout << -1 << '\n';
        else
            cout << ans << '\n';
    }

    return 0;
}