11285 - Exchange Rates

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

Moderator: Board moderators

Post Reply
TimeString
New poster
Posts: 26
Joined: Mon Nov 13, 2006 3:53 am

11285 - Exchange Rates

Post by TimeString » Fri Dec 28, 2007 1:46 pm

i use O(n^2) solution but seems it does not expected, i got TLE.
it's very strange because the limit of n is 365, so i just want to check do i really have to implement an O(n) solution?

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Fri Dec 28, 2007 2:42 pm

I can't imagine a O(n^2) solution. Could you post you code ?

-----
Rio

TimeString
New poster
Posts: 26
Joined: Mon Nov 13, 2006 3:53 am

Post by TimeString » Fri Dec 28, 2007 2:50 pm

Code: Select all

#include <stdio.h>

int main(){
	int en;
	double erate[400];
	int i,j;
	double dp[400];

	while(scanf("%d",&en)==1 && en>0){
		for(i=1;i<=en;i++)
			scanf("%lf",&erate[i]);
		dp[0]=1000.0;
		for(i=1;i<=en;i++){
			dp[i]=0.0;
			for(j=0;j<i;j++){
				static double t;
				t=dp[j]/erate[j]*0.97*erate[i]*0.97;
				if(t>dp[i])
					dp[i]=t;
				if(dp[j]>dp[i])
					dp[i]=dp[j];
			}
		}
		printf("%.2lf\n",dp[en]);
	}

	return 0;
}

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Fri Dec 28, 2007 3:41 pm

You code has a bug. You didn't initialize erate[0], but using in code:

Code: Select all

         for(j=0;j<i;j++){
            static double t;
            t=dp[j]/erate[j]*0.97*erate[i]*0.97;
            if(t>dp[i])
               dp[i]=t;
            if(dp[j]>dp[i])
               dp[i]=dp[j];
         } 
I sent a code which initialize erate[0] with 1e9 and it got WA in 0.060 s.

Anyway, O(n) DP is way easier to implement.
-----
Rio

TimeString
New poster
Posts: 26
Joined: Mon Nov 13, 2006 3:53 am

Post by TimeString » Fri Dec 28, 2007 4:04 pm

rio wrote:You code has a bug. You didn't initialize erate[0], but using in
I sent a code which initialize erate[0] with 1e9 and it got WA in 0.060 s.
thanks a lot.
but i think the bug will lead to runtime error or wrong answer, not time limited exceed = =||

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Fri Dec 28, 2007 4:20 pm

Send a code with commenting out below part.

Code: Select all

            if(t>dp[i])
               dp[i]=t;
            if(dp[j]>dp[i])
               dp[i]=dp[j]; 
You could guess why its getting TLE.
-----
Rio

TimeString
New poster
Posts: 26
Joined: Mon Nov 13, 2006 3:53 am

Post by TimeString » Sun Dec 30, 2007 8:14 am

rio wrote:Send a code with commenting out below part.

Code: Select all

            if(t>dp[i])
               dp[i]=t;
            if(dp[j]>dp[i])
               dp[i]=dp[j]; 
You could guess why its getting TLE.
i still don't know why.
does it mean that it costs a lot of time to do float number comparison?

Post Reply

Return to “Volume 112 (11200-11299)”