10201 - Adventures in Moving - Part IV

[Solmon K.]

I can't understand why my program is wrong.

Code: Select all

removed

[Solmon K.]

"tenjegop" is korean name

never mind

[Solmon K.]

Someone please reply...

[Solmon K.]

Why nobody reply???

I got AC...

[shankar]

Can someone tell me about the greedy approach... if possible larry can u explain the greedy approach....

Thank U

[Kallol]

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

[masque]

...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]

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

[Jehad Uddin]

@masque , your dp state [150][11000]is too high for the problem
try to decrease it , it can be solved in [100][200]