10465 - Homer Simpson

homer.cpp

//http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1406
#include <cstdio>
#include <algorithm>

using namespace std;

int main() {
    int n, m, t;
    while(scanf("%d %d %d", &m, &n, &t) != EOF) {
        int dp[10005];
        fill(dp,dp+t+1,-1);
        dp[0] = 0;
        for(int i = min(n,m); i <= t; i++) {
            if(i >= n && dp[i-n] != -1)
                dp[i] = max(dp[i],1+dp[i-n]);
            if(i >= m && dp[i-m] != -1)
                dp[i] = max(dp[i],1+dp[i-m]);
        }
        if(dp[t] != -1) {
            printf("%d\n",dp[t]);
        } else {
            int i = t;
            while(dp[i] == -1) i--;
            printf("%d %d\n", dp[i], t-i);
        }
    }
    return 0;
}