Page **1** of **1**

### 11285 - Exchange Rates

Posted: **Fri Dec 28, 2007 1:46 pm**

by **TimeString**

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?

Posted: **Fri Dec 28, 2007 2:42 pm**

by **rio**

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

-----

Rio

Posted: **Fri Dec 28, 2007 2:50 pm**

by **TimeString**

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

Posted: **Fri Dec 28, 2007 3:41 pm**

by **rio**

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

Posted: **Fri Dec 28, 2007 4:04 pm**

by **TimeString**

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 = =||

Posted: **Fri Dec 28, 2007 4:20 pm**

by **rio**

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

Posted: **Sun Dec 30, 2007 8:14 am**

by **TimeString**

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?