624 - CD
Moderator: Board moderators
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.
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.
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.
Hi
Hi!
I found a bug in your program...
Try to test it with this test data :
Good Luck
I found a bug in your program...
Try to test it with this test data :
The output should be :10 4 1 3 2 1
but your program gives :1 3 2 1 sum:8
Change it and try to submit it again...1 3 2 sum:7
Good Luck
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();
}
-
- Experienced poster
- Posts: 192
- Joined: Sat Nov 30, 2002 5:14 am
624
Code: Select all
Hai,
*******************************************
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.
-
- 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.
I've got AC.
Thanks.
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 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;
}
#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;
}
-
- Experienced poster
- Posts: 169
- Joined: Wed Oct 31, 2001 2:00 am
- Location: Singapore
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
[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