PROBLEM LINK:
Practice
Project Code 1.0 Contest
Author: mohilllll
Tester: phoenix_307
Editorialist: mohilllll
DIFFICULTY:
CAKEWALK
PREREQUISITES:
Basic Math, Geometric Progression
PROBLEM:
Given the number of slices of cake made per family S, slices received by smallest member K, and a lucky number R such that a family member gets R times more slices than member smaller than them and the number of members N, find if family has enough slices to share. Also find if all the T families share their extra slices, will all families have enough slices or not.
QUICK EXPLANATION:
The problem description clearly indicates the formation of a Geometric Progression. For a family of size N, first number of series as K and a factor R, the required sum of series would be K + K.R + K.R^2 + K.R^3 + ... + K.R^{N-1} which is given by \frac{K(R^N -1)}{R - 1}. Compare the sum with S to find if this is possible for not and print |\frac{K(R^N -1)}{R - 1} - S|. Keep two variables extraSlices and requiredSlices and add the difference to extraSlices when sum of GP > S, else add the difference to requiredSlices. If extraSlices ≥ requiredSlices, print POSSIBLE, else IMPOSSIBLE.
EXPLANATION:
We get the following things as input:
- T : Number of families in the locality.
- S : Number of slices baked per family.
- N : Number of members in particular family.
- K : Slices received by smallest member of the family.
- R : Lucky number of the family.
Let’s talk about each family first, the youngest family member gets K slices. Member older than them would get K.R slices, now the next member would get R times slices more than the previous one i.e. K.R.R slices.
We can see a series being formed where the next term exceeds the previous by R times. This series is called as Geometric Progression.
Example
For example, For a family of N = 4 members, smallest member getting K = 2 slices and R = 3. Family made S = 100 slices. We get,
- First member gets 2 slices.
- Second member gets 2*3 = 6 slices.
- Third member gets 6*3 = 18 slices.
- Fourth member gets 18*3 = 54 slices.
Sum would be 80 slices.
It is know that sum of finite GP is given by \frac{A(F^N -1)}{F - 1}, where A is the first element of the series, F is the common ratio and N is the number of elements.
In this question, A is K, F is R and number of elements would be number of family members i.e. N.
There is a special case to it! Can you think of it?
Special Case
If R = 1, denominator would become zero which isn’t right, so in that case required slices would be N.K.
Now if the sum of GP ≤ S, add S - Sum of GP to a variable extraSlices, otherwise add Sum of GP - S to variable requiredSlices. Do this for T families and then,
If requiredSlices ≤ extraSlices print POSSIBLE else print IMPOSSIBLE.
SOLUTIONS:
Setter's and Editorialist's Solution
#include <bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
using namespace std;
ll sumOfGP(ll members, ll kidSlices, ll r) {
if(r == 1)
return members*kidSlices;
double ans = (kidSlices*(1 - pow(r, members)))/(1 - r);
return ans;
}
int main() {
ll t; cin >> t;
ll extra = 0, shortBy = 0;
for(ll i = 0; i < t; i++) {
ll slices, members, kidSlices, r;
cin >> slices >> members >> kidSlices >> r;
ll reqiuredAtLeast = sumOfGP(members, kidSlices, r);
if(slices >= reqiuredAtLeast) {
ll remaining = slices - reqiuredAtLeast;
cout << "POSSIBLE " << remaining << endl;
extra += remaining;
}
else {
ll required = reqiuredAtLeast - slices;
cout << "IMPOSSIBLE " << required << endl;
shortBy += required;
}
}
if(extra >= shortBy)
cout << "POSSIBLE" << endl;
else
cout << "IMPOSSIBLE" << endl;
return 0;
}
Tester's Solution
def gpSum(a, r, n):
ans = (a*(r**n - 1))//(r-1)
return ans
totalSlices = 0
totalReq = 0
for t in range(int(input())):
s, n, k, r = map(int, input().split())
if r == 1:
temp = k*n
else:
temp = gpSum(k, r, n)
if temp > s:
print("IMPOSSIBLE", temp-s)
else:
print("POSSIBLE", s-temp)
totalSlices += s
totalReq += temp
if totalSlices<totalReq:
print('IMPOSSIBLE')
else:
print('POSSIBLE')