Untitled

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
6.6 kB
0
Indexable
Never
#include <bits/stdc++.h>
#include <cstdint>

using namespace std;
using namespace std::chrono;

// datatypes
#define int long long
#define ld long double
#define ull unsigned long long
#define mii map<int, int>
#define pi pair<int, int>
#define pq priority_queue<int>
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fi first
#define se second
#define endl "\n"
#define as " "

// important constants
#define MOD 1000000007
#define INF 1LL << 57LL
#define MAX 1000000
#define pie 3.14159265358979
#define ESP (1e-9)

// Modulus-Mathematics
template <typename T, typename U>
int modMul(T a, U b) { return ((a % MOD) * 1LL * (b % MOD)) % MOD; }
template <typename T, typename U>
int binpower(T n, U k)
{
    T res = 1;
    while (k)
    {
        if (k & 1)
        {
            res = modMul(res, n);
        }
        n = modMul(n, n);
        k >>= 1;
    }
    return res % MOD;
}
template <typename T>
T moduloInverse(T a) { return binpower(a, MOD - 2); }
template <typename T, typename U>
int modAdd(T a, U b) { return ((a % MOD) + (b % MOD)) % MOD; }
template <typename T, typename U>
int modSub(T a, U b) { return ((a % MOD) - (b % MOD) + MOD) % MOD; }
template <typename T, typename U>
int modDiv(T a, U b) { return modMul(a, moduloInverse(b)); }

// GCD and LCM
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
int lcm(int a, int b)
{
    return (a / gcd(a, b)) * b;
}

// vectors
typedef vector<int> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef pair<int, bool> pib;
typedef pair<string, int> psi;
typedef pair<string, string> pss;
typedef vector<pii> vpii;
typedef vector<psi> vpsi;
typedef vector<pss> vpss;

// looping
#define fr(i, a) for (int i = 0; i < a; i++)
#define fe(i, a) for (int i = 0; i <= a; i++)
#define fu(i, a, n) for (int i = a; i < n; i++)
#define fue(i, a, n) for (int i = a; i <= n; i++)
#define fd(i, n, a) for (int i = n; i > a; i--)
#define fde(i, n, a) for (int i = n; i >= a; i--)

#define sum(a) (accumulate((a).begin(), (a).end(), 0ll))
#define mine(a) (*min_element((a).begin(), (a).end()))
#define maxe(a) (*max_element((a).begin(), (a).end()))
#define mini(a) (min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a) (max_element((a).begin(), (a).end()) - (a).begin())
#define maxij(a, i, j) (max_element((a).begin() + i, (a).begin() + j + 1) - (a).begin())
#define lowb(a, x) (lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) (upper_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define sz(a) (int)((a).size())
#define rs(a, n) ((a).resize(n))
#define ms(a, val)     ( memset((a), val, sz(a))

// debugging
#ifndef ONLINE_JUDGE
#define dg(x)           \
    cerr << #x << "\t"; \
    _print(x);          \
    cerr << endl;
#define dg2(x, y)                  \
    cerr << #x << "\t";            \
    _print(x);                     \
    cerr << "\t|\t" << #y << "\t"; \
    _print(y);                     \
    cerr << endl;
#define dg3(x, y, z)               \
    cerr << #x << "\t";            \
    _print(x);                     \
    cerr << "\t|\t" << #y << "\t"; \
    _print(y);                     \
    cerr << "\t|\t" << #z << "\t"; \
    _print(z);                     \
    cerr << endl;
#define dg4(x, y, z, w)            \
    cerr << #x << "\t";            \
    _print(x);                     \
    cerr << "\t|\t" << #y << "\t"; \
    _print(y);                     \
    cerr << "\t|\t" << #z << "\t"; \
    _print(z);                     \
    cerr << "\t|\t" << #w << "\t"; \
    _print(w);                     \
    cerr << endl;
#else
#define dg(x)
#define dg2(x, y)
#define dg3(x, y, z)
#define dg4(x, y, z, w)
#endif

void _print(int x)
{
    cerr << x;
}
void _print(float x) { cerr << x; }
void _print(double x) { cerr << x; }
void _print(string x) { cerr << x; }
void _print(ull x) { cerr << x; }
void _print(char x) { cerr << x; }
void _print(bool x) { cerr << x; }

template <typename T>
vector<T> inp(int n)
{
    vector<T> ain(n);
    fr(i, n) cin >> ain[i];
    return ain;
}

template <typename T>
void print(vector<T> arr)
{
    fr(i, arr.size()) cout << arr[i] << " ";
    cout << endl;
    return;
}

bool isPalindrome(int x)
{
    string s = to_string(x);
    string t = s;
    reverse(all(t));
    if (s == t)
        return true;
    return false;
}

int n, d, ans;
vll arr;
int dp[410][410][11];

int diff(int a, int b)
{
    int val = abs(a - b);
    val = min(abs(min(a, b) + d - max(a, b)), val);
    return val;
}

int rec(int i, int j, int k) 
{
    if (i < 0 || j < 0 || i > j)
    {
        return 0;
    }
    else if (i == j)
    {
        dp[i][j][k] = diff(arr[i], k);
    }
    else if (dp[i][j][k] != 1e15)
    {
        // return dp[i][j][k];
    }
    else if (arr[i] == arr[j])
    {
        dp[i][j][k] = rec(i + 1, j - 1, arr[i]);
        dp[i][j][k] += diff(arr[i], k);
    }
    else
    {
        int a = rec(i + 1, j, arr[i]);
        if (i < n - 1)
        {
            a += diff(k, arr[i]);
        }
        int b = rec(i, j - 1, arr[j]);
        if (j > 0)
        {
            b += diff(k, arr[j]);
        }
        dp[i][j][k] = min(a, b);
    }
    // cerr << i << " " << j << " " << k << " " << dp[i][j][k] << endl;
    return dp[i][j][k];
}

void solve(int t)
{
    cin >> n >> d;
    // cerr << n << " " << d << endl;
    arr = inp<int>(n);
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            for (int k = 0; k <= 10; k++)
                dp[i][j][k] = 1e15;
        }
    }
    ans = rec(0, n - 1, 0);
    //  + max(0LL, min(arr[0], arr[n - 1]) - 1);
    cout << "Case #" << setprecision(10) << t << ": " << ans << endl;
    return;
}

int32_t main()
{
    // auto start = high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // Start of Code..
    int t;
    cin >> t;
    int p = 1;
    while (t--)
    {
        solve(p);
        p++;
    }
    // End of Code
    // auto stop = high_resolution_clock::now();                  // stop clock
    // auto duration = duration_cast<microseconds>(stop - start); // printing duration
    // cerr << "Time taken by function: " << duration.count() / 1000.0 << " millisec" << endl;
    return 0;
}

//   ___       __   __       __  ___  ___  __            __   __
//  |__  |\ | /  ` |__) \ / |__)  |  |__  |  \        | |__) / _`
//  |___ | \| \__, |  \  |  |     |  |___ |__/ ___ \__/ |    \__>
//