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

Post by Kamp » Tue Mar 05, 2002 9:32 pm

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 :sad: Pls help.

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 » Wed Mar 06, 2002 3:35 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:

Post by Kamp » Wed Mar 06, 2002 10:20 pm

Here it goes :smile:

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
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Hi

Post by cyfra » Mon Jun 17, 2002 1:52 pm

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 :wink:

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

Post by Kamp » Fri Jun 21, 2002 5:50 pm

Thanks Cyfra, but pls notice that in the problem description there is said that:
tracks do not repeat
:cry:

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

Post by cyfra » Fri Jun 21, 2002 6:12 pm

Hi

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

Good Luck :wink:

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

I also got WA with DP.

Post by dongyf » Wed Aug 14, 2002 9:00 am

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

Post by Red Scorpion » Tue Feb 04, 2003 4:52 am

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

Post by Red Scorpion » Fri Mar 21, 2003 10:06 am

Ignore this,
I've got AC.
Thanks. :lol: :lol: :lol: :lol:

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

624CD

Post by losskid » Mon Jul 28, 2003 7:23 am

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
New poster
Posts: 18
Joined: Sat May 03, 2003 10:33 pm

Re: Hi

Post by pingus » Sat Mar 27, 2004 12:01 pm

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

Post by junjieliang » Sat Mar 27, 2004 7:43 pm

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

Post by pingus » Sat Mar 27, 2004 8:01 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

Post by helmet » Tue Aug 10, 2004 7:30 am

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

Plz help
Just another brick in the wall...

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

Post by jagadish » Tue Aug 10, 2004 8:08 am

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 ?)

Post Reply

Return to “Volume 6 (600-699)”