Cod sursa(job #66253)

Utilizator scapryConstantin Berzan scapry Data 17 iunie 2007 10:04:44
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <assert.h>
#include <stdio.h>

enum { maxn = 30001, maxval = 1001 };

int n, minlen, maxlen;
int up[maxn],
    down[maxn];
int upm[maxn]; //up modified

int sum[maxn]; //sum upm[0..i]
int best[maxn]; //best sum upm[?..i]

int ans;

bool possible(int value)
{
	int i;

	//avoiding fp numbers
	for(i = 0; i < n; i++)
	{
		upm[i] = up[i] * 100 - value * down[i];

		printf("upm[%d] %d\n", i, upm[i]);
	}
	printf("\n");

	sum[0] = upm[0];
	best[0] = upm[0];
	for(i = 1; i < n; i++)
	{
		sum[i] = upm[i] + sum[i - 1];

		best[i] = upm[i];
		if(best[i - 1] + upm[i] > best[i])
			best[i] = best[i - 1] + upm[i];
	}

	for(i = 0; i < n; i++)
		printf("sum[%d] %d\n", i, sum[i]);
	printf("\n");

	for(i = 0; i < n; i++)
		printf("best[%d] %d\n", i, best[i]);
	printf("\n");

	if(best[minlen - 1] > 0)
		return true;

	//FIXME: what to do with maxlen?
	for(i = minlen; i < n; i++)
	{
		if(sum[i] - sum[i - minlen] >= 0)
			return true;
		if(sum[i] - sum[i - minlen] + best[i - minlen] >= 0)
			return true;
	}

	return false;
}

void go()
{
	int bottom = 0, top = maxval * 100, mid;
	//bottom can't be reached, top can.

	while(true)
	{
		mid = (bottom + top + 1) / 2;

		bool ans = possible(mid);

		printf("bottom %d top %d mid %d possible %d\n",
				bottom, top, mid, ans);

		if(mid == top) break;

		if(ans) //maybe this one, maybe a bigger one
			bottom = mid;
		else //surely a smaller one
			top = mid - 1;
	}

	ans = mid;
}

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

	fscanf(f, "%d%d%d", &n, &minlen, &maxlen);

	for(i = 0; i < n; i++)
		fscanf(f, "%d", &up[i]);

	for(i = 0; i < n; i++)
		fscanf(f, "%d", &down[i]);

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

	go();

	fprintf(f, "%d.%02d\n", ans / 100, ans % 100);
	fclose(f);
	return 0;
}