# Codeforces 1063D Candies for Children

2018/10/15 11:15

## 题目大意

Note, that basically, we have two parts of the circle — the part between $[l;r]$ which gets candies one time more than the other part.

$(2a + (x- a)) (t + 1) + (2b + (y - b) ) t = k$ 化简得

$$(a + x) (t + 1) + (b + y) t = k \label{E:1}$$

（下面是这道题最精髓的地方。）

## Implementation

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

ll ple(ll fz, ll fm) { // fz >= 0, fm > 0
return fz / fm;
}

ll pge(ll fz, ll fm) { //fz >= 0, fm > 0
return (fz + fm - 1) / fm;
}

ll le (ll fz, ll fm) {
return fz >= 0 ? ple(fz, fm) : -pge(-fz, fm); // 别忘了pge(-fz, fm)前面的负号！
}
ll ge(ll fz, ll fm) {
return fz >= 0 ? pge(fz, fm) : -ple(-fz, fm);
}

int main() {
ios::sync_with_stdio(false);
//    cin.tie(nullptr);
#ifdef LOCAL
freopen("main.in", "r", stdin);
//    freopen("main.out", "w", stdout);
#endif

ll n, l, r, k;
cin >> n >> l >> r >> k;
ll x = r - l + 1;
if (x <= 0) x += n;
ll y = n - x;
ll ans = -1;

if (n <= (ll)cbrt(k)) {
for (ll a = 0; a <= x; a++) {
for (ll b = 0; b <= y; b++) {
ll s = a + x + b + y;
ll bb = k - a - x;
if (bb >= 0 && bb % s == 0) {
ans = max(ans, a + b);
}
if (a > 0 && (bb + 1) >= 0 && (bb+1)%s == 0) {
ans = max(ans, a + b);
}
}
}
}
else {
for (ll t = 0; t <= k / n; t++) {
ll bb = k - n * t - x;
if (bb >= 0) {
// a = bb - tz , b = (t + 1) z - bb;
if (t == 0) { // a = bb, b可任意取值
if (bb <= x) ans = max(ans, bb + y);
if (bb + 1 <= x) ans = max(ans, bb + 1 + y);
}
else {
// bb - tz >= 0 => z <= bb / t, bb - tz <= x => z >= (bb - x) / t
// (t + 1) z - bb >= 0 => z >= bb / (t + 1), (t + 1) z - bb <= y -> z <= (bb + y) / (t + 1)
ll minz = max(ge(bb - x, t), ge(bb, t + 1));
ll maxz = min(le(bb, t), le(bb + y, t + 1));
if (maxz >= minz) {
ans = max(ans, maxz);
}
// bb - tz >= 1 => z <= (bb - 1)/t
bb++;
minz = max(ge(bb - x, t), ge(bb, t + 1));
maxz = min(le(bb - 1, t), le(bb + y, t + 1));
if (maxz >= minz) {
ans = max(ans, maxz);
}
}
}
}
}
cout << ans << endl;

#ifdef LOCAL
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
return 0;
}


0
0 收藏

0 评论
0 收藏
0