## 10086 - Test the Rods

Moderator: Board moderators

Andrey Popyk
New poster
Posts: 6
Joined: Wed Jan 16, 2002 2:00 am
Location: Ukraine
Contact:

### 10086 - Test the Rods

Code: Select all

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

#define DIM 307
#define oo 2000000000L

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

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

zyc
New poster
Posts: 2
Joined: Sat Nov 16, 2002 6:07 am
for(k=0;k<=p;k++)
need another condition k<=a[1]+a[2]+...+a[i-1]
if you add it , it is ok!

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

### Re: 10086 - Test the Rods

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 :*
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

crip121
New poster
Posts: 29
Joined: Tue Jul 08, 2008 9:04 pm

### Re: 10086 - Test the Rods

its a DP problem...

@li_kuet
New poster
Posts: 44
Joined: Fri May 25, 2012 6:22 pm

### Re: 10086 - Test the Rods

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

New poster
Posts: 17
Joined: Thu Jul 03, 2014 11:13 am

### Re: 10086 - Test the Rods

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[25];int C[50][50][2];
int memo[50][310][310];
int trace[50][310][310];
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][0];
if(j==0) sum2=0;
else sum2=C[idx][j-1][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][0]);
for(int j=0;j<m[i];j++) scanf("%d",&C[i][j][1]);
}
memset(memo,-1,sizeof memo);
memset(trace,-1,sizeof trace);
int val=TesttheRods(0,T1,T2);
printf("%d\n",val);
printf("%d",trace[0][T1][T2]);
int ind1=trace[0][T1][T2];
int ind2=m[0]-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;
}

``````
Last edited by bradd123 on Thu Feb 19, 2015 2:14 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10086 - Test the Rods

return 0;
Check input and AC output for thousands of problems on uDebug!

New poster
Posts: 17
Joined: Thu Jul 03, 2014 11:13 am

### Re: 10086 - Test the Rods

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10086 - Test the Rods

Try changing int m[25] to int m[30]
Check input and AC output for thousands of problems on uDebug!

New poster
Posts: 17
Joined: Thu Jul 03, 2014 11:13 am

### Re: 10086 - Test the Rods

It worked for RE Error. But Now I am getting Time LImit Exceeded. How to improve this solution.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10086 - Test the Rods

My algorithm AC in 0.072 seconds.

My variables:
int m[30];
int m_sum[31]; //m_sum[0] is always 0.
int C[30][21][2]; //C[x][0][y] is always 0. I use x and y here to mean any valid integer
int dp[31][301]; //dp[j] is the minimum cost to build a total of j rods at NCPC after considering site i.
int p[31][301]; //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.