Cod sursa(job #61399)

Utilizator risenshineAkil Nasser risenshine Data 19 mai 2007 12:03:57
Problema Loto Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <stdio.h>

int N, S;
int a[100], m, b[3][5000], p, c[3][12500000];
int x, pos;

int bsearch(int p, int q) {
	if (p <= q) {
		int m = (p + q) / 2;
		if (c[0][m] == x)
			return m;
		else if (c[0][m] > x)
			return bsearch(p, m-1);
		else
			return bsearch(m+1, q);
	}
	else
		return -1;
}
int main() {
	FILE *fi = freopen("loto.in", "r", stdin);
	//FILE *fo = freopen("loto.out", "w", stdout);
	int i, j;
	scanf("%d%d", &N, &S);
	for (i = 0; i < N; ++i)
		scanf("%d", &a[i]);
	for (i = 0; i < N; ++i)
		for (j = i; j < N; ++j) {
			b[0][m] = a[i] + a[j];
			b[1][m] = a[i], b[2][m] = a[j], ++m;
		}
	for (i = 0; i < m; ++i)
		for (j = i; j < m; ++j) {
			c[0][p] = b[0][i] + b[0][j];
			c[1][p] = i, c[2][p] = j, ++p;
		}
	for (i = 0; i < m; ++i) {
		x = S - b[0][i];
		if (x > 0) {
			pos = bsearch(0, p-1);
			if (pos != -1) {
				printf("%d %d ", b[1][i], b[2][i]);
				printf("%d %d %d %d\n", b[1][c[1][pos]], b[2][c[1][pos]], b[1][c[2][pos]], b[2][c[2][pos]]); 
				break;			
			}
		}
		else {
			printf("-1\n");
			break;
		}
	}
	/*x = 7;
	pos = bsearch(0, p-1);
	printf("%d %d\n", b[2][5], c[2][19]);
	for (i = 0; i < m; ++i)
		printf("%d ", b[0][i]);
	printf("\n");
	for (i = 0; i < p; ++i)
		printf("%d ", c[0][i]);*/
	return 0;
}