Cutting Sticks

You have to cut a wood stick into pieces. The most affordable company, The Analog Cutting Machinery,

Inc. (ACM), charges money according to the length of the stick being cut. Their procedure of

work requires that they only make one cut at a time.

It is easy to notice that different selections in the order of cutting can led to different prices. For

example, consider a stick of length 10 meters that has to be cut at 2, 4 and 7 meters from one end.

There are several choices. One can be cutting first at 2, then at 4, then at 7. This leads to a price of 10

+ 8 + 6 = 24 because the first stick was of 10 meters, the resulting of 8 and the last one of 6. Another

choice could be cutting at 4, then at 2, then at 7. This would lead to a price of 10 + 4 + 6 = 20, which

is a better price.

Your boss trusts your computer abilities to find out the minimum cost for cutting a given stick.

3.1 Input

The input will consist of several input cases. The first line of each test case will contain a positive number

l that represents the length of the stick to be cut. You can assume l < 1000. The next line will contain

the number n(n < 50) of cuts to be made.

The next line consists of n positive numbers ci(0 < ci < l) representing the places where the cuts

have to be done, given in strictly increasing order.

An input case with l = 0 will represent the end of the input.

3.2 Output

You have to print the cost of the optimal solution of the cutting problem, that is the minimum cost of

cutting the given stick. Format the output as shown below.

3.3 Sample Input

100

3

25 50 75

10

4

4 5 7 8

0

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

 

namespace CuttingSticks

{

    class Program

    {

        static void Main(string[] args)

        {

            int length = 10;

            int minimumCost = -1;

            int[] cuttingArray = { 4, 5, 7, 8 };

            int[] pointer = new int[cuttingArray.Length];

            int i = 0;

            for (i = 0; i < pointer.Length; i++)

            {

                pointer[i] = i;

            }

            pointer[–i]–;

            do

            {

                i = pointer.Length – 1;

            label1:

                pointer[i]++;

                if (pointer[i] == pointer.Length && i != 0)

                {

                    pointer[i] = 0;

                    i–;

                    goto label1;

                }

                if (pointer[i] == pointer.Length && i == 0)

                {

                    break;

                }

                else

                {

                    int flag = 0;

                    int[] counter = new int[pointer.Length];

                    for (int j = 0; j < counter.Length; j++)

                    {

                        counter[j] = 0;

                    }

                    //Check pointer for duplicate pointers

                    for (int j = 0; j < pointer.Length; j++)

                    {

                        counter[pointer[j]]++;

                        if (counter[pointer[j]] > 1)

                        {

                            flag = 1;

                            break;

                        }

                    }

                    if (flag == 0)

                    {

                        int[] tempArray = new int[cuttingArray.Length];

                        for(int j = 0; j < cuttingArray.Length; j++)

                        {

                            tempArray[j] = cuttingArray[pointer[j]];

                        }

                        if (minimumCost == -1)

                        {

                            minimumCost = CalculateCost(tempArray, length);

                        }

                        else

                        {

                            if (minimumCost > CalculateCost(tempArray, length))

                            {

                                minimumCost = CalculateCost(tempArray, length);

                            }

                        }

                    }

                }

            } while (pointer[0] != pointer.Length);

            Console.WriteLine("Minimum Cost = " + minimumCost);

        }

        public static int CalculateCost(int[] cuttingArray, int length)

        {

            int[] lengthArray = new int[length + 1];

            for (int i = 0; i < lengthArray.Length; i++)

            {

                lengthArray[i] = 0;

            }

            lengthArray[0] = -1;

            lengthArray[lengthArray.Length – 1] = -1;

            int cost = 0;

            for (int i = 0; i < cuttingArray.Length; i++)

            {

                int start = 0;

                int end = 0;

                for (int j = cuttingArray[i] – 1; j >= 0; j–)

                {

                    if (lengthArray[j] == -1)

                    {

                        start = j;

                        break;

                    }

                }

                for (int j = cuttingArray[i] + 1; j < lengthArray.Length; j++)

                {

                    if (lengthArray[j] == -1)

                    {

                        end = j;

                        break;

                    }

                }

                cost = cost + (end – start);

                lengthArray[cuttingArray[i]] = -1;

            }

            return cost;

        }

    }

}

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