赛后题解...
相关题目:Candies for Children
官方 Editorial: https://codeforces.com/blog/entry/62455

D. Candies for Children

time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

At the children's festival, children were dancing in a circle. When music stopped playing, the children were still standing in a circle. Then Lena remembered, that her parents gave her a candy box with exactly kk candies "Wilky May". Lena is not a greedy person, so she decided to present all her candies to her friends in the circle. Lena knows, that some of her friends have a sweet tooth and others do not. Sweet tooth takes out of the box two candies, if the box has at least two candies, and otherwise takes one. The rest of Lena's friends always take exactly one candy from the box.

Before starting to give candies, Lena step out of the circle, after that there were exactly nn people remaining there. Lena numbered her friends in a clockwise order with positive integers starting with 11 in such a way that index 11 was assigned to her best friend Roma.

Initially, Lena gave the box to the friend with number ll, after that each friend (starting from friend number ll) took candies from the box and passed the box to the next friend in clockwise order. The process ended with the friend number rr taking the last candy (or two, who knows) and the empty box. Please note that it is possible that some of Lena's friends took candy from the box several times, that is, the box could have gone several full circles before becoming empty.

Lena does not know which of her friends have a sweet tooth, but she is interested in the maximum possible number of friends that can have a sweet tooth. If the situation could not happen, and Lena have been proved wrong in her observations, please tell her about this.

Input

The only line contains four integers nn, ll, rr and kk (1n,k10111 \le n, k \le 10^{11}, 1l,rn1 \le l, r \le n) — the number of children in the circle, the number of friend, who was given a box with candies, the number of friend, who has taken last candy and the initial number of candies in the box respectively.

Output

Print exactly one integer — the maximum possible number of sweet tooth among the friends of Lena or "-1" (quotes for clarity), if Lena is wrong.

Examples

input

4 1 4 12

5 3 4 10

10 5 5 1

5 4 5 6

output

2

3

10

-1

Note

In the first example, any two friends can be sweet tooths, this way each person will receive the box with candies twice and the last person to take sweets will be the fourth friend.

In the second example, sweet tooths can be any three friends, except for the friend on the third position.

In the third example, only one friend will take candy, but he can still be a sweet tooth, but just not being able to take two candies. All other friends in the circle can be sweet tooths as well, they just will not be able to take a candy even once.

In the fourth example, Lena is wrong and this situation couldn't happen.

Solution

https://codeforces.com/blog/entry/62455 官方题解两种算法上,时间复杂度 O(3n)O(^{3}\sqrt{n})

https://www.cnblogs.com/ywwyww/p/9789573.html 时间复杂度 O((n))O(\sqrt(n))

实际上下面跑的比上面还快。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0
typedef long long ll;
long long n, k, l, r;

long long solve(ll n, ll r, ll k, int p) {
if(k < r) return -1;
long long s=-1;
if(n > k/n/n) {
if(k<=2*r) return k-r+n-r;

for(ll t=(k-2*r-1)/(2*n)+1; t<=(k-r)/n; ++t) { //枚举圈数t
ll a = (k-r)%t;
if(a < p) a+=t;
ll b = (k-r-a)/t - n-a;
if(b > n-r) {
ll x = (b-n+r-1)/(t+1) + 1;
a += t*x;
b -= (t+1)*x;
} // Diophantine equation
if(a<=r && b>=0) s=max(s, a+b);
}
// O(n/k)
}
else {
for(ll a=p; a<=r; ++a)for(ll b=0; b<=n-r; ++b)
if((k-r-a)%(n+a+b)==0) s=max(s, a+b);
// O(n^2)
}
return s;
}

int main() {
cin >> n >> l >> r >> k;
r = (r-l+n)%n+1;
cout << max(solve(n,r,k,0),solve(n,r,k+1,1)) << endl;
return ~~(0^_^0);
}

Code2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(long long i=a;i<=b;++i)
#define _ 0
typedef long long ll;
ll n, l, r, k, ans=-1;

int main() {
cin >> n >> l >> r >> k;
r = r>=l?r-l+1:n-l+r+1;

if(n < k/n) {
rep(z,n,2*n) {
ll a = max(0ll, z-n-(n-r)-1);
ll b = min(z-n, r);
ll w = (k-1)%z+1-r;
if(a<=w&&w<=b) ans=max(ans,z-n);
}
}
else {
if(k>=r&&k<=2*r) ans=max(ans, k==2*r?n:n-r+k-r+1);
rep(t,1,k/n) {
ll a = min((k-2*r+2*n+1)/(t+1),(k-r)/t);
ll b = max((k-2*r+t-1)/t,(k-r+n+t)/(t+1)); //ceil
if(b <= a) ans=max(ans,a-n);
}
}
cout << ans << endl;
return ~~(0^_^0);
}