Cod sursa(job #116763)

Utilizator wefgefAndrei Grigorean wefgef Data 19 decembrie 2007 14:40:40
Problema Bile2 Scor Ascuns
Compilator cpp Status done
Runda Marime 1.59 kb
#include <stdio.h>

int N, D;
int A, B;

inline long long GCD( long long A, long long B )
{
	for (; A % B; )
	{
		long long C = A % B;
		A = B;
		B = C;
	}
	return B;
}

class fractie
{
public:
	long long X, Y;

	fractie() { X = 0; Y = 1;}
	fractie( long long x, long long y )
	{
		X = x; Y = y;
		fixme();
       	}

	void fixme()
	{
		long long gcd = GCD(X, Y);
		X /= gcd; Y /= gcd;
	}

	fractie operator = ( const fractie &B )
	{
		X = B.X; Y = B.Y;
		return (*this);
	}

	fractie operator * ( const fractie &B )
	{
		return fractie( X * B.X, Y * B.Y );
	}

	fractie operator + ( const fractie &B )
	{
		if (Y == B.Y)
			return fractie( X + B.X, Y );
		return fractie( X * B.Y + B.X * Y, Y * B.Y );
	}

	int operator < ( const fractie &B )
	{
		return (X * B.Y) < (B.X * Y);
	}
};

#define MAXN 1024
fractie Prob[2][MAXN], ProbA[2][MAXN], CMP;

int main()
{
	freopen("bile2.in", "rt", stdin);
	freopen("bile2.out", "wt", stdout);

	scanf("%d %d", &N, &D);
	scanf("%d %d", &A, &B);
	CMP = fractie(A, B);

	for (int i = 1; i <= N; i++)
	{
		Prob[1][i]  = fractie(1, N),
		ProbA[1][i] = fractie(N - i + 1, N);
	}

	int step = 0;
	for (int i = 2; i <= N; i++, step ^= 1)
	{
		for (int j = N; j >= 1; j--)
		{
			Prob[step][j] = ProbA[1 ^ step][j + D + 1] * fractie(i, N - i + 1);

			ProbA[step][j] = Prob[step][j];
			if (j < N)
				ProbA[step][j] = ProbA[step][j] + ProbA[step][j + 1];
		}

		fractie tmp = ProbA[step][1];
		tmp.X = tmp.Y - tmp.X;
		if (!(tmp < CMP))
		{
			printf("%d\n", i);
			return 0;
		}
	}

	return 0;
}