Pagini recente » Cod sursa (job #73744) | Cod sursa (job #706914) | Cod sursa (job #2834556) | Cod sursa (job #1485056) | Cod sursa (job #743045)
Cod sursa(job #743045)
#include <fstream>
#include <cstring>
using namespace std;
const int N = 1005, LMax = 64;
ifstream in("bile2.in");
ofstream out("bile2.out");
struct Mare
{
short int mare[LMax];
void sloppy()
{
int i;
for (i = 1 ; i <= mare[0] || mare[i] ; i++)
if (mare[i] > 9)
{
mare[i + 1] += mare[i] / 10;
mare[i] %= 10;
}
mare[0] = i > 1 ? i - 1 : 1;
}
void get()
{
char s[LMax];
in >> s;
mare[0] = strlen(s);
for (int i = mare[0] , j = 0 ; s[j] ; j++, i--)
mare[i] = s[j] - '0';
}
void operator= (int x)
{
memset(mare, 0, sizeof(mare));
mare[1] = x;
sloppy();
}
Mare operator+ (Mare& Num)
{
Mare rez; rez = 0;
short int *v = rez.mare, *a = mare, *b = Num.mare;
int i, t = 0;
for (i = 1 ; i <= a[0] || i <= b[0] || t; i++, t /= 10)
v[i] = (t += a[i] + b[i]) % 10;
v[0] = i - 1;
return rez;
}
Mare operator- (Mare& Num)
{
Mare rez; rez = *this;
short int *a = rez.mare, *b = Num.mare;
int i, t=0;
for (i = 1 ; i <= a[0] ; i++)
{
a[i] -= b[i];
if (a[i] < 0)
{
a[i] += 10;
a[i + 1]--;
}
}
for ( ; !a[a[0]] ; a[0]--);
return rez;
}
Mare operator* (Mare& Num)
{
Mare rez; rez = 0;
short int *v = rez.mare, *a = mare, *b = Num.mare;
v[0] = a[0] + b[0] - 1;
for (int i = 1 ; i <= a[0] ; i++)
for (int j = 1 ; j <= b[0] ; j++)
v[i + j - 1] += a[i] * b[j];
rez.sloppy();
return rez;
}
bool operator<= (Mare Num)
{
short int *a = mare, *b = Num.mare;
if (a[0] != b[0])
return a[0] < b[0];
for (int i = a[0] ; i ; i--)
if (a[i] != b[i])
return a[i] < b[i];
return true;
}
} v[N][N], comb[N][N];
int main()
{
int n, D;
Mare A, B;
in >> n >> D; D++;
A.get();
B.get();
for (int i = 1 ; i <= n ; i++)
v[1][i] = i;
for (int i = 1 ; i <= n ; i++)
{
comb[i][0] = 1;
comb[i][i] = 1;
for (int j = 1 ; j < i ; j++)
comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
}
for (int i = 2 ; i <= n ; i++)
{
for (int j = D + 1 ; j <= n ; j++)
v[i][j] = v[i][j - 1] + v[i - 1][j - D];
if ((A * comb[n][i])<= ((comb[n][i] - v[i][n]) * B))
{
out << i << "\n";
return 0;
}
}
out << "-1\n";
return 0;
}