Cod sursa(job #2382791)

Utilizator akaprosAna Kapros akapros Data 18 martie 2019 18:00:20
Problema Vanatoare Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.94 kb
#include <bits/stdc++.h>
#define maxN 16
#define maxCf (1 << maxN) + 2
#define maxP 14145
#define v first
#define c second
#define pii pair<int, 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];

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

vector < int > sol;

int ExtEuclid(int a, int b, int &x, int &y)
{
    int x0, y0;
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int z = a / b, c = a;
    a = b;
    b = c % b;
    int d = ExtEuclid(a, b, x0, y0);
    x = y0;
    y = x0 - z * y0;
    return d;
}
int MinVal(int bit, int cf)
{
    if (cf == 0)
    {
        dp[cf | (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);
    int x, y, gcd, r;
    gcd = ExtEuclid(A.v, B.v, x, y);
    r = B.c - A.c;
    if (r % gcd) return t + 1;
    r /= gcd;
    B.v /= gcd;
    ll lcm = 1LL * B.v * A.v / gcd;
    ll ret = (1LL * x * A.v * r + A.c) % lcm;
    dp[cf | (1 << bit)].p = lcm;
    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;
        if (!vis[cf])
        {
            vis[cf] = true;
            for (int bit = 0; bit < n; ++ bit)
                if (cf & (1 << bit))
                {
                    if (dp[cf ^ (1 << bit)].a > t)
                        dp[cf].a = t + 1;
                    else
                        dp[cf].a = MinVal(bit, cf ^ (1 << bit));
                    break;
                }
        }
        if (dp[cf].a > t)
        {
            int compCf = all ^ cf;
            for (int prvCf = compCf; prvCf != 0; prvCf = compCf & (prvCf - 1))
            {
                vis[prvCf | cf] = true;
                dp[prvCf | cf].a = t + 1;
            }
            Update(cf);
            //sort(dp[cf].sol.begin(), dp[cf].sol.end());
        }
        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;
}