Cod sursa(job #2239888)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 11 septembrie 2018 23:00:45
Problema Vanatoare Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.05 kb
#include <bits/stdc++.h>
using namespace std;

ifstream in("vanatoare.in");
ofstream out("vanatoare.out");

const int DIM = 16;

pair<int, int> fnc[1 << DIM];
int dp[1 << DIM], ant[1 << DIM];

int extendedEuclid(int a, int b, long long &x, long long &y)
{
    if (!b) {
        x = 1; y = 0;
        return a;
    } else {
        long long x0, y0; int d;
        d = extendedEuclid(b, a % b, x0, y0);
        x = y0; y = x0 - y0 * (a / b);
        return d;
    }
}

pair<int, int> computeFunction(pair<int, int> fnc1, pair<int, int> fnc2, int t)
{
    if (fnc1 == make_pair(0, 0) || fnc2 == make_pair(0, 0))
        return make_pair(0, 0);
    long long x, y, gcd, c, p, lcm, val, pos;
    p = max(fnc1.first, fnc2.first); c = fnc1.first - fnc2.first;
    gcd = abs(extendedEuclid(-fnc1.second, fnc2.second, x, y));
    lcm = 1LL * fnc1.second * fnc2.second / gcd;
    if (c % gcd)
        return make_pair(0, 0);
    x *= c / gcd; y *= c / gcd;
    val = -(x * fnc1.second + fnc1.first - p);
    val = val / lcm + (val % lcm > 0);
    pos = x * fnc1.second + fnc1.first + lcm * val;
    return (pos > t) ? make_pair(0, 0) : make_pair((int)pos, (int)min(lcm, (long long)(t + 1)));
}

void debug()
{
    pair<int, int> f = computeFunction(make_pair(3, 5), make_pair(2, 4), 10000);
    cout << f.first << " " << f.second << endl;
    exit(0);
}

int main(void)
{
    //debug();
    
    int n, t; in >> n >> t;
    for (int i = 0; i < n; ++i)
        in >> fnc[1 << i].first >> fnc[1 << i].second;
    for (int msk = 1; msk < (1 << n); ++msk)
        if (msk ^ (msk & -msk))
            fnc[msk] = computeFunction(fnc[msk & -msk], fnc[msk ^ (msk & -msk)], t);
    for (int msk = 1; msk < (1 << n); ++msk) {
        dp[msk] = (fnc[msk] != make_pair(0, 0)) ? 1 : n + 1;
        for (int axm = msk; axm; (--axm) &= msk)
            if (dp[msk] > dp[axm] + dp[msk ^ axm])
                dp[msk] = dp[axm] + dp[msk ^ axm], ant[msk] = axm;
    }
    out << dp[(1 << n) - 1] << endl;
    for (int msk = (1 << n) - 1; msk; msk = ant[msk])
        out << fnc[msk ^ ant[msk]].first << " ";
    return 0;
}