## 624 - CD

Moderator: Board moderators

toni
New poster
Posts: 7
Joined: Wed Jul 25, 2007 6:03 pm
thanks Jan again ! your test cases is very helpful. I indeed ignore to initialized the array ithenewguyi
New poster
Posts: 5
Joined: Tue Nov 20, 2007 11:27 pm
Sample Input

5 3 1 3 4
10 4 9 8 4 2
20 4 10 5 7 4
90 8 10 23 1 2 3 4 5 7
45 8 4 10 44 43 12 9 8 2

Sample Output

1 4 sum:5
8 2 sum:10
10 5 4 sum:19
10 23 1 2 3 4 5 7 sum:55
4 10 12 9 8 2 sum:45
that was straight from the site, the output should be sorted right? because the sample output isnt sorted..... DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:
This problem has a special correction program. It's ok to output any correct solution. (At this time, the new site does not show the information about the special judgement.)
WingletE
New poster
Posts: 35
Joined: Sun Aug 13, 2006 1:34 pm
Location: Taipei, Taiwan
Contact:

### N

I assumed N <= 5000 and got AC.
jknisely
New poster
Posts: 2
Joined: Tue Sep 16, 2008 6:35 pm

### Getting RE from the judge

I am getting a RE from the judge. My code solves all the inputs listed on this thread, but it does not handle negative track lengths. Does anyone know if that is necessary? I am posting my code below.

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>
/* used to indicate which tracks are used for each possible solution */
unsigned int codes[] = { 0x80000, 0x40000, 0x20000, 0x10000, 0x8000, 0x4000, 0x2000, 0x1000, 0x800, 0x400, 0x200, 0x100, 0x80, 0x40, 0x20, 0x10, 0x8, 0x4, 0x2, 0x1};

int main() {
unsigned int code, k,n, nTapeLength, nTracks;
unsigned int tracks;
unsigned int *sols;
unsigned int nMaxFound;

while (2 == scanf("%u %u", &nTapeLength, &nTracks)) {
if (0 == nTracks) {
puts("sum:0");
continue;
}
sols = (unsigned int *)calloc(nTapeLength+1, sizeof(unsigned int));
scanf("%u", tracks);
nMaxFound = tracks;
sols[tracks] = codes;

for (n=1; n < nTracks; ++n) {
scanf("%u", tracks+n);
for (k=nMaxFound; k > 0; --k) {
if (sols[k] > 0 && k+tracks[n] <= nTapeLength) {
code = sols[k] | codes[n];
if (sols[k+tracks[n]] < code) {
sols[k+tracks[n]] = code;
if (nMaxFound < k+tracks[n]) { nMaxFound = k+tracks[n]; }
} /* end of if a better solution was found */
} /* end of if a solution was found */
} /* end of for each possible solution */

code = codes[n];
if (sols[tracks[n]] < code) {
sols[tracks[n]] = code;
if (nMaxFound < tracks[n]) { nMaxFound = tracks[n]; }
}
} /* end of for each number which needs to be read */

for (n=nTapeLength; !sols[n]; --n) { ; }
for (k=0; k < 20; ++k) {
if (sols[n] & codes[k]) { printf("%u ", tracks[k]); }
}
printf("sum:%u\n", n);
free(sols);
}
}

``````
Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

### Re: N

WingletE wrote:I assumed N <= 5000 and got AC.
I assumed N <= 2000 and got AC. ryen
New poster
Posts: 5
Joined: Mon Feb 01, 2010 6:25 pm

### Re: Get WA, Need Help!!!

Could anybody help me? I've passed all the test case in this post, but still get WA. I use dp and assumu N < 20000
here is my code.

Code: Select all

``````#include <stdio.h>
#include <string.h>

int track;
int N,cnt;
int d;

int dp(int cur, int s)
{
int& ans = d[cur][s];
if(ans)return ans;

if(s == cnt) return 0;

for(int i = s; i < cnt; i++)
{
if(cur >= track[i])
{
int t = dp(cur-track[i], i+1) + track[i];
if(t > ans)ans = t;
}
}
return ans;
}

int main()
{
while(scanf("%d%d", &N, &cnt) != EOF)
{
for(int i = 0; i < cnt; i++)
{
scanf("%d", &track[i]);
}
memset(d, 0, sizeof(d));

dp(N,0);
int cur = N;
for(int i = 0; i < cnt-1; i++)
{
for(int j = i; j < cnt; j++)
{
if(cur >= track[j])
{
if(d[cur][i] - d[cur-track[j]][j+1] == track[j])
{
printf("%d ",track[j]);
cur = cur - track[j];
}
}
}
}
if(cur >= track[cnt-1])printf("%d ", track[cnt-1]); // check the last
printf("sum:%d\n", d[N]);
}
return 0;
}``````
ryen
New poster
Posts: 5
Joined: Mon Feb 01, 2010 6:25 pm

### Re: 624 - CD

could somebody give some more critical I/O? I just cannot find where am wrong!
qwerty
New poster
Posts: 21
Joined: Sun Feb 08, 2009 5:26 pm
Location: Mumbai,India

### Re: 624 - CD

i also passed all i/o of the board but still wa.no idea what's wrong.some hints plz.here my code

Code: Select all

``````ac
``````
i was using less arraysize.finally changed my approach to dp Last edited by qwerty on Wed Jul 27, 2011 12:52 pm, edited 1 time in total.
qwerty
New poster
Posts: 21
Joined: Sun Feb 08, 2009 5:26 pm
Location: Mumbai,India

### Re: 624 - CD

ok here is a question which sequence is better

20 7
or
15 5 7
oys135
New poster
Posts: 1
Joined: Fri Mar 26, 2010 1:51 pm

### I got WA. Somebody help me plz~

Hello, this is my code. I've read all the posts about 624, but I still can't find where my problem is. I sent this code and got WA. Would you please help me find where My code is wrong? Thank you very much!

#include <iostream>

using namespace std;

class Depth{
private :
int n;
int P;
int maxprofit;
int *p;
bool bestset;
bool include;
public :
void start(int n, int P, int *p);
void knapsack(int i, int profit);
bool promising(int i, int profit);
void display(void);
};

void bubble(int *p, int n);

int main(void)
{
int i, n, P, p;
Depth depth;

while(1) {
cin >> P;
if(cin.eof())
break;

cin >> n;

for(i=1; i <= n; i++) {
cin >> p;
}
bubble(p, n);

depth.start(n, P, p);
depth.display();
}

return 0;
}

/***************************************************/
/* Depth-first Search (Backtracking) */
/***************************************************/
void Depth::start(int nN, int nP, int *np)
{
n = nN;
P = nP;
p = np;
maxprofit = 0;

knapsack(0, 0);
}

void Depth::knapsack(int i, int profit)
{
if(profit<=P && profit > maxprofit) {
maxprofit = profit;
for(int j=1; j<=n; j++)
bestset[j] = include[j];
}

if(promising(i, profit)) {
include[i+1] = true;
knapsack(i+1, profit+p[i+1]);
include[i+1] = false;
knapsack(i+1, profit);
}
}

bool Depth::promising(int i, int profit)
{
int j;
int bound;

if(profit >= P)
return false;
else {
j = i+1;
bound = profit;
while((j <= n) && (bound+p[j] <= P)) {
bound = bound + p[j];
j++;
}

if(j <= n)
bound += (P - bound);

return bound > maxprofit;
}
}

void Depth::display()
{
int i;

for(i=1; i<=n; i++) {
if(bestset == true){
cout << p << " ";
}
}
cout << "sum:" << maxprofit << endl;
}

void bubble(int *p, int n)
{
int i, j, tmp;
for(i=n-1; i>=0; i--) {
for(j=1; j<=i ; j++) {
if(p[j] > p[j+1]) {
tmp = p[j];
p[j] = p[j+1];
p[j+1] = tmp;
}
}
}
}
amishera
New poster
Posts: 38
Joined: Sat Dec 27, 2008 10:42 pm

### Re: 624 - CD

For the sample input/ouput sequence:

45 8 4 10 44 43 12 9 8 2

why is the solution not

43 2?

I tested this sequence (the permutation of the above):

45 8 43 2 4 10 44 12 9 8

with

http://uvatoolkit.com/problemssolve.php

and the output is coming out as

43 2
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Contact:

### Re: 624 - CD

In fact, in this problem the number of track used is not important,the main thing is to maximize used space.So

Code: Select all

``````for input
45 8 4 10 44 43 12 9 8 2

output 1: 4 10 12 9 8 2 sum:45
output 2:43 2 sum:45

Both are correct.

``````
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
solon_aguiar
New poster
Posts: 7
Joined: Mon Jun 08, 2009 11:16 pm

### Re: 624 - CD

Hello guys,

I've searched on all inputs and outputs available here. My code seems to work on all of them, but I still get RE. Can you guys help me?
I'm using 0/1 knapsack.
Thank you very much

Code: Select all

``````#include <cstdio>
#include <algorithm>
#define MAX 20000

using namespace std;

long long tracks[MAX], resp[MAX];
long long current, N, n_tracks, sum, tam;
long long tab[MAX][MAX];

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

long long print(long long n, long long W){
long long indiceAtual = 0;
long long linhaAtual = n;
long long colunaAtual = W;
while(linhaAtual != 0 && colunaAtual != 0){
int num = tab[linhaAtual][colunaAtual];
int sup = tab[linhaAtual - 1][colunaAtual];
if(num == sup){
linhaAtual--;
}else{
resp[indiceAtual] = tracks[linhaAtual - 1];
indiceAtual++;
colunaAtual = colunaAtual - tracks[linhaAtual - 1];
linhaAtual--;
}
}
return indiceAtual;
}

long long custo(long long n, long long W){
for(long long i = 0; i <= n; i++)
tab[i] = 0;
for(long long i = 0; i <= W; i++)
tab[i] = 0;
for(long long i = 1; i <= n; i++){
for(long long j = 1; j <= W; j++){
if(tracks[i - 1] > j){
tab[i][j] = tab[i-1][j];
}else{
tab[i][j] = max(tab[i-1][j], tracks[i - 1] + tab[i-1][j - tracks[i - 1]]);
}
}
}
return tab[n][W];
}

int main(){
while(scanf("%lld", &N)!=EOF){
scanf("%lld", &n_tracks);
sum = 0;
for(long long i = 0; i < n_tracks; i++){
scanf("%lld", &current);
tracks[i] = current;
}
//sort(tracks, tracks + n_tracks + 2);
sum = custo(n_tracks, N);
tam = print(n_tracks, N);
for(long long i = tam - 1; i >= 0; i--)
printf("%lld ", resp[i]);
printf("sum:%lld\n", sum);
}
return 0;
}
``````
Bidhan
New poster
Posts: 6
Joined: Mon May 17, 2010 5:07 pm
Contact:

### Re: 624 - CD

N will not exceed 5000.
Can be solved by 0-1 Knapsack/Coin Change/Backtrack.
Any correct output is acceptable. My output for the sample was

Code: Select all

``````1 4 sum:5
8 2 sum:10
10 5 4 sum:19
10 23 1 2 3 4 5 7 sum:55
43 2 sum:45``````