624 - CD

[toni]

thanks Jan again ! your test cases is very helpful. I indeed ignore to initialized the array

[ithenewguyi]

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]

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]

I assumed N <= 5000 and got AC.

[jknisely]

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[20];
    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[0];
        sols[tracks[0]] = codes[0];
        
        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]

I assumed N <= 5000 and got AC.

I assumed N <= 2000 and got AC.

[ryen]

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[21];
int N,cnt;
int d[20000][21];

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;
		// print answer
		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][0]);
	}
	return 0; 
}

[ryen]

could somebody give some more critical I/O? I just cannot find where am wrong!

[qwerty]

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

[qwerty]

ok here is a question which sequence is better

20 7
or
15 5 7

[oys135]

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[21];
bool include[21];
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[21];
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]

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

[sazzadcsedu]

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.

[solon_aguiar]

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] = 0;
    for(long long i = 0; i <= W; i++)
        tab[0][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]

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