Page 1 of 1

### 10086 - Test the Rods

Posted: Thu Oct 03, 2002 1:55 pm

Code: Select all

``````#include <iostream.h>

#define DIM 307
#define oo 2000000000L

long N,T1,T2;
long A;
int B[DIM],C[DIM];
long D[DIM];
int R[DIM];
int Res;

{ long i,j;
cin>>T1>>T2;
if(T1==0 && T2==0) return 0;
cin>>N;
for(i=1;i<=N;i++)
{
cin>>A[i];
for(j=1;j<=A[i];j++) cin>>B[i][j];
for(j=1;j<=A[i];j++) cin>>C[i][j];
}
return 1;
}

void Solve()
{ long s,k,p,i,j;
for(i=0;i<33;i++)
for(j=0;j<DIM;j++) D[i][j]=0;
s=0;
for(i=1;i<=N;i++)
{ s+=A[i];
for(j=0;j<=T1;j++)
{ D[i][j]=oo;
p=j; if(A[i]<j) p=A[i];
for(k=0;k<=p;k++)
if(D[i][j]>D[i-1][j-k]+B[i][k]+C[i][A[i]-k])
{
D[i][j] = D[i-1][j-k]+B[i][k]+C[i][A[i]-k];
R[i][j] = k;
}
}
}
cout<<D[N][T1]<<endl;
p=T1;
for(i=N;i>=1;i--)
{ Res[i]=R[i][p];
p=p-R[i][p];
}
for(i=1;i<=N;i++) cout<<Res[i]<<' ';
cout<<endl<<endl;
}

int main()
{
return 0;
}
``````

Posted: Wed Nov 27, 2002 9:32 am
for(k=0;k<=p;k++)
need another condition k<=a+a+...+a[i-1]
if you add it , it is ok!

### Re: 10086 - Test the Rods

Posted: Fri Oct 08, 2010 7:03 pm
HI alll could somebody help me ...
whats The underlying algorithm ...
how to solve this problem ...
i'll be glad if any one could help ....
Thanks :*

### Re: 10086 - Test the Rods

Posted: Thu Oct 14, 2010 12:38 am
its a DP problem...

### Re: 10086 - Test the Rods

Posted: Tue Feb 11, 2014 10:46 pm
What is wrong with my code ??
Any tricky case ??

Code: Select all

``````AC
Can try this input who r getting WA

Code: Select all

``````5 0
1
5
10 20 30 20 50
40 25 10 50 20``````
Output : 50

### Re: 10086 - Test the Rods

Posted: Wed Feb 18, 2015 11:02 am
Hi, Can anyone tell me why my code shows RE for this problem.

Code: Select all

``````#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF 2000000000
int T1,T2,n;
int m;int C;
int memo;
int trace;
int TesttheRods(int idx,int rem1,int rem2){
if(idx>=n){
if(rem1==0&&rem2==0) return 0;
else return INF;
}
if(rem1==0&&rem2==0) return INF;
if(rem1<0||rem2<0) return INF;
if(memo[idx][rem1][rem2]!=-1) return memo[idx][rem1][rem2];
int tmp=INF;
for(int i=0;i<=m[idx];i++){
int j=m[idx]-i;
int sum1=0,sum2=0;
if(i==0) sum1=0;
else sum1=C[idx][i-1];
if(j==0) sum2=0;
else sum2=C[idx][j-1];
int tmpvalue=((TesttheRods(idx+1,rem1-i,rem2-j))+sum1+sum2);
if(tmpvalue<tmp){
tmp=tmpvalue;
trace[idx][rem1][rem2]=i;
}
}
return memo[idx][rem1][rem2]=tmp;
}
int main()
{
//freopen("in.txt","r",stdin);
while(scanf("%d %d",&T1,&T2)){
if(T1==0&&T2==0) break;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&m[i]);
for(int j=0;j<m[i];j++) scanf("%d",&C[i][j]);
for(int j=0;j<m[i];j++) scanf("%d",&C[i][j]);
}
memset(memo,-1,sizeof memo);
memset(trace,-1,sizeof trace);
int val=TesttheRods(0,T1,T2);
printf("%d\n",val);
printf("%d",trace[T1][T2]);
int ind1=trace[T1][T2];
int ind2=m-ind1;
int total1=T1,total2=T2;
for(int i=1;i<n;i++){
total1-=ind1;total2-=ind2;
ind1=trace[i][total1][total2];
ind2=m[i]-ind1;
printf(" %d",ind1);
}
printf("\n");
printf("\n");
}
return 0;
}

``````

### Re: 10086 - Test the Rods

Posted: Wed Feb 18, 2015 9:30 pm
return 0;

### Re: 10086 - Test the Rods

Posted: Thu Feb 19, 2015 2:12 pm
@Brianfry713 : I added return 0; to the program Still It shows RE. Could you please tell me any other mistakes. I think it is out of bounds error. But I couldn't find it. Please Give me some test cases.

### Re: 10086 - Test the Rods

Posted: Thu Feb 19, 2015 10:58 pm
Try changing int m to int m

### Re: 10086 - Test the Rods

Posted: Fri Feb 20, 2015 11:46 am
It worked for RE Error. But Now I am getting Time LImit Exceeded. How to improve this solution.

### Re: 10086 - Test the Rods

Posted: Wed Feb 25, 2015 10:33 pm
My algorithm AC in 0.072 seconds.

My variables:
int m;
int m_sum; //m_sum is always 0.
int C; //C[x][y] is always 0. I use x and y here to mean any valid integer
int dp; //dp[j] is the minimum cost to build a total of j rods at NCPC after considering site i.
int p; //each time you update dp[j], p[j] = k indicates that dp[k] was used. This is needed for the second line of the output.