
624 - CD
Moderator: Board moderators
-
- New poster
- Posts: 5
- Joined: Tue Nov 20, 2007 11:27 pm
that was straight from the site, the output should be sorted right? because the sample output isnt sorted.....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

N
I assumed N <= 5000 and got AC.
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[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);
}
}
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.
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;
}
Re: 624 - CD
could somebody give some more critical I/O? I just cannot find where am wrong!
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
i was using less arraysize.finally changed my approach to dp 
Code: Select all
ac

Last edited by qwerty on Wed Jul 27, 2011 12:52 pm, edited 1 time in total.
Re: 624 - CD
ok here is a question which sequence is better
20 7
or
15 5 7
20 7
or
15 5 7
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[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;
}
}
}
}
#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;
}
}
}
}
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
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
- Location: narayangong,bangladesh.
- 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
For Hints: http://salimsazzad.wordpress.com
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com
-
- 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
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", ¤t);
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;
}
-
- New poster
- Posts: 6
- Joined: Mon May 17, 2010 5:07 pm
- Location: University Of Dhaka, Bangladesh.
- 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
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