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:
- 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.
- 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';
}
}