10465 - Homer Simpson

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Post by htl » Tue Jul 06, 2004 6:05 pm

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

aoc90058
New poster
Posts: 1
Joined: Wed Jul 07, 2004 10:20 am

Post by aoc90058 » Wed Jul 07, 2004 2:02 pm

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
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am

Post by jackie » Tue Jul 27, 2004 11:17 am

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
New poster
Posts: 19
Joined: Sun Aug 17, 2003 2:10 pm

10465 Homer Simpsons TLE Help

Post by Betty » Sun Aug 01, 2004 5:35 am

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]

User avatar
Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

Post by Ghost77 dimen » Sun Aug 01, 2004 4:23 pm


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. 8)

Betty
New poster
Posts: 19
Joined: Sun Aug 17, 2003 2:10 pm

Post by Betty » Mon Aug 02, 2004 1:05 pm

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?

User avatar
Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

Post by Ghost77 dimen » Mon Aug 02, 2004 7:49 pm


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. 8)

User avatar
jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland

Post by jaracz » Mon Jun 13, 2005 6:18 pm

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
keep it real!

jaron.yeh
New poster
Posts: 1
Joined: Wed Dec 07, 2005 5:25 pm

10465

Post by jaron.yeh » Wed Dec 07, 2005 5:34 pm

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 ;
	}
}

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

10465 TLE O(n^2) ??

Post by smilitude » Sat Jul 01, 2006 8:27 am

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?
fahim
#include <smile.h>

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 » Sat Jul 01, 2006 6:40 pm

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++). ;)

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

thanks!

Post by smilitude » Sun Jul 02, 2006 8:27 pm

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... :roll:
fahim
#include <smile.h>

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

Post by sunny » Mon Jul 03, 2006 5:02 am

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.

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude » Mon Jul 03, 2006 9:17 pm

nice solution sunny!
i made it really complicated, thanks!
fahim
#include <smile.h>

sklitzz
New poster
Posts: 32
Joined: Fri Dec 03, 2004 5:19 pm

Post by sklitzz » Sun Aug 13, 2006 8:32 pm

sunny wrote: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;
}

Post Reply

Return to “Volume 104 (10400-10499)”