Maximum number of pieces with cuts

 

Introduction

   The problem is taken from HackerRank. The task is to cut a huge chocolate bar into 1x1 pieces with as much as possible cuts. The number of cuts are given using which we need to identify the number of pieces.

Solution

  The problem is so simple if we understand the logic behind it. The given value is number of cuts. In this value, some are horizontal lines and some are vertical lines. Don’t get confused by it. Just check for the base case, when there are two lines.

when number of cuts is 2, there will be only one chocolate piece. when the number of cuts are 3, there will be 3 = 1 + 2 = 1*2 = 2 cuts.. how ? all numbers are divisible by 2 and you get a nearest possible value divisible by 2. Next step is just subtracting that value with the main value. i.e, 3/2 = 1 (q).. 3-q = 2. Multiply both these values, you get the number of pieces.

#include <vector>

#include <iostream>

using namespace std;

int main(void)

{

    int T;

    vector<long> out;

    cin>>T;

    for(int i = 0; i < T; ++i)

    {

        long q, r, val;

        cin>>val;

        q = val / 2;

        r = val - q;

        out.push_back(q*r);

    }

    for(int i = 0; i < (int) out.size(); ++i)

        cout<<out[i]<<endl;

}

what is the math logic here? when you divide any number by 2, you get a exact median of all the cuts. The median might be even or odd. The remaining value can be taken either as horizontal or vertical to maximize number of cuts (it doesn’t matter larger value need to be horizontal or vertical).  You can event print out how many vertical & horizontal now safely. :)

This means if somebody asks you to cut a cake for 30 people, then try for a multiple of 30 which can give as exactly equal pieces(3x10 or 15x2 wont give as that, we need both the factors as much near as possible). So its (6+5) 11 cuts. (i.e) you put a 5 horizontal and then a 6 vertical cuts (or vice versa) to get 30 pieces total. A math in reverse just confused the dummy mind at first look!! :D This problem made me lose faith on basic division, subtraction and multiplication.

See also

Find out the prime factors of the number: http://en.wikipedia.org/wiki/Prime_factor. It has applications on cryptography and this problem shows as some basics to it. :)