Cutting Blocks

Niloy is a cool mathematician and is good at solving puzzles. He has been given a puzzle which he solves very quickly but he wants to check his solution. Now your task is to find the answer so that Niloy can match his answer.
Here is the puzzle
J
Given a block of W weight you have to cut the block into blocks having a weight of K or less. Each block can be a cut only once such that it results in blocks with minimal weight difference. We can further cut the newer blocks but we can apply only one cut to a particular block. The cuts are made such that we get blocks of integral weight. W and K are both integer.

 

Input 

n – No. of cases

W (integer) – Weight of original block

K (integer) – Maximum weight of final blocks to be formed

 

2 < = W  <= 10000

1 < = K

 

Output 

No. of final blocks formed

 

Sample Input 

5

16 1

4 2

16 2

32 4

11 2

 

Sample Output 

16

2

8

8

7
 

using System;

using System.Collections.Generic;

using System.Collections;

using System.Linq;

using System.Text;

 

namespace ConsoleApplication1

{

    class Program

    {

        public static int minimumNumberOfBlocks = 0;

        public static int maxBlockWeight = 0;

        static void Main(string[] args)

        {

            int givenWeight = 11;

            maxBlockWeight = 2;

            if (givenWeight >= maxBlockWeight && maxBlockWeight != 0)

            {

                NumberOfBlocks(givenWeight);

            }

            Console.WriteLine("Number of final blocks formed: " + minimumNumberOfBlocks);

        }

        public static void NumberOfBlocks(int givenWeight)

        {

            if (givenWeight > maxBlockWeight)//cutting is required

            {

                if (givenWeight % 2 == 0)//even distribution

                {

                    NumberOfBlocks(givenWeight / 2);

                    NumberOfBlocks(givenWeight / 2);

                }

                else//odd distribution

                {

                    NumberOfBlocks(givenWeight / 2);

                    NumberOfBlocks((givenWeight / 2) + 1);

                }

            }

            else//no further cutting required

            {

                //Console.WriteLine(givenWeight);

                minimumNumberOfBlocks++;

            }

        }

    }

}

Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s