624 - CD

[Kamp]

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]

It is hard to help without details and without code. Can you describe your algorithm?

[Kamp]

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
read(input,n);
read(input,tracks);
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
read(input,tab[i,-1]);
cos[1,i]:=tab[i,-1];
end;
readln(input);
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]

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]

Thanks Cyfra, but pls notice that in the problem description there is said that:

tracks do not repeat

[cyfra]

Hi

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

Good Luck

[dongyf]

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]

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.

[Red Scorpion]

Ignore this,
I've got AC.
Thanks.

[losskid]

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

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];
}
}
answer = m[1][Vtape];
}

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]

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]

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]

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]

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

Plz help

[jagadish]

even i am getting WA for quite some time..
as far i see its just a special case of 0/1 knapsack where value=weight of each object.
the problem doesnt specify the upper limit for N.(is it <2^32 ?)