**PROBLEM STATEMENT:**

You are given a very large rectangular chocolate bar. You must cut only as 1 x 1 pieces. You are allowed to do only ‘K’ cuts at the maximum. What is maximum number of chocolate pieces can u cut ?

For a detailed problem statement click here

**SOLUTION:**

Let **‘a’ **be the number of cuts made horizontally. Let **‘b’ **be the number cuts vertically.

Total number of Chocolate pieces = a * b

We know that, b = K – a;

So, Tot. no. of Choc. Pieces = a * K – a^{2 }

Only When a = K / 2, No. of Chocolate pieces will be maximum

So, Maximum No. of Pieces = K^{2}/2 – K^{2}/4 = K^{2}/ 4

**CODE:**

#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; int main() { int t; scanf("%d",&t); while(t--) { long long int k; scanf("%lld",&k); printf("%lld\n", (k*k)/4LL); } return 0; }

Advertisements

How did you get

Maximum No. of Pieces = K^2 /2 – K^2/4 ?

Substitute in the formula a*k – a^2 where a=k/2

you are champ !