Cod sursa(job #2640423)

Utilizator bogdi1bogdan bancuta bogdi1 Data 6 august 2020 13:36:01
Problema Vanatoare Scor 100
Compilator cpp-32 Status done
Runda Arhiva de probleme Marime 2.79 kb
#include <cstdio>
#include <algorithm>
using namespace std;
const int INF = 2000000000;
struct Porci
{
    int c,v;
} porc[20];
int sepoate[65600];
int dp[65600];
int sol[20];
int t;
int n1,a1,n2,a2;
int cmmdc(int a, int b)
{
    int r;
    while(b){
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
int cmmmc(int a, int b)
{
    a=a/cmmdc(a, b);
    if(a<=INF/b)
        return a*b;
    else
        return -1;
}
int euclid(int a, int b, long long &x, long long &y)
{
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    int d;
    long long x0,y0;
    d=euclid(b, a%b, x0, y0);
    x=y0;
    y=x0-(a/b)*y0;
    return d;
}

void chinez()
{
    if(n1==t+1){
        if(a1%n2!=a2){
            a1=-1;
            return;
        }
        else
            return;
    }
    long long c1,c2;
    int d=euclid(n1, n2, c1, c2);
    if((a2-a1)%d!=0){
        a1=-1;
        return;
    }
    int h=min(1LL*(t+1), 1LL*n1*n2/d);
    int l=(a2-a1)/d;
    int m1=(1LL*c1*l)%(n2/d);
    if(m1<0)
        m1+=n2/d;
    long long x=1LL*n1*m1+a1;
    if(h<=t){
        x%=h;
        a1=x;
        n1=h;
        return;
    }
    else{
        x%=(1LL*n1*n2/d);
        if(x<=t){
            a1=x;
            n1=h;
            return;
        }
        else{
            a1=-1;
            return;
        }
    }
}
void dfs(int stare)
{
    int i;
    if(sepoate[stare]!=-1){
        sol[++sol[0]]=sepoate[stare];
        return;
    }
    for(i=stare; i!=0; i=(i-1)&stare)
        if(dp[i]+dp[stare-i]==dp[stare] && i!=stare)
            break;
    dfs(i);
    dfs(stare-i);
}
int main()
{   freopen("vanatoare.in", "r", stdin);
    freopen("vanatoare.out", "w", stdout);
    int n,i,ok,j,doilan;
    scanf("%d%d", &n, &t);
    for(i=0; i<n; i++)
        scanf("%d%d", &porc[i].c, &porc[i].v);
    doilan=(1<<n);
    for(i=1; i<doilan; i++){
        ok=0;
        for(j=0; j<n; j++){
            if(((1<<j)&i)!=0){
                if(ok==0){
                    n1=porc[j].v;
                    a1=porc[j].c;
                    ok=1;
                }
                else{
                    n2=porc[j].v;
                    a2=porc[j].c;
                    chinez();
                    if(a1==-1)
                        break;
                }
            }
        }
        sepoate[i]=a1;
    }
    for(i=1; i<doilan; i++){
        if(sepoate[i]==-1)
            dp[i]=20;
        else
            dp[i]=1;
    }
    for(i=1; i<doilan; i++)
        for(j=i; j!=0; j=(j-1)&i)
            dp[i]=min(dp[i], dp[j]+dp[i-j]);
    printf("%d\n", dp[doilan-1]);
    dfs(doilan-1);
    sort(sol+1, sol+sol[0]+1);
    for(i=1; i<=sol[0]; i++)
        printf("%d ", sol[i]);
    return 0;
}