UVa : 10465 (Homer Simpson)


Title : Homer Simpson

Link : http://uva.onlinejudge.org/external/104/10465.html

Tricky Lines :

  1. print in a single line the maximum number of burgers Homer can eat without having beer.
  2. If homer must have beer, then also print the time he gets for drinking, separated by a single space.

Analysis :

  1. this problem has tags : number theory, gcd, diophantine equation. Though i’ve solve it with dp, becoz i’m not good at dp
  2. array times [n] = highest number of burgers Homer can have in time ‘n’
  3. surely, times [m] = times [n] = 1
  4. if ( times [k] > 0 ) then
    times [k + m] = times [k] + 1;
  5. at last, if ( times [t] > 0 ) then print times [t]
    otherwise, find the first time, k ( k < t )
    such that, times [k] > 0

Runtime : 0.208s

Critical Input : 
852 965 9999
96 52 50
48 52 55
6 9 96
3 5 2
3 5 4

Critical output : 
11 62
0 50
1 3
16
0 2
1 1

Solution :

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#define INT_MAX 2147483647
#define INT_MIN -2147483648
#define pi acos(-1.0)
#define N 1000000
#define long long LL
using namespace std;

int main ()
{
    int m, n, t;

    while ( scanf ("%d %d %d", &m, &n, &t) != EOF ) {
        int times [10000 + 10];
        memset (times, 0, sizeof (times));

        if ( m > n ) swap (m, n);

        times [m] = 1;
        times [n] = 1;

        for ( int i = m; i <= t; i++ ) {
            if ( times [i] ) {
                if ( i + m <= t ) times [i + m] = max ( times [i + m], times [i] + 1);
                if ( i + n <= t ) times [i + n] = max ( times [i + n], times [i] + 1);
            }
        }

        if ( times [t] > 0 ) printf ("%d\n", times [t]);
        else {
            bool printed = false;
            for ( int i = t - 1; i >= 0; i-- ) {
                if ( times [i] > 0 ) {
                    printf ("%d %d\n", times [i], t - i);
                    printed = true;
                    break;
                }
            }

            if ( !printed ) printf ("0 %d\n", t);
        }
    }

	return 0;
}

// @END_OF_SOURCE_CODE

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