BFOC - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Prajwal Agarwal
Tester: Harris Leung
Editorialist: Trung Dang

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

Today is your birthday. You have decided to give away candies to your friends.

You have N friends and M candies. Suppose the 1^{st} friend has L buckets, 2^{nd} has L+1 buckets, 3^{rd} has L+2 buckets, and so on — in general, the i^{th} friend has L + i - 1 buckets.

You start distributing candies from the N^{th} friend and go towards the 1^{st} friend.

For each friend, you put the maximum number of candies in each bucket such that all the buckets for that friend have an equal number of candies in them. Now, you take the remaining candies, move to the next friend, and repeat the above step.

Find the number of candies which will remain with you after visiting all your friends.

EXPLANATION:

Notice that with X candies, after going through a person with C buckets, you will be left with X \mod C candies. We then have the following cases:

  1. When L + N - 1 \ge M, then the answer is M if L > M, or 0 if L \le M. This is because if L > M, all friends have more buckets than there are candies, therefore no candies will be distributed; if L \le M, then there exists a friend i that L + i - 1 = M exactly while all friends to the right of i have more than M buckets, therefore after we pass this friend i we are left with 0 candies.
  2. If L + N - 1 < M, we simply take M \mod (L + N - 1) candies and solve the problem for N - 1 friends, and it will immediately be case 1. That is because M \mod (L + N - 1) < L + N - 1, which means M \mod (L + N - 1) \le L + N - 2.

Beware of the case where N = 0.

TIME COMPLEXITY:

Time complexity is O(1) for each test case.

SOLUTION:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define endl "\n"

void solve() {
    int N, M, L;
    cin >> N >> M >> L;
    if(N == 0) {
        cout << M << endl;
        return ;
    }
    int left = M % (N + L - 1);
    int ans = left;
    if(left >= L) {
        ans = 0;
    }
    cout << ans << endl;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int T;
    cin >> T;
    while(T --) {
        solve();
    }
    return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
ll n;
ll a[2001];
ll dp[2001];
void solve(){
	ll n,m,l;
	cin >> n >> m >> l;
	if(n==0) cout << m << '\n';
	else if(n==1) cout << m%l << '\n';
	else if(m%(l+n-1)>=l) cout << "0\n";
	else cout << m%(l+n-1) << '\n';
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int t;cin >> t;while(t--) solve();
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t--) {
        long long n, m, l; cin >> n >> m >> l;
        if (n > 0 && l + n - 1 < m) {
            m %= (l + n - 1);
            n--;
        }
        cout << (n != 0 && l <= m ? 0 : m) << '\n';
    }
}
3 Likes

I got so demotivated after this round. I failed on the trivial case when N=0. This is the first time i have ever seen such constraint. Still feeling too low

4 Likes

Just like the dirty trick in MISS_NUM, it’s always worth double-checking the constraints before you submit your code. They got you this time, so turn the tables and make sure they don’t get you the next time.

2 Likes

why this condition left>=L why ‘>’ is used? if left > L we put 1 candy in each L buckets the
there would be (left-L) candy still remaining ? pls reply