10465 - Homer Simpson

[htl]

I solve it in a traditional way. I used a array with t items. Could someone tell me the faster way?

[aoc90058]

I got TLE QQ~~
[cpp]#include<iostream>
#include<vector>
using namespace std;
int sum(vector<vector<unsigned int> > &h,int flag,int _sum=0){
if(flag>0){
_sum+=h[flag][1];
sum(h,flag-h[flag][1],_sum);
}
else{
return _sum;
}
}
int main(){
unsigned int m,n,input;
vector<unsigned int> t(2);
while(cin>>t[0]>>t[1]>>input){
if(input<t[0] && input<t[1]){
cout<<'0'<<' '<<input<<endl;
continue;
}
vector<vector<unsigned int> > h(input+1,vector<unsigned int> (2,0));
h[0][1]=0;
for(unsigned int i=1;i<h.size();i++){
for(unsigned int j=0;j<t.size();j++){
if(i<t[j]) continue;
if(i-t[j]==0 || h[0]<h[i-t[j]][0]+1 && h[i-t[j]][1]){
h[0]=h[i-t[j]][0]+1;
h[1]=t[j];
}
}
}
int flag,_sum;
for(int i=h.size()-1;i>=0;i--){
if(h[1]>0){
flag=i;
break;
}
}
_sum=sum(h,flag);
if(flag==h.size()-1) cout<<h[flag][0]<<endl;
else cout<<h[flag][0]<<' '<<input-_sum<<endl;
}
} [/cpp]

plz help me ^^
[/cpp][/code]

[jackie]

I use traditonal DP algorithm O(n) max(n) = 10000 and got AC, but it takes the program 2 sec to generate the right output .

I see many people got AC quite fast. Is there some better algorithm or i just code a program not good enough?

if any plz contact me via the private message or mail to: jackie@hit.edu.cn because i may not come this topic soon.

thks

BTW for the person who got WA

you should minimize the time for drinking beer(0 is the best) then maximize the number of burgers.

[Betty]

Hi, I am trying to get better with my DP type problems so i thought i'd have a go with Homer Simpson, my program works and seems to get the right results using a DP solution however i get a TLE when I submit. I tested my program on some high values and yes it does take a while to return them which is why I think I'm missing something that simplyfies the numbers a bit.

Anyone got any tips for this problem?

[cpp]
#include <stdio.h>

int a[4][10000] = {0}; // DP Structure

int t[2]; // time it takes for each type of burger

void check(int val, int type) {


if(type > 0)
check(val, type-1);


// can i skip down more then val - 1? maybe min(t[0], t[1]) then use mod to work out beer
if(val > 0)
check(val-1, type);


int index1 = val - t[type];
int value1 = 0;
int wasted1 = val%t[type];

if(val < t[type]) //set wasted correctly when can't eat burger
wasted1 = val;

if(index1 >= 0) {
value1 = a[type][index1] + 1;

if (a[type+2][index1] < wasted1) wasted1 = a[type+2][index1];
}

int value2 = 0;
int wasted2 = 0;
if(type > 0) {
value2 = a[type-1][val];
wasted2 = a[type+1][val];
}

//check for min wasted time, then amount eaten
if(wasted1 != wasted2 && value2 > 0){
a[type][val] = (wasted1 < wasted2) ? value1 : value2;
a[type+2][val] = (wasted1 < wasted2) ? wasted1 : wasted2;
} else {
a[type][val] = (value1 >= value2) ? value1 : value2;
a[type+2][val] = (value1 >= value2) ? wasted1 : wasted2;
if(value1==value2 && value2 > 0)
a[type+2][val] = (wasted1 < wasted2) ? wasted1 : wasted2;

}


}


int main() {
char line[1000];
int val;


//overkill to make sure loop ends
while(!feof(stdin)) {
fgets(line, 1000, stdin);

if(feof(stdin)) break;
if( sscanf(line, "%d %d %d", &t[0], &t[1], &val) < 3)
break;

//swap t[0] and t[1] if they're the wrong way around
if(t[1] < t[0]) {
t[0]^=t[1]^=t[0]^=t[1];
}


//do a cheat if val can be divided by the smaller of the times
if(val % t[0] == 0) {
a[1][val] = val / t[0];
a[3][val] = 0;
} else {
//run the dp solution
check(val,1);
}
//print answer
printf("%d", a[1][val] );

// if homer drink beer then output it
if(a[3][val] !=0)
printf(" %d", a[3][val]);
printf("\n");
}

return 0;
}

[/cpp]

[Ghost77 dimen]

The problem you request is

ax+by=c find maximum x+y if existed

otherwise decrease the c

There is a well-known formula to examine the possiblity of the statement.

That is wheather gcd(a,b) | c.

If not don't waste any time to find the maximum x+y, otherwise

try it.

The formula work at the x and y are interger, that is maybe negative.

However, the problem only allowed x and y non-negative.

So, if gcd(a,b) | c , maybe still no solution you can find out.

Don't worry, just decrease c again.

Good luck.

[Betty]

I'm not sure what you mean by

gcd(a,b) | c.

I know what a greatest common divisor is, and I presume a and b are the times it takes to eat each type of burger, is c the time it takes overall?

is this a big change i have to make to my code or a simple statement + the gcd function?

[Ghost77 dimen]

gcd(a,b)|c means c can be divided by gcd(a,b)

maybe the symbol '|' isn't quite common in your country.

Well, maybe the method I mentioned before doesn't fit your request.

You want do that by DP.

If I were you, I'll do that by this.

Now I read a, b, and t.

a represented the needed time1, and b ... time2

t is the request time

now I declare an array, the index represented the t

and the value stored in index t means the maximum coresponding to t

if you can't find that, the value should be -1

now the opt-table can be derived from below
[c]
int i,j,k;
int a,b,t;
int opt[Max];

opt[0]=0;
for(i=1;i<=t;i++){
opt=-1;
if(i>=a&&opt[i-a]>opt){
opt=opt[i-a]+1;
}
if(i>=b&&opt[i-b]>=opt){
/*^you should notice here, not typing error*/
opt=opt[i-b]+1;
}
}
[/c]
and then let i from t back to 0

if opt !=-1

then opt is what you want, perhaps t-i is also needed.

I pass the problem long time ago by math formula, around 0.117sec.

Now I try it by simple DP, around 1.389sec.

Good luck.

If you want more dp problems, contact me by pm.

[jaracz]

My critical I/O was:

9 11 21
9 11 19

my prog printed

2 1
1 8 <----- it was obviously wrong
should be : 2 1

Maybe you did same mistake as me
If yes, fix it and have a nice AC;)

Regards

[jaron.yeh]

http://www2.dmhs.kh.edu.tw/homework/q10465.htm


Why WA?

I test all the test data that I can find

but my program is WA as well.......

My code is here

Code: Select all

#include <iostream>
using namespace std ;
int main(){
	int m , n , t ;
	while( cin >> m >> n >> t ){
		int Mx = 0 , My = 0 , Ma = 0 ;
		for( int i = t / m ; i >= 0 ; i -- ){
			if( ( t - m * i ) % n == 0 ){
				Mx = i ;
				My = ( t - m * i ) / n ;
				Ma = i * m + ( ( t - m * i ) / n ) * n ;
				break ;
			}
			else if( Ma < i * m + ( ( t - m * i ) / n ) * n 
					&& i * m + ( ( t - m * i ) / n ) * n < t ){
				Ma = i * m + ( ( t - m * i ) / n ) * n ;
				Mx = i ;
				My = ( t - m * i ) / n ;
			}
			else if( Ma == i * m + ( ( t - m * i ) / n ) * n 
					&& i * m + ( ( t - m * i ) / n ) * n < t )
	      			    if( Mx + My < i + ( t - m * i ) / n ){
					    Mx = i ;
					    My = ( t - m * i ) / n ;
				    }
		}
		if( Ma == t )
			cout << Mx + My << endl ;
		else 
			cout << Mx + My << " " << t - Ma << endl ;
	}
}

[smilitude]

I coded 10465 like this -->

Code: Select all

#include <iostream>
#include <cstdio>
using namespace std;

int main() {
    int i,j,m,n,t,best[10010];
    int time[10010];
    while(scanf("%d%d%d",&m,&n,&t)==3){
        for(i=0;i<=t;i++) {
            time[i]=0;
            best[i]=0;
        }
        best[m]=1;
        best[n]=1;
        time[m]=m;
        time[n]=n;
        
        for(i=1;i<=t;i++)
        for(j=1;j<=i/2;j++) {
            if(time[i]<time[j]+time[i-j]) {
                best[i]=best[j]+best[i-j];
                time[i]=time[j]+time[i-j];
            }else if(time[i]==time[j]+time[i-j]) {
                if(best[i]<best[j]+best[i-j])
                    best[i]=best[j]+best[i-j];                
            }   
        }
       
        cout<<best[t];
        if(t-time[t]) cout<<" "<<t-time[t];
        cout<<endl;        
    }
    return 0;
}    

I am getting TLE - is there any better dp approach?

[asif_rahman0]

You can simply do it by

Code: Select all

mx+ny=t then (x+y=maximum time)

If it remains extra TIME then it should go for beer.

Your DP code give some overflow value in my compiler(VC++).

[smilitude]

Thanks a lot!
But i think you wanted to tell me x+y=maximum burger, when m, and n are the eating time of each burgers respectively!
I am not sure, but if i start to check from given time t, to lower t--, and check whether its possible to get a valid equation for mx+ny=t, it would involve some serious modular arithmatic! I thought for a nice sweet dp thing!
Hmm... I use devcpp, I thought GNU compilers ints are 32 bit, 2147483648 is the highest, not sure, why you get overflow...

[sunny]

i solved it in O(n) time.

my dp part looks like :

initialize best[10001] array by 0;

best[m]=best[n]=1;

for(i=min(m,n);i<=t;i++){
if(i>=m && best[i-m]+1 > best && best[i-m]) best=best[i-m]+1;
if(i>=n && best[i-n]+1 > best && best[i-n]) best=best[i-n]+1;
}


if best[t]!=0 then simply output best[t].
if best[t]=0 that means u must have some beers. so do a simple linear search 2 find the amounts.

[smilitude]

nice solution sunny!
i made it really complicated, thanks!

[sklitzz]

i solved it in O(n) time.

my dp part looks like :

initialize best[10001] array by 0;

best[m]=best[n]=1;

for(i=min(m,n);i<=t;i++){
if(i>=m && best[i-m]+1 > best && best[i-m]) best=best[i-m]+1;
if(i>=n && best[i-n]+1 > best && best[i-n]) best=best[i-n]+1;
}


if best[t]!=0 then simply output best[t].
if best[t]=0 that means u must have some beers. so do a simple linear search 2 find the amounts.

Firstly I was amazed that your code looked so much like mine! But there's one problem I get WA.

I did it with the same idea( actualy the variable's names are very simmilar ). But I don't get it why my code fails.

Code: Select all

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

int n, m, t;
int best[10001];

int main() {
	
	while( cin >> m ) {
		cin >> n >> t;
		
		int sol = 0, beer = INT_MAX;
		memset( best, 0, sizeof( best ) );
		best[m] = best[n] = 1;
			
		for( int i = min( m, n ); i <= t; ++i ) {
			if( i >= m && best[i - m] != 0 ) best[i] >?= best[i - m] + 1;
			if( i >= n && best[i - n] != 0 ) best[i] >?= best[i - n] + 1;
		}
		
		for( int i = 1; i <= t; ++i ) {
			if( best[i] != 0  && ( t - i ) < beer )  {
				sol = best[i];
				beer = t - i;
 			}
			if( best[i] != 0  && ( t - i ) == beer ) 
				sol >?= best[i];
		}
				
		if( beer > 0 ) cout << sol << " " << beer << endl;
		else cout << sol << endl;
		
		
		/*for( int i = 1; i <= t; ++i ) cout << best[i] << " " ;
		cout << endl;*/
	}
	
	return 0;
}