Subtask 1, 2 (30%)

Thuật toán

Ta có thể dùng quay lui để mô phỏng thực hiện tìm tất cả đường đi có thể để giải cứu công chúa, với cách làm này ta có thể AC được subtask 1 với kích thước dữ liệu nhỏ, và subtask 2 do chỉ có một đường đi duy nhất đến màn chơi ~n~.

Code tác giả

// Created by BJMinhNhut
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i) 
#define FORD(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MASK(i) (1ll<<(i))
#define BIT(t, i) (((t)>>(i))&1)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<int, int> ii;

/***Common Functions***/
template <class T>
bool minimize(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template <class T>
bool maximize(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

/***End of Template***/
int n, m, p, D;
const int N = 1e6+5;
vector<ii> adj[N];
ll best = 0;

void Input() {
    cin >> n >> m >> p >> D;
    FOR(i, 1, n) adj[i].clear();
    FOR(i, 1, m) {
        int v, t, l; cin >> l >> v >> t;
        adj[v].pb(mp(t, l));
    }
}

void backtrack(int u, ll cur) {
    if (u == n) maximize(best, cur);
    else {
        for(ii e : adj[u]) {
            if (cur > e.se) backtrack(e.fi, cur+e.se/2);
            else backtrack(e.fi, cur-cur/2);
        }
    }
}

void Solve() {
    best = 0;
    backtrack(1, p);
    if (best >= D) cout << best;
    else cout << "Impossible";
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    if (fopen("inputf.in", "r")) {
        freopen("inputf.in", "r", stdin);
        freopen("outputf.in", "w", stdout);
    }
    int t; cin >> t;
    while (t--)
    Input(), Solve();
    return 0;
}   

Subtask 3 (70%)

Thuật toán

Ta xem mỗi màn chơi như một đỉnh của đồ thị, và các cánh cổng là một cung của đồ thị đó. Do các cánh cổng đều chỉ cho phép đi từ một màn chơi đến màn chơi có chỉ số lớn hơn (~v_i < t_i~). Vậy nên ta dễ dàng nhìn ra đây là một đa đồ thị có hướng không chu trình (DAG).

Từ đây ta có thể nhận thấy rằng bài toán này có thể được giải bằng quy hoạch động như sau:

• Gọi ~dp[u]~ là điểm sức mạnh tối đa có thể đạt được sau khi vượt qua màn chơi $u$;
• ~dp[1] = p~
• ~ dp[t_i] = \begin{cases} dp[v_i] + \lfloor l_i/2 \rfloor && \text{nếu } dp[v_i] > l_i\\ dp[v_i] - \lfloor dp[v_i]/2 \rfloor && \text{ngược lại} \end{cases} ~
• Ta dùng ~dp[n]~ so sánh với ~D~ rồi đưa ra đáp án.

Code tác giả

// Created by BJMinhNhut
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i) 
#define FORD(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MASK(i) (1ll<<(i))
#define BIT(t, i) (((t)>>(i))&1)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<int, int> ii;

/***Common Functions***/
template <class T>
bool minimize(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template <class T>
bool maximize(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

/***End of Template***/
int n, m, p, D;
const int N = 1e6+5;
vector<ii> radj[N];
ll best[N];

void Input() {
    cin >> n >> m >> p >> D;
    FOR(i, 1, n) radj[i].clear();
    FOR(i, 1, m) {
        int v, t, l; cin >> l >> v >> t;
        radj[t].pb(mp(v, l));
    }
}

ll getAns(int u) {
    ll &res = best[u];
    if (~res) return res;
    if (u == 1) return res = p;
    res = 0;
    for(ii e : radj[u]) {
        ll cur = getAns(e.fi);
        if (cur > e.se) cur += e.se/2;
        else cur -= cur/2;
        maximize(res, cur);
    }
    return res;
}

void Solve() {
    FOR(i, 1, n) best[i] = -1;
    if (getAns(n) >= D) {
        cout << best[n];
    } else cout << "Impossible";
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    if (fopen("inputf.in", "r")) {
        freopen("inputf.in", "r", stdin);
        freopen("outputf.in", "w", stdout);
    }
    int t; cin >> t;
    while (t--)
    Input(), Solve();
    return 0;
}