MORECAKE - Editorial


Project Code 1.0 Contest

Author: mohilllll
Tester: phoenix_307
Editorialist: mohilllll




Basic Math, Geometric Progression


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.


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 extraSlicesrequiredSlices, print POSSIBLE, else IMPOSSIBLE.


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.


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 requiredSlicesextraSlices print POSSIBLE else print IMPOSSIBLE.


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;
        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
        temp = gpSum(k, r, n)
    if temp > s:
        print("IMPOSSIBLE", temp-s)
        print("POSSIBLE", s-temp)
    totalSlices += s
    totalReq += temp
if totalSlices<totalReq: