Pagini recente » Cod sursa (job #2185746) | Cod sursa (job #112147) | Cod sursa (job #2329599) | Cod sursa (job #1217495) | Cod sursa (job #1997865)
#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 ];
}
}
for (int i = 0; i < (int)z.size() || t != 0; ++ i) {
if (i == (int)z.size())
z.push_back( 0 );
z[ i ] += t;
t = z[ i ] / base;
z[ i ] = z[ i ] % 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;
for (int i = 1; i <= n; ++ i) {
if (d[ i ][ n ] * fact[ i ] * fact[n - i] * b <= fact[ n ] * (b - a)) {
ans = i; break;
}
}
fout << ans << "\n";
fin.close();
fout.close();
return 0;
}