Toph - Guti Khela [ Tutorial + Solution ]

=>Try Yourself First. For help Scroll Down.

Problem Link: Read the problem statement very carefully from HERE. 

Problem Clearance: Problem asked to find out the location of placing the extra pebbles. 

Tutorial: Do a binary search to figure out the maximum value of N such that sum of 0 - N <= S. Find out the extra portion by subtracting the sum of 0 - N from S. Check whether the remaining amount evenly divisible by K or not. Print the desired output. Pay special attention to the corner cases -

1. The undetermined case occurs only when K = 0 and there are no extra pebbles.
2. The NO case occurs when K = 0 and there are some extra pebbles or extra pebbles that can't be divisible by K.
3. Except for those two cases, the answer is present and output the whole number.

Dataset is too strict. While doing binary search set the higher limit such that the desired sum of MID value does not cross the S. Take good care of corner cases.

Solution:

#include<bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define LOOP(i, b, n) for(int i=b; i<=n; i++)

using namespace std;

int main()
{
    //freopen("Type - 6.txt", "r", stdin);
    //freopen("Output - Type - 6.txt", "w", stdout);
    int test;
    scanf("%d", &test);
    LOOP(caseno, 1, test){
        ULL S, K;
        scanf("%llu %llu", &S, &K);
        ULL lo = 0, hi = 6074000999, mid, ans;
        while(lo<=hi){
            mid = lo + (hi - lo)/2;
            ULL ask = 1;
            if(mid&1){
                ask = ask * (mid + 1)/2 * mid;
            }
            else{
                ask = ask * (mid / 2) * (mid + 1);
            }

            if(ask<=S)
                ans = mid, lo = mid + 1;
            else
                hi = mid - 1;

        }

        //printf("Val = %llu\n", ans);
        ULL ret = 1;
        if(ans&1) ret = ret * (ans + 1)/2 * ans;
        else ret = ret * (ans)/2 * (ans + 1);
        //cout<<ret<<endl;
        ULL extra = S - ret;
        if(K==0){
            printf("Undetermined\n");
        }
        else if(extra>0 && extra%K==0){
            printf("%llu\n", extra/K);
        }
        else{
            printf("NO\n");
        }
    }
}

=>Leave a comment for any kinds of Hugs and/or Bugs. Thank you.