Cod sursa(job #2382967)

Utilizator akaprosAna Kapros akapros Data 18 martie 2019 21:24:18
Problema Vanatoare Scor 75
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.65 kb
#include <bits/stdc++.h>
#define maxN 16
#define maxCf (1 << maxN) + 2
#define v first
#define c second
#define pii pair<ll, int>
#define ll long long

using namespace std;

FILE *fin = freopen("vanatoare.in", "r", stdin);
FILE *fout = freopen("vanatoare.out", "w", stdout);

int n, t;
pii b[maxN + 1];

struct State
{
    ll p;
    int a, cost, prv;
};
State dp[maxCf];

vector < int > sol;

ll ExtEuclid(ll a, ll b, ll &x, ll &y)
{
    ll x0, y0;
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    ll z = a / b, c = a;
    a = b;
    b = c % b;
    ll d = ExtEuclid(a, b, x0, y0);
    x = y0;
    y = x0 - z * y0;
    return d;
}
int MinVal(int bit, int cf)
{
    if (cf == 0)
    {
        dp[(1 << bit)].p = b[bit].v;
        return b[bit].c;
    }
    pii A = pii{dp[cf].p, dp[cf].a},
        B = b[bit];
    if (B.c < A.c) swap(A, B);
    ll x, y, gcd;
    gcd = ExtEuclid(A.v, B.v, x, y);
    ll r = B.c - A.c;
    if (r % gcd) return t + 1;
    r /= gcd;
    B.v /= gcd;
    ll lcm = B.v * A.v;
    ll ret = (x * r) % B.v;
    ret = (ret + B.v) % B.v;
    ret = ((ret * A.v + A.c) % lcm + lcm) % lcm;

    dp[cf | (1 << bit)].p = lcm;
    if (r == 0) return A.c;
    if (ret > t) return t + 1;

    return (int)ret;
}
void findSol(int cf)
{
    if (cf == 0) return ;
    if (dp[cf].cost == 1)
    {
        sol.push_back(dp[cf].a);
        return ;
    }
    findSol(dp[cf].prv);
    findSol(dp[cf].prv ^ cf);
}
void Update(int cf)
{
    int prv = 0;
    for (int prvCf = cf & (cf - 1); prvCf != 0; prvCf = cf & (prvCf - 1))
        if (dp[cf].cost > dp[cf ^ prvCf].cost + dp[prvCf].cost)
        {
            dp[cf].cost = dp[cf ^ prvCf].cost + dp[prvCf].cost;
            dp[cf].prv = prvCf;
        }
}
int main()
{
    scanf("%d%d", &n, &t);

    for (int i = 0; i < n; ++ i)
        scanf("%d%d", &b[i].c, &b[i].v);


    int all = (1 << n) - 1;
    for (int cf = 1; cf <= all; ++ cf)
    {
        dp[cf].cost = n;

        for (int bit = 0; bit < n; ++ bit)
            if ((cf & (1 << bit)) && dp[cf ^ (1 << bit)].a > t)
                dp[cf].a = t + 1;
        if (dp[cf].a == 0)
            for (int bit = 0; bit < n; ++ bit)
                if (cf & (1 << bit))
                {
                    dp[cf].a = MinVal(bit, cf ^ (1 << bit));
                    break;
                }

        if (dp[cf].a > t)
            Update(cf);
        else
            dp[cf].cost = 1;

    }
    printf("%d\n", dp[all].cost);
    findSol(all);
    sort(sol.begin(), sol.end());
    for (int ans : sol)
        printf("%d ", ans);
    return 0;
}