Lucky貓的 UVA（ACM）園地(難度2)_1

Q102:Ecological Bin Packing

luckycat

有3個桶子用來裝回收的玻璃瓶，玻璃瓶的顏色有三種：棕色（Brown）、綠色（Green）、透明色（Clear）。在這個問題裡我們會告訴你每個桶子裏的玻璃瓶的顏色及數量，現在要搬移桶子裏的玻璃瓶使得最後每個桶子裡都只有單一顏色的玻璃瓶，以方便回收。你的任務就是要算出最小搬移的瓶子數。你可以假設每個桶子的容量無限大，並且總共搬移的瓶子數不會超過2³¹。

Input

每筆測試資料一行，每行有9個整數.前3個代表第1個桶子裡Brown, Green, Clear顏色的瓶子數。接下來的3個數代表 第2個桶子裡Brown, Green, Clear顏色的瓶子數。最後的3個數代表第3個桶子裡Brown, Green, Clear顏色的瓶子數。

例如：10 15 20 30 12 8 15 8 31
表示有20個Clear色的玻璃瓶在第1個桶子裏，12個Green色的玻璃瓶在第2個桶子裏，15個Brown色的玻璃瓶在第3個桶子裏。

Output

對每一筆測試資料，輸出3個桶子內最後存放之玻璃瓶顏色，以及最小搬移的瓶子數。請以大寫的'G'、 'B'、 'C' 分別代表綠色（Green）、棕色（Brown）、透明色（Clear）。

例如：BCG 30
代表最後搬移的結果第1個桶子內的玻璃瓶顏色為Brown，第2個桶子內的玻璃瓶顏色為Clear，第3個桶子內的玻璃瓶顏色為Green.並且總共搬移了30個玻璃瓶。

如果最小搬移瓶子數有一組以上的組合，請輸出字典順序最小的那一組答案。

Sample input

1 2 3 4 5 6 7 8 9

5 10 5 20 10 5 10 20 10

Sample Output

BCG 30

CBG 50

        static string[] Color = new string[] { "BCG", "BGC", "CBG", "CGB", "GBC", "GCB" };

        static List<int> ls = new List<int>();

        static int total = 0, Cal = 0;       

        static void Main()

        {                     

            foreach (string item in Console.ReadLine().Split(' '))

            {

                total += int.Parse(item);

                ls.Add(int.Parse(item));

            }

            Console.WriteLine("{0}   {1}", GetColor(), total - Cal);

        }

        static string GetColor()

        {

            int cal = 0;

            string result = null;

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

            {

                switch (Color[i])

                {

                    case "BCG":

                        cal = ls[0] + ls[5] + ls[7];

                        break;

                    case "BGC":

                        cal = ls[0] + ls[4] + ls[8];

                        break;

                    case "CBG":

                        cal = ls[2] + ls[3] + ls[7];

                        break;

                    case "CGB":

                        cal = ls[2] + ls[4] + ls[6];

                        break;

                    case "GBC":

                        cal = ls[1] + ls[3] + ls[8];

                        break;

                    case "GCB":

                        cal = ls[1] + ls[5] + ls[6];

                        break;

                    default:

                        break;

                }

                if (cal > Cal)

                {

                    Cal = cal;

                    result = Color[i];

                }

            }

            return result;

        }

Q107: The Catin the Hat

題目不懂

一隻神奇聰明貓走進了一間亂七八糟的房間，他不想自己動手收拾，他決定要找幫手來工作。於是他從他的帽子中變出了N隻小貓來幫他（變出來的貓，高度為原來貓的 1/(N+1) ）。這些小貓也有帽子，所以每一隻小貓又從他的帽子中變出N隻小小貓來幫他。如此一直下去，直到這些小小小....貓小到不能再小（高度＝1），他們的帽子無法再變出更小的貓來幫忙，而這些最小的貓只得動手打掃房間。注意：所有貓的高度都是正整數。

在這個問題中，給你一開始那隻貓的高度，以及最後動手工作的貓的數目（也就是高度為1的貓的數目）。要請你求出有多少隻貓是沒有在工作的，以及所有貓的高度的總和。

Input

每組測試資料一列，有2個正整數分別代表一開始那隻貓的高度，以及最後動手工作的貓的數目。0 0代表輸入結束。

Output

每組測試資料輸出一列，包含2個正整數分別代表有多少隻貓是沒有在工作的，以及所有貓的高度的總和。

Sample Input

216 125

5764801 1679616

64 1

2 1

1 1

0 0

Sample Output

31 671

335923 30275911

6 127

1 3

0 1

        static List<int> Collect, ColNumber;

        static int Quantity, SumHigh;

        static void Main()

        {

            while (true)

            {

                string input = Console.ReadLine();

                if (input == "0 0") return;

                Collect = new List<int>();

                ColNumber = new List<int>();

                Quantity = SumHigh = 0;

                foreach (string item in input.Split(' '))

                    Collect.Add(Convert.ToInt32(item));

                Program P = new Program();

                P.Calculator();

                Console.WriteLine("{0} {1}\n", Quantity - Collect[1], SumHigh);  

            }           

        }

        void Calculator()

        {

            int high = Collect[0], R = 0, H = 1;

             while (high > 1)

            {

                for (int i = 2; i <= Collect[0]; i++)

                {

                    if (high%i == 0)

                    {

                        high /= i;

                        if (R != i)

                        {

                            R = i;

                            ColNumber.Add(R);

                        }

                        break;

                    }

                }

            }

            foreach (int item in ColNumber) H *= item;

            R = 0;     

            while (true)

            {

                high = Collect[0] / (int)Math.Pow(H, R);     

                Quantity += (int)Math.Pow(H - 1, R);

                SumHigh += high * (int)Math.Pow(H - 1, R);

                R++;

                if (high <= 1) return;

            }

        }

Q118: MutantFlatworld Expolrers

MVC架構  

給你一塊矩形土地的長寬，再依序給定每個機器人的初始位置狀況及一連串的指令集，你必須用你的程式求出每個機器人最後的位置狀況。

一個機器人的位置狀況包括了其坐標（ x 坐標， y 坐標），和它面向的方向（用 N , S , E , W 來分別代表北、南、東、西）。至於一個機器人所收到的指令集，是一個由字母 ' L ' ， ' R ' ， 和 ' F ' 所構成的字串，其分別代表：

• 左轉（Left）：機器人在原地往左轉 90 度。
• 右轉（Right）: 機器人在原地往右轉 90 度。
• 前進（Forward）: 機器人往其面向的方向向前走一格，且不改變其面向之方向。

從坐標 (x,y) 走至 (x,y+1) 的這個方向我們定義為北方。

因為此矩形土地是有邊界的，所以一旦一個機器人走出邊界掉落下去，就相當於永遠消失了。不過這個掉下去的機器人會留下「標記 ( scent ) 」，提醒以後的機器人，避免他們從同一個地方掉下去。掉下去的機器人會把標記，留在他掉落之前所在的最後一個坐標點。所以對於以後的機器人，當他正位在有標記的地方時，這個機器人就會忽略會讓他掉下去的指令。

Input

輸入裡的第一列有2個正整數，代表這個矩形世界右上角頂點的坐標，其中假設這個世界的左下角頂點坐標為 ( 0 , 0 )。

接下來是若干組有關機器人的初始位置狀況和指令集，每個機器人2列。第一列為位置狀況，包括了兩個整數和一個字元（ N , S , E 或 W ），代表機器人初始的位置坐標以及機器人最初所面對的方向。第二列則是指令集，是一個由 ' L ' ， ' R ' 和 ' F ' 所組成的字串。輸入以 end-of-file 作為結束。

各機器人是依序動作的，也就是說，直到一個機器人作完他全部的動作，下一個機器人才會開始動作。

所有機器人的初始位置皆會在矩形土地上，不會落在外面。任何坐標的最大值皆不會超過 50 。每個指令集的長度皆不會超過 100 個字元長。

Output

對於每一個機器人，你都必須輸出其最後所在的坐標和面對的方向。如果一個機器人會掉落出此世界外，你必須先輸出他在掉落前，最後的所在位置和面對的方向，再多加一個字： LOST 。

Sample Input

5 3

1 1 E

RFRFRFRF

3 2 N

FRRFLLFFRRFLL

0 3 W

LLFFFLFLFL

Sample Output

1 1 E

3 3 N LOST

2 3 S

 

        static Int32 X_Boundary, Y_Boundary, X, Y, DirNumber;
        static List<char> Direction;
        static List<int> X_Danger, Y_Danger;
        static void Main()
        {
            Model();
            while (true)
            {
                string s = Console.ReadLine();
                if (s == "") return;
                string[] cell = s.Split(' ');
                X = int.Parse(cell[0]);
                Y = int.Parse(cell[1]);
                DirNumber = Direction.IndexOf(char.Parse(cell[2]));
                s = Console.ReadLine() + " ";
                if (Controller(s)) Console.WriteLine("{0} {1} {2}", X, Y, Direction[DirNumber]);
                else View();
                Console.WriteLine();
            }
        }
        static void Model()
        {
            string[] cell = Console.ReadLine().Split(' ');
            char[] item = new char[] { 'N', 'E', 'S', 'W' };
            Direction = new List<char>(item);
            X_Danger = new List<int>();
            Y_Danger = new List<int>();
            X_Boundary = int.Parse(cell[0]);
            Y_Boundary = int.Parse(cell[1]);
        }
        static void View()
        {
            if (X > X_Boundary) X = X_Boundary;
            if (X < 0) X = 0;
            if (Y > Y_Boundary) Y = Y_Boundary;
            if (Y < 0) Y = 0;
            X_Danger.Add(X);
            Y_Danger.Add(Y);
            Console.WriteLine("{0} {1} {2} LOST", X, Y, Direction[DirNumber]);
        }
        static bool Controller(string input)
        {
            foreach (char instruct in input.ToCharArray())
            {
                if (X > X_Boundary || X < 0 || Y > Y_Boundary || Y < 0) return false;
                switch (instruct)
                {
                    case 'R':
                        DirNumber = (DirNumber + 1) % 4;
                        break;
                    case 'L':
                        DirNumber = (DirNumber + 3) % 4;
                        break;
                    case 'F':
                        if (X_Danger.Contains(X) && Y_Danger.Contains(Y) &&
                            X_Danger.IndexOf(X) == Y_Danger.IndexOf(Y) &&
                            DirNumber < 2) break;
                        switch (DirNumber)
                        {
                            case 0:
                                Y++;
                                break;
                            case 1:
                                X++;
                                break;
                            case 2:
                                Y--;
                                break;
                            case 3:
                                X--;
                                break;
                            default:
                                break;
                        }
                        break;
                    default:
                        break;
                }
            }
            return true;
        }