Pagini recente » Cod sursa (job #602944) | Cod sursa (job #1514918) | Cod sursa (job #1761829) | Cod sursa (job #561145) | Cod sursa (job #1997913)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("bile2.in"); ofstream fout ("bile2.out");
typedef vector< int > huge;
const int nmax = 1000;
const int base = 1e4;
huge fact[nmax + 1];
huge d[nmax + 1][nmax + 1];
huge operator + (const huge &x, const huge &y) {
int t = 0;
huge z = x;
for (int i = 0; i < (int)y.size() || t != 0; ++ i) {
if (i == (int)z.size()) {
z.push_back( 0 );
}
if (i < (int)y.size()) {
z[ i ] += y[ i ];
}
z[ i ] += t;
if (z[ i ] >= base) {
t = 1; z[ i ] -= base;
} else {
t = 0;
}
}
return z;
}
huge operator * (const huge &x, long long k) {
long long t = 0;
huge z = x;
for (int i = 0; i < (int)z.size() || t != 0; ++ i) {
if (i == (int)z.size())
z.push_back( 0 );
long long aux = k * z[ i ] + t;
z[ i ] = aux % base;
t = aux / base;
}
return z;
}
huge operator * (const huge &x, const huge &y) {
long long t = 0;
huge z;
z.resize((int)x.size() + (int)y.size() - 1);
for (int i = 0; i < (int)x.size(); ++ i) {
for (int j = 0; j < (int)y.size(); ++ j) {
z[i + j] += x[ i ] * y[ j ];
}
t = 0;
for (int j = 0; j < (int)z.size() || t != 0; ++ j) {
if (j == (int)z.size())
z.push_back( 0 );
z[ j ] += t;
t = z[ j ] / base;
z[ j ] = z[ j ] % base;
}
}
return z;
}
huge nr (long long x) {
huge z;
while (x > 0) {
z.push_back(x % base);
x /= base;
}
return z;
}
bool operator <= (const huge &x, const huge &y) {
if (x.size() != y.size()) {
return x.size() < y.size();
}
int i = (int)x.size() - 1;
while (i > 0 && x[ i ] == y[ i ]) -- i;
return (x[ i ] <= y[ i ]);
}
int main() {
int n, k;
long long a, b;
fin >> n >> k >> a >> b;
++ k;
for (int i = 1; i <= n; ++ i) {
d[ 1 ][ i ].push_back( 1 );
d[ 1 ][ i ] = d[ 1 ][ i ] + d[ 1 ][i - 1];
}
for (int i = 2; i <= n; ++ i) {
for (int j = k; j <= n; ++ j) {
d[ i ][ j ] = d[ i ][j - 1] + d[i - 1][j - k];
}
}
fact[ 0 ].push_back( 1 );
for (int i = 1; i <= n; ++ i)
fact[ i ] = fact[i - 1] * i;
int ans = -1;
huge bb = nr( b ), ba = nr(b - a);
for (int i = 1; i <= n; ++ i) {
if (d[ i ][ n ] * fact[ i ] * fact[n - i] * bb <= fact[ n ] * ba) {
ans = i; break;
}
}
fout << ans << "\n";
fin.close();
fout.close();
return 0;
}