## 624 - CD

All about problems in Volume 6. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Kamp
New poster
Posts: 18
Joined: Tue Mar 05, 2002 2:00 am
Location: Poland (3-city)
Contact:

### 624 - CD

I have some problems with problem number 624 "CD". I made it using dynamic programming and it should give good answer, but still I have WA Pls help.

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
It is hard to help without details and without code. Can you describe your algorithm?

Kamp
New poster
Posts: 18
Joined: Tue Mar 05, 2002 2:00 am
Location: Poland (3-city)
Contact:
Here it goes

program hiszpania624(input,output);
var
w,i,j,n,tracks:longint;
tab,Q:array[1..20,-1..1000]of longint;
cos:array[1..2,1..20]of longint;

begin
repeat
if tracks>0 then begin
for i:=1 to tracks do
begin
for j:=1 to n do
begin
tab[i,j]:=0;
end;
end;
for j:=1 to 20 do
begin
cos[1,j]:=0;
cos[2,j]:=0;
end;
for i:=1 to tracks do
begin
cos[1,i]:=tab[i,-1];
end;
for i:=tab[1,-1] to n do
begin
tab[1,i]:=tab[1,-1];
q[1,i]:=1;
end;

for i:=2 to tracks do
begin
for j:=1 to n do
begin
if (j>=tab[i,-1]) then
begin
if (tab[i-1,j]<tab[i-1,j-tab[i,-1]]+tab[i,-1])and(j-tab[i,-1]>-1) then
begin
tab[i,j]:=tab[i-1,j-tab[i,-1]]+tab[i,-1];
Q[i,j]:=1;
end
else
begin
tab[i,j]:=tab[i-1,j];
q[i,j]:=0;
end;
end
else
begin
tab[i,j]:=tab[i-1,j];
q[i,j]:=0;
end;
end;
end;
i:=tracks;j:=n;
while i<>0 do
begin
if q[i,j]=1 then
begin
w:=1;
while cos[1,w]<>tab[i,-1] do w:=w+1;
cos[2,w]:=1;
j:=j-tab[i,-1];
end;
i:=i-1;
end;
for i:=1 to tracks do
if cos[2,i]=1 then write(output,cos[1,i],' ');
writeln(output,'sum:',tab[tracks,n]);
end
else
writeln(output,'sum:0');
until eof(input);
end.

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

### Hi

Hi!

I found a bug in your program...

Try to test it with this test data :
10 4 1 3 2 1
The output should be :
1 3 2 1 sum:8
but your program gives :
1 3 2 sum:7
Change it and try to submit it again...

Good Luck

Kamp
New poster
Posts: 18
Joined: Tue Mar 05, 2002 2:00 am
Location: Poland (3-city)
Contact:
Thanks Cyfra, but pls notice that in the problem description there is said that:
tracks do not repeat

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland
Hi

I know but I wonder if it means that their length does not repeat

Good Luck

dongyf
New poster
Posts: 4
Joined: Thu Jun 13, 2002 5:12 pm

### I also got WA with DP.

Code: Select all

``````#include <iostream>
#include <cstring>
using namespace std;

const int maxsize = 1000;
int space, num;
int track[maxsize+1];
int record[maxsize+1];
int last[maxsize+1];

bool getcase()
{
if (cin >> space) {
cin >> num;
for (int i = 1; i <= num; i++)
cin >> track[i];

return true;
}
else
return false;
}

void show(int p)
{
if (p == 0)
return;

show(last[p]);
cout << track[p] << " ";
}

void solve()
{
int i, j, k, max;

record[0] = 0;
last[0] = 0;
for (i = 1; i <= num; i++) {
max = 0;
k = 0;
for (j = 0; j <= i - 1; j++)
if (record[j] + track[i] <= space && record[j] + track[i] > max) {
max = record[j] + track[i];
last[i] = j;
}
record[i] = max;
}

max = 0;
j = 0
for (i = 1; i <= num; i++)
if (record[i] > max) {
max = record[i];
j = i;
}

show(j);
cout << "sum:" << max << endl;
}

void main()
{
while (getcase())
solve();
}
``````

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

### 624

Code: Select all

``Hai,``
I am trying to solved this Prob,

*******************************************
Cut.
****************************************
How, If the Sample input :
1 1 0

My output :
0 sum:0

Please , Help me.

Regards,
RS.
Last edited by Red Scorpion on Fri Mar 21, 2003 10:08 am, edited 1 time in total.

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

### Re: P 624-Need test Case

Ignore this,
I've got AC.
Thanks.

losskid
New poster
Posts: 3
Joined: Mon Jul 28, 2003 7:13 am

### 624CD

i cannot find what is wrong with my code
#include <iostream>
#include <math.h>
using namespace std;

const int maxLen = 1000;
int m[maxLen][maxLen];
int nMusic;
int Vtape;
int VMusic[maxLen];
int x[maxLen];

int max(int a,int b)
{
if (a>b)
return a;
else
return b;
}

void solve()
{
int i,j;

for (j = 0; j<=Vtape; j++)
{
if (j>=VMusic[nMusic])
m[nMusic][j] = VMusic[nMusic];
else
m[nMusic][j] = 0;
}
for (i = nMusic-1;i>=1;i--)
{
for (j = 0;j<=Vtape;j++)
{
if (j>=VMusic)
m[j] = max(m[i+1][j],m[i+1][j-VMusic]+VMusic);
else
m[j] = m[i+1][j];
}
}
}

void back()
{
for (int i = 1;i<=nMusic;i++)
{
if (m[Vtape]!=m[i+1][Vtape])
{
cout << VMusic << ' ';
Vtape-=VMusic;
}
}
}

int main()
{
while (cin>>Vtape>>nMusic)
{
for (int i = 1;i<=nMusic;i++)
cin >> VMusic;
solve();
back();
cout <<"sum:"<< answer << endl;
}
return 0;
}

pingus
New poster
Posts: 18
Joined: Sat May 03, 2003 10:33 pm

### Re: Hi

Hello

One question cyfra ?

Why for input data
10 4 1 3 2 1

The output should be :
1 3 2 1 sum:8

and not
1 3 2 1 sum:7
thx

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore
I think it should be "1 3 2 1 sum: 7", but cyfra had a typo. Btw, the way I see it "tracks do not repeat" does not mean the length, just that you cannot use the same track more than once.

pingus
New poster
Posts: 18
Joined: Sat May 03, 2003 10:33 pm
Ok, Do you have some idea why this goes WA ?

[c]#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

int N, n, min, m;
int a[32];
char v[32];
char r[32];

void save()
{
for(int i = 0; i <n; i++)
r = v;
}

void doit(int pos, int s, int add)
{
int i;

if (m < s)
{
min = N - add;
m = s;
save();
}
else
if ((m == s) && (N - add < min))
{
min = N - add;
save();
}

for(i = pos; i < n; i++)
if (add <= N - a)
{
v = 1;
doit(i + 1, s + 1, add + a);
v = 0;
}

return;
}

main()
{
int i;
for(;;)
{
if (scanf("%i", &N) != 1) break;
scanf("%i",&n);
for(i = 0; i < n; i++) scanf("%i", &a);
for(i = 0; i < n; i++) r = v = 0;

min = N;
m = 0;
doit(0,0,0);

for(i = 0; i < n; i++)
if (r == 1) printf("%i ", a[i]);

printf("sum:%i\n",N - min);

}

}[/c]
Thx

helmet
New poster
Posts: 31
Joined: Tue Mar 02, 2004 11:55 am

### 624 CD

Hi I keep on getting WA...any tricks here?

Plz help
Just another brick in the wall...