Cod sursa(job #65405)

Utilizator scapryConstantin Berzan scapry Data 9 iunie 2007 13:13:40
Problema Loto Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <assert.h>
#include <stdio.h>
#include <bitset>
#include <algorithm>
using namespace std;

enum { maxval = 100000001, maxnumbers = 101 };

int numbers, sum;
int number[maxnumbers];
bitset<3 * maxval> possible;
bool succeeded;
int ans[6];

void go()
{
	int a, b, c;
	int part;
	bool found_one = false, found_two = false;

	for(a = 0; a < numbers; a++)
		for(b = a; b < numbers; b++)
			for(c = b; c < numbers; c++)
				possible[ number[a] + number[b] + number[c] ] = true;

	for(part = max(0, sum - 3 * maxval);
	    part <= sum - part;
	    part++)
		if(possible[part] && possible[sum - part])
		{
			succeeded = true;
			break;
		}

	if(succeeded)
	{
		for(a = 0; a < numbers; a++)
		{
			if(found_one && found_two) break;

			for(b = a; b < numbers; b++)
			{
				if(found_one && found_two) break;

				for(c = b; c < numbers; c++)
				{
					if(found_one && found_two) break;

					if(number[a] + number[b] + number[c] == part)
					{
						ans[0] = number[a];
						ans[1] = number[b];
						ans[2] = number[c];
						found_one = true;
					}
					
					if(number[a] + number[b] + number[c] == sum - part)
					{
						ans[3] = number[a];
						ans[4] = number[b];
						ans[5] = number[c];
						found_two = true;
					}
				}
			}
		}

		assert(found_one && found_two);
	}
}

int main()
{
	int i;
	FILE *f = fopen("loto.in", "r");
	if(!f) return 1;

	fscanf(f, "%d%d", &numbers, &sum);
	for(i = 0; i < numbers; i++)
		fscanf(f, "%d", &number[i]);

	fclose(f);
	f = fopen("loto.out", "w");
	if(!f) return 1;

	go();

	if(succeeded)
		fprintf(f, "%d %d %d %d %d %d\n", ans[0], ans[1], ans[2], ans[3], ans[4], ans[5]);
	else
		fprintf(f, "-1\n");
	fclose(f);
	return 0;
}