10090 - Marbles

Problem Link :https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1031

Solution Idea : A very good problem. we have to use extended euclid and then the  solve  of Diophantine equation with positive values to solve this problem.for avoiding tle we need to check only the boundary values of the limit for the positive solution.

Solution :

#include<bits/stdc++.h>
#define ll long long
using namespace std;


ll int X=-1,Y=-1;

ll int ext_gcd (ll int A,ll int B)
{
    ll int x2, y2, x1, y1, x, y, r2, r1, q, r;
    x2 = 1;
    y2 = 0;
    x1 = 0;
    y1 = 1;
    for (r2 = A, r1 = B; r1 != 0; r2 = r1, r1 = r, x2 = x1, y2 = y1, x1 = x, y1 = y )
    {
        q = r2 / r1;
        r = r2 % r1;
        x = x2 - (q * x1);
        y = y2 - (q * y1);
    }
    X = x2;
    Y = y2;

    return r2;
}

int main()
{
    ll int n,c1,n1,c2,n2,g,x1,y1,x,y,lo,hi,ans=1000000000000000,m=1000000000000000,a1=0,b1=0;

    while(scanf("%lld",&n) and n)
    {
        scanf("%lld%lld%lld%lld",&c1,&n1,&c2,&n2);
        ans=1000000000000000;
        m=1000000000000000;
        g=ext_gcd(n1,n2);

        if(n%g!=0) printf("failed\n");
        else
        {
            x=(n*X)/g;
            y=(n*Y)/g;

            lo=ceil(-((double)n*X)/n2);
            hi=floor(((double)n*Y)/n1);

            if(lo>hi)
            {
                printf("failed\n");
                continue;
            }

            x1=x+((n2*lo)/g);
            y1=y-((n1*lo)/g);
            a1=x+((n2*hi)/g);
            b1=y-((n1*hi)/g);

            if(x1>=0 and y1>=0)
            {


                m=(x1*c1)+(y1*c2);
            }
            if(a1>=0 and b1>=0)
            {


                ans =(a1*c1)+(b1*c2);
            }
            if(m<ans)
            {
                ans=m;
                a1=x1;
                b1=y1;
            }

            printf("%lld %lld\n",a1,b1);
        }
    }



}