Pagini recente » Cod sursa (job #1854159) | Cod sursa (job #858447) | Cod sursa (job #2236273) | Cod sursa (job #956953) | Cod sursa (job #116763)
Cod sursa(job #116763)
Utilizator |
Andrei 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;
}