## 10201 - Adventures in Moving - Part IV

Moderator: Board moderators

Solmon K.
New poster
Posts: 34
Joined: Sun Jun 04, 2006 4:57 am
Location: Busan, Korea

### 10201 Why WA???

I can't understand why my program is wrong.

Code: Select all

``````removed
``````
Last edited by Solmon K. on Fri Jun 23, 2006 2:24 pm, edited 1 time in total.

OTL
frustrate

Solmon K.
New poster
Posts: 34
Joined: Sun Jun 04, 2006 4:57 am
Location: Busan, Korea

### ...

"tenjegop" is korean name

never mind

OTL
frustrate

Solmon K.
New poster
Posts: 34
Joined: Sun Jun 04, 2006 4:57 am
Location: Busan, Korea

### ...

OTL
frustrate

Solmon K.
New poster
Posts: 34
Joined: Sun Jun 04, 2006 4:57 am
Location: Busan, Korea

### ...

I got AC...

OTL
frustrate

shankar
New poster
Posts: 2
Joined: Thu Jun 07, 2007 9:31 am
Contact:
Can someone tell me about the greedy approach... if possible larry can u explain the greedy approach....

Thank U

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
I am geting RTE here ...
can u help me , why ??

Code: Select all

``````#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

#define INF 999999999

int memo[10005][205];
int D,station[105],price[105];
bool isst[10005];
int pos[10005];
bool flag;

int dp(int dis, int fuel)
{
if(dis>=D) //destination reached
if(fuel>=100)
return 0;
else
if(flag)
return (100-fuel)*price[pos[D]];
else
return INF;

if(fuel<0) //fuel runout
return INF;

if(memo[dis][fuel]!=-1) //cached value
return memo[dis][fuel];

int minx=INF,i,j;//starting point case
if(dis==0)
{
for(i=1;i<=100;i++)
if(isst[dis+i])
{
int p=(dp(dis+i , fuel-i) ) ;
if(p<minx)
minx=p;
}

memo[dis][fuel]=minx;
return minx;
}

for(i=1;i<=200;i++) //other points
if(isst[dis+i])
for(j=0;(j+fuel)<=200;j++)if((fuel-i+j)>=0)
{
int p=( (j*price[pos[dis]]) + dp(dis+i , fuel-i+j) ) ;
if(p<minx)
minx=p;
}

memo[dis][fuel]=minx;
return minx;
}

int main(void)
{
int ks;
scanf("%d",&ks);
char str[50];
int i,j;
gets(str);
//	fflush(stdin);
gets(str);
while(ks--)
{
scanf("%d",&D);
gets(str);
i=0;
for(i=0;i<D;i++)
isst[i]=false;
isst[D]=true;
flag=false;
while(true)
{
gets(str);
if((strcmp(str,""))==0)break;
sscanf(str,"%d%d",&station[i],&price[i]);
isst[station[i]]=true;
pos[station[i]]=i;
if(station[i]==D)
flag=true;
i++;
}
for(i=0;i<=D;i++)
for(j=0;j<=201;j++)
memo[i][j]=-1;

int d=dp(0,100);
if(d==INF)
{
printf("Impossible\n");
}
else
{
printf("%d\n",d);
}
if(ks)
printf("\n");
}
return 0;
}``````
Syed Ishtiaque Ahmed Kallol
CSE,BUET

masque
New poster
Posts: 1
Joined: Wed Nov 11, 2009 4:44 am

### Re: 10201 - Adventures in Moving - Part IV

...I think the input former is disgusting...
why just make it simple...

anybody can help me check out why RE?
I've submitted for nearly 20 times...

Code: Select all

``````#include <iostream>
#include <cstdio>
#define MAXN 11000
#define INF 9999999
using namespace std;
int T,sto[150][2],rec[150][2],N,dp[150][MAXN],limit;
void init(){
for ( int i=0;i<150;i++ ){
for ( int j=0;j<MAXN;j++ ){
dp[i][j]=INF;
}
}
}
int run(){
init();
if ( 100-sto[0][0]<0 ){
return -1;
}else{
dp[0][100]=0;
}
for ( int i=1;i<=N;i++ ){
for ( int j=0;j<=200;j++ ){
if ( j+sto[i][0]<=200 ){
dp[i][j]=dp[i-1][j+sto[i][0]];
}
}
for ( int j=0;j<=200;j++ ){
for ( int k=0;k<j;k++ ){
if ( dp[i][j]>dp[i][k]+( sto[i][1]*( j-k ) ) ){
dp[i][j]=dp[i][k]+( sto[i][1]*( j-k ) );
}
}
}
}
int ans=INF;
int pos;
for ( int i=100;i<=200;i++ ){
if ( ans>dp[N][i] ){
ans=dp[N][i];
pos=i;
}
}
if ( ans>=INF ){
return -1;
}else{
return ans;
}
return ans;
}

int main()
{
scanf( "%d",&T );
getchar();
while ( T-- ){
char ts[500];
gets( ts );
scanf( "%d",&limit );
N=1;
char tmp[500];
getchar();
while ( 1 ){
gets( tmp );
int len=strlen( tmp );
if ( len==0 ){
break;
}
int pos;
for ( int i=0;i<len;i++ ){
if ( tmp[i]==' ' ){
pos=i;
break;
}
}
int t1=0,t2=0;
for ( int i=0;i<pos;i++ ){
t1=t1*10+tmp[i]-'0';
}
for ( int i=pos+1;( tmp[i]>='0'&&tmp[i]<='9' );i++ ){
t2=t2*10+tmp[i]-'0';
}
rec[N][0]=t1,rec[N][1]=t2;
sto[N][0]=t1,sto[N][1]=t2;
N++;
}
for ( int i=N;i>=0;i-- ){
sto[i][0]-=sto[i-1][0];
}
sto[N][0]=limit-rec[N-1][0];
sto[N][1]=INF;
int ans=run();
if ( ans==-1 ){
cout<<"Impossible"<<endl;
}else{
cout<<ans<<endl;
}
cout<<endl;
}

return 0;
}
``````

pdwd
New poster
Posts: 19
Joined: Sat May 15, 2010 4:35 pm

### Re: 10201 - Adventures in Moving - Part IV

I got RE when I didn't consider case in which there are no stations.