Pagini recente » Cod sursa (job #1452746) | Cod sursa (job #2039489) | Cod sursa (job #2495594) | Cod sursa (job #381042) | Cod sursa (job #2224224)
/**
* Worg
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
FILE *fin = freopen("bile2.in", "r", stdin); FILE *fout = freopen("bile2.out", "w", stdout);
const int MAX_N = 1000 + 5;
const int MAX_SIZE = 120;
const int BASE = 1e9;
const int BASE_DIGITS = 9;
class Huge {
public:
int a[MAX_SIZE];
int size;
void Reset() {
memset(a, 0, sizeof(a));
size = 1;
}
Huge() {
Reset();
}
void SetValue(long long value) {
Reset();
do {
a[++size] = value % BASE;
value /= BASE;
}while(value != 0);
}
void operator = (const Huge &other) {
this->size = other.size;
for(int i = 1; i < MAX_SIZE; i++) {
this->a[i] = other.a[i];
}
}
void operator *= (long long value) {
long long i, t;
for(i = 1, t = 0; i <= size || t != 0; i++, t /= BASE) {
a[i] = (t += a[i] * value) % BASE;
}
}
void operator /= (long long value) {
long long i, t;
for(i = size, t = 0; i > 0; i--) {
t = t * BASE + a[i];
a[i] = t / value;
t %= value;
}
while(size > 1 && a[size] == 0) {
size--;
}
}
void operator += (const Huge &other) {
int i, j, t;
for(i = 1, j = 1, t = 0; i <= this->size || j <= other.size || t != 0; i++, j++, t /= BASE) {
t += this->a[i] + other.a[i];
this->a[i] = t % BASE;
}
this->size = i - 1;
}
void operator -= (const Huge &other) {
int i, t;
for(i = 1; i <= this->size; i++) {
this->a[i] -= (other.a[i] + t);
t = 0;
if(this->a[i] < 0) {
this->a[i] += BASE;
t = 1;
}
}
while(this->size > 1 && this->a[this->size] == 0) {
this->size--;
}
}
Huge operator *(const Huge &other) {
Huge answer;
for(int i = 1; i <= this->size; i++) {
long long t = 0;
int j;
for(j = 1; j <= other.size || t; j++, t /= BASE) {
t += answer.a[i + j - 1] + 1LL * this->a[i] * other.a[j];
answer.a[i + j - 1] = t % BASE;
}
answer.size = std::max(answer.size, i + j - 2);
}
return answer;
}
bool operator >(const Huge &other) const {
if(this->size != other.size) {
return this->size > other.size;
}
for(int i = this->size; i > 0; i--) {
if(this->a[i] != other.a[i]) {
return this->a[i] > other.a[i];
}
}
return false;
}
};
/*-------- Data --------*/
Huge comb, a, b;
Huge dp[2][MAX_N];
/*-------- --------*/
bool Check(Huge _a, Huge _b, Huge _c, Huge _d) {
Huge x = _a * _d;
Huge y = _b * _c;
return y > x;
}
int main() {
long long n, d, frac_a, frac_b; scanf("%lld%lld%lld%lld", &n, &d, &frac_a, &frac_b);
frac_a = frac_b - frac_a;
a.SetValue(frac_a); b.SetValue(frac_b); comb.SetValue(n);
for(int i = 1; i <= n; i++) {
dp[0][i].SetValue(i);
}
int now = 1, before = 0;
int level = 1;
while(Check(a, b, dp[before][n], comb)) {
comb *= (n - level);
level++;
comb /= level;
for(int i = 0; i < level; i++) {
dp[now][i].SetValue(0);
}
for(int i = level; i <= n; i++) {
dp[now][i] = dp[now][i - 1];
if(i - d - 1 > 0) {
dp[now][i] += dp[before][i - d - 1];
}
}
now ^= 1; before ^= 1;
}
printf("%d\n", level);
return 0;
}