UVa 10465 – Homer Simpson

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

Github Link : https://github.com/tanmoy13/Uva/tree/master/10465—Homer-Simpson

Solution Idea:

This is a dp problem. we can say that this is a knapsack problem where n and m is weight of two burgers and profit is always 1. Capacity is the given time t. so we have to maximize the weight. The main problem I faced to solve this problem is to understand the 2nd sample case. After reading the problem statement several time I understand that the problem statement states that we have to minimize the number of beer. So in the 2nd sample case the maximum number of burger can be eaten is 18 but in this case Simpson have to drink 1 beer. On the other hand if Simpson take 17 burgers (15*3)+(5*2) then he need not to drink any beer so in this case the solution will be 17 instead of 18.

Now think how can we code the problem. In recursive method I at first I  determine the maximum time that can be spend in burger through a recursion like dfs. and then I calculate the maximum number of burger that can be eaten in that time. if the maximum time is equal to “t” then we print only number of burgers otherwise maximum number of burgers and the number of beer (t-maximum time) .  U have to handle two special cases separately. Think about that 😛 .

Now it’s time for Iterative solution. this one is faster than previous one. in this solution let dp[] array contains the number of burgers in a certain time. dp[x] means Simpson can eat dp[x] burgers in x time. so we can say that always dp[min(n,m)]=1. so at first we set the whole dp array with negative value and dp[0]=0. Now we run a loop and calculate the result as follows.




/*
         +-+ +-+ +-+
         |R| |.| |S|
         +-+ +-+ +-+
 */

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sfl(a)          scanf("%lld",&a)
#define sff(a,b)        scanf("%d %d",&a,&b)
#define sffl(a,b)       scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)     scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)    scanf("%lld %lld %lld",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d: ",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

int dp[10100];

int main()
{
//    freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);

    int n,m,t;
    while(sfff(n,m,t)==3)
    {
        if(n==1|| m==1)
        {
            pf("%d\n",t);
            continue;
        }

        ms(dp,-1);

        dp[0]=0;

        REP(i,0,t+5)
        {
            int xx=0,yy=0;

            if(i-n>=0)
                xx=dp[i-n]+1;
            if(i-m>=0)
                yy=dp[i-m]+1;
            if(max(xx,yy)>0)
                dp[i]=max(xx,yy);
        }

        if(dp[t]>=0)
        {
            pf("%d\n",dp[t]);
            continue;
        }

        for(int i=t-1; i>-1; i--)
        {
            if(dp[i]>=0)
            {
                pf("%d %d\n",dp[i],t-i);
                break;
            }

        }
    }
    
    return 0;
}

Recursive solution is here. But this one is slower than upper one.

/*
         +-+ +-+ +-+
         |R| |.| |S|
         +-+ +-+ +-+
 */

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sfl(a)          scanf("%lld",&a)
#define sff(a,b)        scanf("%d %d",&a,&b)
#define sffl(a,b)       scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)     scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)    scanf("%lld %lld %lld",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d: ",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

int dp[10500];
bool visit[10500];
int n,m,t;
int maxi=100000000;

void func(int u)
{
    if(visit[u]) return;
    visit[u]=1;
    if(u>=t)
    {
        return;
    }
    func(u+n);
    func(u+m);
}


int find_ans(int u)
{
    if(u==0) return 0;
    if(u<0) return -10000000;
    if(dp[u]!=-1) return dp[u];

    int p=0,q=0;

    p=1+find_ans(u-n);
    q=1+find_ans(u-m);
    return dp[u]=max(p,q);

}

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);


    while(cin>>n>>m>>t)
    {

        if(n==1 || m==1)
        {
            cout<<t<<endl;
            continue;
        }
        if(n>t && m>t)
        {
            cout<<0<<" "<<t<<endl;
            continue;
        }

        ms(dp,-1);
        ms(visit,0);

        func(0);

        if(visit[t])
        {
            cout<<find_ans(t)<<endl;
        }
        else
        {
            int x=t;
            while(--x)
            {
                if(visit[x])
                {
                    cout<<find_ans(x)<<" "<<t-x<<endl;
                    break;
                }
            }
        }


    }

    return 0;
}


Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s