624 - CD

[lighted]

Don't read from file

[lolicaddict]

Hello, I keep getting WA
This is my code (I couldn't find any special input):

Any help would be greatly appreciated.

Code: Select all

#include <iostream>
#include <vector>
#include <cstdlib>

using namespace std;

vector <int> tracklist;

int capacity;
int maximum = 0;
int final = 0;

int calculate(int index, int n, int backtrack)
{
	for(int i = index; i < tracklist.size(); i++)
	{
		if(tracklist[i] <= n)
		{
			return max(calculate(i + 1, n - tracklist[i], backtrack|(1<<i)), calculate(i + 1, n, backtrack));
		}
	}

	if(index == tracklist.size())
	{
		if(capacity - maximum >= n)
		{
			final = backtrack;
			maximum = capacity - n;
		}
		return maximum;
	}
}

int main()
{
	int num;
	while(cin >> capacity >> num)
	{
		tracklist.clear();
		maximum = 0;
		final = 0;
		
		for(int i = 0; i < num; i++)
		{
			int temp;
			cin >> temp;
			tracklist.push_back(temp);
		}

		int result = calculate(0, capacity, 0);

		for(int i = 0; i < tracklist.size(); i++)
		{
			if(final&(1<<i))
				cout << tracklist[i] << " ";
		}
		cout << "sum:" << result << endl;
	}
}

[saniatrasel]

Hello, I keep getting WA
This is my code (I couldn't find any special input):

Any help would be greatly appreciated.

Code: Select all

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#define TRACK 25
#define INT_MAX 2147483647
#define SIZE 1000000
int Ans;
int Duration, TrackNo;
int SongDuration[TRACK];

int index_i[TRACK];
int used[TRACK];
int Count;
int stack[SIZE][TRACK];
int playTrackNo;
bool EqualtoDuration;

void readCase()
{
	int i, j;
	for (i = 0; i < TrackNo; i++)
		scanf("%d",&SongDuration[i]);
}



void printCase()
{
	int i, j;
	int sum = 0;
	int MIN_DIFF = INT_MAX;
	int min_index;
	int count = 0;
	int track_no = 0;
	for (i = 0; i < Count; i++)
	{
		for (j = 0; j < TrackNo; j++)
		{
			sum = sum + stack[i][j];
			count++;			
			if (stack[i][j + 1] == 0)
				break;
		}		
		int diff = Duration - sum;
		if (diff >= 0)
		{
			if (MIN_DIFF > diff)
			{
				MIN_DIFF = diff;
				min_index = i;
				track_no = count;
			}		
		}
		count = 0;
		sum = 0;		
	}
	for (i = 0; i < track_no; i++)
	{
		printf("%d ", stack[min_index][i]);
		sum = sum + stack[min_index][i];		
	}
	printf("sum:%d\n",sum);
}

bool storeValue(int n)
{
	int i,j;
	playTrackNo = n;

	bool isExist;
	for (i = 0; i < playTrackNo; i++)
	{
		isExist = false;
		for (j = 1; j <= playTrackNo; j++)
		{
			if (stack[i][j - 1] == SongDuration[index_i[j]])
				isExist = true;
			else
			{
				isExist = false;
				break;
			}
		}
		if (isExist)
			return false;
	}


	for (i = 0; i < playTrackNo;i++)
		stack[Count][i] = SongDuration[index_i[i+1]];
	return true;
}

void solve(int sum,int n)
{
	if (sum > Duration)
		return;
	if (sum <= Duration)
	{
		if(storeValue(n))
			Count++;
		EqualtoDuration = true;		
	}
	int i;
	for (i = index_i[n]; i < TrackNo; i++)
	{
		if (!used[i])
		{
			used[i] = 1;
			index_i[n + 1] = i;
			solve(sum + SongDuration[i], n + 1);
			used[i] = 0;
		}
	}
	
}

void solveCase()
{
	Ans = 0;
	index_i[0] = 0;
	solve(0,0);
}



void resetArray()
{
	int i,j;
	for (i = 0; i < TrackNo; i++)
	{
		used[i] = 0;
		index_i[i] = 0;
	}
	for (i = 0; i < Count; i++)
		memset(stack[i],0,sizeof(stack[i]));
	/*for (i = 0; i < Count; i++)
		for (j = 0; j < TRACK; j++)
			stack[i][j] = -1;		*/
	Count = 0;
	
}

int main()
{
	/*freopen("Text.txt", "r", stdin);
	freopen("Text1.txt", "w", stdout);*/
	while (1)
	{
		scanf("%d %d",&Duration,&TrackNo);
		if (Duration == 0 && TrackNo == 0)
			break;		
		readCase();
		EqualtoDuration = false;
		playTrackNo = 0;
		resetArray();
		solveCase();
		if (EqualtoDuration)
			printCase();		
		Duration = 0;
		TrackNo = 0;
	}	
	return 0;
}

All input are successfully executed from https://www.udebug.com/UVa/624/input
If there is any special input that I am missing please let it share here.

Thanks/
Saniat