Pagini recente » Cod sursa (job #2487763) | Cod sursa (job #1535210) | Cod sursa (job #461591) | Cod sursa (job #2503645) | Cod sursa (job #1085609)
#include <cstdio>
#include <algorithm>
#include <cstring>
#define NMAX 257
using namespace std;
int D[NMAX][NMAX][NMAX], C[NMAX][NMAX][NMAX];
void adun(int a[], int b[]){
int t = 0;
a[0] = max(a[0], b[0]);
for(int i = 1; i <= a[0]; ++i){
a[i] += b[i] + t;
t = a[i] / 10;
a[i] %= 10;
}
while(t > 0){
a[++a[0]] = t % 10;
t /= 10;
}
}
void scad(int a[], int b[]){
int t = 0;
for(int i = 1; i <= a[0]; ++i){
a[i] -= (b[i] + t);
if(a[i] < 0)
t = 1;
else
t = 0;
a[i] += t * 10;
}
while(a[a[0]] == 0)
-- a[0];
}
void prod(int a[], int x){
int t = 0;
for(int i = 1; i <= a[0]; ++i){
a[i] *= x;
a[i] += t;
t = a[i] / 10;
a[i] %= 10;
}
while(t > 0){
a[++a[0]] = t % 10;
t /= 10;
}
}
inline int Comp(int a[], int b[]){
if(a[0] != b[0])
return a[0] > b[0];
for(int i = a[0]; i >= 1; --i)
if(a[i] != b[i])
return a[i] > b[i];
return 0;
}
int main(){
int n, d, a, b;
freopen("bile2.in", "r", stdin);
freopen("bile2.out", "w", stdout);
scanf("%d %d %d %d", &n, &d, &a, &b);
for(int i = 0; i <= n; ++i)
D[0][i][0] = D[0][i][1] = 1;
C[0][0][0] = C[0][0][1] = 1;
for(int i = 1; i <= n; ++i){
C[i][0][0] = C[i][0][1] = 1;
for(int j = 1; j <= n; ++j){
memcpy(C[i][j], C[i - 1][j], sizeof(C[i][j]));
adun(C[i][j], C[i - 1][j - 1]);
memcpy(D[i][j], D[i][j - 1], sizeof(D[i][j - 1]));
adun(D[i][j], D[i - 1][max(j - d - 1, 0)]);
}
}
int Aux[NMAX], Aux2[NMAX];
for(int i = 1; i <= n; ++i){
memset(Aux, 0, sizeof(Aux));
memcpy(Aux, C[n][i], sizeof(Aux));
scad(Aux, D[i][n]);
prod(Aux, b);
memset(Aux2, 0, sizeof(Aux));
memcpy(Aux2, C[n][i], sizeof(Aux2));
prod(Aux2, a);
if(Comp(Aux, Aux2) == 1){
printf("%d\n", i);
return 0;
}
}
return 0;
}