Pagini recente » Cod sursa (job #1071518) | Cod sursa (job #1751010) | Cod sursa (job #1919243) | Cod sursa (job #827859) | Cod sursa (job #3299821)
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <algorithm>
#include <cassert>
#include <queue>
#include <set>
#include <iomanip>
#include <complex>
using namespace std;
using ll = long long;
using ld = long double;
class huge
{
private:
int sign; // -1 daca numarul este negativ, +1 daca este pozitiv
string digits; // cifrele numarului, stocate in ordine inversa
public:
// initializare implicita cu 0
huge()
{
digits = "0";
sign = 1;
}
// initializare prin intermediul unui sir de caractere
huge(string s)
{
int i;
if (s.front() == '-')
sign = -1, i = 1;
else if (s.front() == '+')
sign = 1, i = 1;
else
sign = 1, i = 0;
for (int j = s.size() - 1; j >= i; --j)
digits.push_back(s[j]);
}
// initializare prin intermediul unui caracter
huge(char c)
{
sign = 1;
digits.push_back(c);
}
// initializare prin intermediul unui numar intre -2^31 si 2^31 - 1
huge(int n)
{
if (n < 0)
sign = -1;
else
sign = 1;
n = std::abs(n);
do
{
digits.push_back(n % 10 + '0');
n /= 10;
}
while (n);
}
// conversie la sir de caractere
operator string() const
{
string ans;
if (sign == -1)
{
ans.resize(1 + digits.size());
ans.front() = '-';
reverse_copy(digits.begin(), digits.end(), ans.begin() + 1);
return ans;
}
else
{
ans.resize(digits.size());
reverse_copy(digits.begin(), digits.end(), ans.begin());
return ans;
}
}
// comparator ==
friend bool operator == (const huge& a, const huge& b)
{
return (a.sign == b.sign && a.digits == b.digits);
}
// comparator <
friend bool operator < (const huge& a, const huge& b)
{
if (a.sign == -1 && b.sign == 1)
return true;
if (a.sign == 1 && b.sign == -1)
return false;
if (a.sign == -1 && b.sign == -1)
return (b.abs() < a.abs());
if (a.sign == 1 && b.sign == 1)
{
if (a.digits.size() < b.digits.size())
return true;
if (a.digits.size() > b.digits.size())
return false;
for (int i = a.digits.size() - 1; i >= 0; --i)
if (a.digits[i] < b.digits[i])
return true;
else if (a.digits[i] > b.digits[i])
return false;
return false;
}
}
// comparator <=
friend bool operator <= (const huge& a, const huge& b)
{
return (a < b || a == b);
}
// comparator >=
friend bool operator >= (const huge& a, const huge& b)
{
return !(a < b);
}
// comparator >
friend bool operator > (const huge& a, const huge& b)
{
return !(a <= b);
}
// valoarea absoluta
huge abs() const
{
huge ans = *this;
ans.sign = 1;
return ans;
}
// opusul (inversul in raport cu adunarea)
huge operator - () const
{
if (digits == "0")
return *this;
huge ans = *this;
ans.sign *= -1;
return ans;
}
// suma a 2 numere
huge operator + (const huge& b) const
{
if (sign == -1 && b.sign == -1)
return -(this->abs() + b.abs());
if (sign == -1 && b.sign == 1)
return b - this->abs();
if (sign == 1 && b.sign == -1)
return *this - b.abs();
if (sign == 1 && b.sign == 1)
{
huge ans;
ans.sign = 1;
ans.digits = "";
int cnt = 0, i;
for (i = 0; i < std::min(digits.size(), b.digits.size()); ++i)
{
int sum = digits[i]-'0' + b.digits[i]-'0' + cnt;
ans.digits.push_back(sum%10 + '0');
cnt = sum/10;
}
for (; i < digits.size(); ++i)
{
int sum = digits[i]-'0' + cnt;
ans.digits.push_back(sum%10 + '0');
cnt = sum/10;
}
for (; i < b.digits.size(); ++i)
{
int sum = b.digits[i]-'0' + cnt;
ans.digits.push_back(sum%10 + '0');
cnt = sum/10;
}
for (; cnt; cnt /= 10)
ans.digits.push_back(cnt%10 + '0');
return ans;
}
}
// diferenta a 2 numere
huge operator - (const huge& b) const
{
if (sign == -1 && b.sign == -1)
return b.abs() - this->abs();
if (sign == -1 && b.sign == 1)
return -(this->abs() + b);
if (sign == 1 && b.sign == -1)
return *this + b.abs();
if (sign == 1 && b.sign == 1)
{
if (*this < b)
return -(b - *this);
huge ans;
ans.sign = 1;
ans.digits = "";
int i;
bool cnt = 0;
for (i = 0; i < std::min(digits.size(), b.digits.size()); ++i)
{
if ((digits[i]-'0') - (b.digits[i]-'0') - cnt < 0)
{
ans.digits.push_back((digits[i]-'0') - (b.digits[i]-'0') - cnt + 10 + '0');
cnt = 1;
}
else
{
ans.digits.push_back((digits[i]-'0') - (b.digits[i]-'0') - cnt + '0');
cnt = 0;
}
}
for (; i < digits.size(); ++i)
{
if ((digits[i]-'0') - cnt < 0)
{
ans.digits.push_back((digits[i]-'0') - cnt + 10 + '0');
cnt = 1;
}
else
{
ans.digits.push_back((digits[i]-'0') - cnt + '0');
cnt = 0;
}
}
while (ans.digits.size() != 1 && ans.digits.back() == '0')
ans.digits.pop_back();
return ans;
}
}
// produsul a 2 numere
huge operator * (const huge& b) const
{
if (*this == huge(0) || b == huge(0))
return huge(0);
huge ans;
if (sign + b.sign == 0)
ans.sign = -1;
else
ans.sign = 1;
ans.digits.resize(digits.size() + b.digits.size(), '0');
int cnt, i, j;
for (i = 0; i < digits.size(); ++i)
{
cnt = 0;
for (j = 0; j < b.digits.size(); ++j)
{
int sum = (ans.digits[i+j]-'0' + (digits[i]-'0') * (b.digits[j]-'0') + cnt);
ans.digits[i+j] = sum%10 + '0';
cnt = sum/10;
}
if (cnt)
ans.digits[i+j] = (ans.digits[i+j]-'0' + cnt) + '0';
}
while (ans.digits.size() != 1 && ans.digits.back() == '0')
ans.digits.pop_back();
if (ans.digits == "0")
return huge(0);
return ans;
}
// catul impartirii a 2 numere
huge operator / (const huge& b) const
{
if (*this == huge(0))
return huge(0);
huge ans, A = this->abs(), B = b.abs();
if (A < B)
return huge(0);
huge dei, inm;
dei.digits = "";
ans.digits = "";
int i;
for (i = digits.size() - 1; ; --i)
{
dei.digits.insert(dei.digits.begin(), digits[i]);
if (dei >= B)
break;
}
for (i--; i >= -1; --i)
{
for (int j = 0; j <= 9; ++j)
{
inm.digits[0] = j+'0';
if ( !(B * inm <= dei) )
{
inm.digits[0]--;
break;
}
}
ans.digits.push_back(inm.digits[0]);
dei = dei - B*inm;
if (dei.digits == "0")
dei.digits = "";
if (i >= 0)
dei.digits.insert(dei.digits.begin(), digits[i]);
}
if (sign + b.sign == 0)
ans.sign = -1;
else
ans.sign = 1;
reverse(ans.digits.begin(), ans.digits.end());
return ans;
}
// restul impartirii a 2 numere pozitive
huge operator % (const huge& b) const
{
return *this - *this / b * b;
}
// citire prin intermediul stream-urilor
friend istream& operator >> (istream& in, huge& n)
{
int i;
string nr;
in >> nr;
if (nr.front() == '-')
n.sign = -1, i = 1;
else if (nr.front() == '+')
n.sign = 1, i = 1;
else
n.sign = 1, i = 0;
if (nr == "-0")
n.sign = +1;
n.digits.resize(nr.size() - i);
reverse_copy(nr.begin() + i, nr.end(), n.digits.begin());
return in;
}
// scriere prin intermediul stream-urilor
friend ostream& operator << (ostream& out, const huge& n)
{
if (n.sign == -1)
out << '-';
for (int i = n.digits.size() - 1; i >= 0; --i)
out << n.digits[i];
return out;
}
};
huge calcComb(int n, int k) {
if (n < k) {
return 0;
}
if (k > n - k) {
k = n - k;
}
huge comb = 1;
for (int i = 1; i <= k; i++) {
comb = comb * (n - i + 1);
}
for (int i = 1; i <= k; i++) {
comb = comb / i;
}
return comb;
}
void solve() {
int n, d;
huge a, b;
cin >> n >> d;
cin >> a >> b;
a = b - a;
int ans = 0;
for (int i = (1 << 9); i; i >>= 1) {
int k = ans + i;
huge badComb = calcComb(n - (k - 1) * d, k);
huge totalComb = calcComb(n, k);
if (totalComb * a < badComb * b) {
ans += i;
}
}
cout << ans + 1 << '\n';
}
signed main() {
#ifdef LOCAL
assert(freopen("test.in", "r", stdin));
assert(freopen("test.out", "w", stdout));
#else
assert(freopen("bile2.in", "r", stdin));
assert(freopen("bile2.out", "w", stdout));
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
int nrt = 1;
//cin >> nrt;
while (nrt--) {
solve();
}
return 0;
}