Feeds:
文章
留言

Archive for the ‘解題’ Category

[ACM]Q145 Gondwanaland Telecom

Gondwanaland Telecom這家電話公司收費的標準是以所撥電話的距離及時段來訂定的,如下表。在這裡charging step就是指不同的距離。

p145

所有的收費是根據該通電話每一分鐘多少錢來計算的,所以若有某通電話有跨時段,則按時段不同的收費標準分別計算在加總。例如:有一通電話從5:58pm開始到6:04pm結束,那前2分鐘是按白天(Day)的標準計費,而後4分鐘則按傍晚(Evening)的標準計費。

所有小於一分鐘的電話不列入計費,而且沒有一通電話會持續超過24小時。

Input

每筆測試資料一列,代表某通電話的通話記錄。每列輸入資料包含6個部分,第一個部分為charging step(大寫字母A~E)。第二個部分為所撥的電話號碼(為7個數字及一個"-"的字串),第三、四個部分代表通話開始的時間:時及分。第五、六個部分代表通話結束的時間:時及分(均以24小時的時鐘來看,時、分均以2個數字來表現)。

若輸入列的第一個字為#,代表輸入結束。請參考Sample Input

Output

對每一筆測試資料輸出一列,也包含6個部分。

第一個部分為所撥的電話號碼。第二、三、四部分分別代表這通電話所用各時段(Day,Evening,Night)的分鐘數,第五個部分為charging step,第六個部分為這通電話總共計費多少錢。

各部分輸出於一定位置,以靠右對其來說,分別在10,16,22,28,31,39的位置。請參考Sample Output

Sample Input

C 765-7457 10 41 04 29
B 207-0225 21 28 07 53
B 316-0414 16 43 09 37
C 463-1401 19 28 00 33
D 514-9373 01 20 09 08
#

Sample Output

  765-7457   439   240   389  C  362.44
  207-0225     0    32   593  B   34.45
  316-0414   174   240   600  B  109.50
  463-1401     0   152   153  C   70.05
  514-9373    68     0   400  D  127.16

解題思考

  檢查一個時間區段是在哪段收費時段,我覺得判斷區段太麻煩了,乾脆一分一分的檢查是在哪時段。

參考解答(C#3.0)
using System;
//Author: kgame 許智涵
//http://kgame-blog.spaces.live.com/
namespace Q145_Gondwanaland_Telecom
{
    class Program
    {
        static void Main()
        {
            Ratc[] steps = new Ratc[5];
            steps[0] = new Ratc(0.10, 0.06, 0.02);
            steps[1] = new Ratc(0.25, 0.15, 0.05);
            steps[2] = new Ratc(0.53, 0.33, 0.13);
            steps[3] = new Ratc(0.87, 0.47, 0.17);
            steps[4] = new Ratc(1.44, 0.80, 0.30);
            string str;
            while ((str = Console.ReadLine()) != "#")
            {
                string[] strArr = str.Split(' ');
                Ratc r = steps[strArr[0][0] - 'A'];
                int t1, t2;
                t1 = int.Parse(strArr[2]) * 60 + int.Parse(strArr[3]);
                t2 = int.Parse(strArr[4]) * 60 + int.Parse(strArr[5]);
                int d = 0, e = 0, n = 0;
                Action<int> CheckTime = t =>
                {
                    if (t < 480)
                        n++;
                    else if (t < 1080)
                        d++;
                    else if (t < 1320)
                        e++;
                    else
                        n++;
                };
                if (t1 < t2)
                    for (int i = t1; i < t2; i++)
                        CheckTime(i);
                else
                {
                    for (int i = t1; i < 1440; i++)
                        CheckTime(i);
                    for (int i = 0; i < t2; i++)
                        CheckTime(i);
                }
                Console.WriteLine("{0,10}{1,6}{2,6}{3,6}{4,3}{5,8:0.00}", strArr[1], d, e, n, strArr[0], r.Bill(d, e, n));
            }
        }
    }

    class Ratc
    {
        public double Day, Evening, Night;
        public Ratc(double d, double e, double n)
        { Day = d; Evening = e; Night = n; }

        public double Bill(int d, int e, int n)
        {
            return d * Day + e * Evening + n * Night;
        }
    }
}

參考解答(Boo)

namespace Q145_Gondwanaland_Telecom
#Author: kgame 許智涵
#http://kgame-blog.spaces.live.com/
import System

def Main():
    steps = array(Ratc, 5)
    steps[0] = Ratc(0.10, 0.06, 0.02)
    steps[1] = Ratc(0.25, 0.15, 0.05)
    steps[2] = Ratc(0.53, 0.33, 0.13)
    steps[3] = Ratc(0.87, 0.47, 0.17)
    steps[4] = Ratc(1.44, 0.80, 0.30)
    while (str = gets()) != "#":
        s = str.Split(char(' '))
        r = steps[cast(int, s[0][0]) - 0x41]
        t1 = int.Parse(s[2]) * 60 + int.Parse(s[3])
        t2 = int.Parse(s[4]) * 60 + int.Parse(s[5])
        d = e = n = 0
        CheckTime = def(t as int):
            if t < 480:
                n++
            elif t < 1080:
                d++
            elif t < 1320:
                e++
            else:
                n++
        if t1 < t2:
            for i in range(t1, t2):
                CheckTime(i)
        else:
            for i in range(t1, 1440):
                CheckTime(i)
            for i in range(0, t2):
                CheckTime(i)
        Console.WriteLine("{0,10}{1,6}{2,6}{3,6}{4,3}{5,8:0.00}", s[1], d, e, n, s[0], r.Bill(d, e, n))

class Ratc:
    _day as double
    _evening as double
    _night as double
    
    def constructor(d as double, e as double, n as double):
        _day = d
        _evening = e
        _night = n
    
    def Bill(d as int, e as int, n as int):
        return d * _day + e * _evening + n * _night

Read Full Post »

[ACM]Q136 Ugly Numbers

Ugly Number的定義為:該數之質因數必須為 2, 3 5

當然了,依照慣例,1 也算是 Ugly Number

在此列舉一串數列:

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15

這些就是前 11 Ugly Numbers

請寫一個程式求出第1500Ugly Number

Input

No input

Output

The 1500’th ugly number is <number>.

Attention: Your program must be smart enough to solve this problem in 30 seconds. If your program is not so efficient, it may take much time to run. Please be patient.

解題思考

  這題要用DP(動態規劃)做,動態規劃我搞了半年都還學不會,所以我就直接算,但在我的電腦要花103秒,顯然30秒內搞不出來,直接輸出正確答案就好。

參考解答(C#)

using System;
using System.Diagnostics;
//Author: kgame 許智涵
//http://kgame-blog.spaces.live.com/
namespace Q136_Ugly_Numbers
{
    class Program
    {
        static void Main()
        {
            Console.WriteLine("The 1500'th ugly number is 859963392");
            return;
            int count = 1, num = 1;
            Stopwatch sw = new Stopwatch();
            sw.Start();
            while (count < 1500)
            {
                num++;
                int n = num;
                while ((n & 1) == 0)
                    n >>= 1;
                while ((n % 3) == 0)
                    n /= 3;
                while ((n % 5) == 0)
                    n /= 5;
                if (n == 1)
                    count++;
            }
            sw.Stop();
            Console.WriteLine(num);
            Console.WriteLine((double)sw.ElapsedTicks / Stopwatch.Frequency);
            Console.ReadKey(true);
        }
    }
}

Read Full Post »

[ACM]Q128 Software CRC

你在一家有很多個人電腦的公司上班。你的老闆,連一分都省博士,想要把這些個人電腦連線,但是他又不想要花錢買網路卡。由於你不小心告訴老闆每台電腦出廠時就有一個非同步串列埠在上面,老闆當然把腦筋動到這不用花錢的解決方案上。於是可憐的你被指派來完成這工作軟體的需求,以使這些電腦之間可以連線。

你已經讀了許多關於通訊的書並且知道在傳送及接收訊息時,確保訊息的正確性是一個重點。典型的作法是在訊息的最後加上額外的錯誤檢查碼。這個資訊允許接收程式檢查出傳送的資訊是否有錯誤(在大多數的例子)。於是,你跑到圖書館借回了一本關於通訊厚厚的書,利用週末(當然沒有加班費)研究錯誤檢查的部分。

最後,你決定CRC(cyclic redundancy check)是最適合的錯誤檢查方式。以下描述這個機制:

CRC Generation

待傳遞的訊息被視為一列長長二元數。訊息的第一個位元組(byte)被當作這二元數最重要的位元組,第二個位元組被當作第二重要的位元組,依此類推。這個二元數被稱為"m"。當傳送時會在"m"之後加上2個位元組的CRC檢查碼,然後整個二元數稱為"m2"。

這個CRC的檢查碼被產生使得"m2"可以整除某個16位元的值 "g"。所以當接收端收到一訊息,只要把他除以 "g",如果餘數為0即代表此訊息正確。

你也注意到,大部分建議採用的g值都是奇數,所以你決定用 34943 當作 g 的值。現在你迫切的任務就是對待傳送的訊息,寫一個程式算出這個CRC的值。

例如:若要傳送的訊息為:AB(二進位的表示式為:01000001 01000010),你必須算出的CRC值應為60 1B(01100000 00011011的十六進位表示式),使得 01000001 01000010 01100000 00011011可以整除34943(10進位)。

Input

每組測試資料一列,含有一個待傳送的訊息(不會超過1024個ASCII字元的長度),列結束字元(End of line)不被視為待傳送訊息的一部份。若遇到只含 # 的一列,代表輸入結束(此列無須輸出)。請參考Sample Input。

Output

對每組測試資料輸出一列,CRC的值(以十六進位表示)。請注意:CRC的值一定介於0到34942(十進位)之間。輸出格式請參考Sample Output。

Sample Input Sample Output

this is a test

A
AB
Nothing gonna change my love for you.
#

77 FD
00 00
0C 86
60 1B
57 98

 

解題思考

  餘數&位移運算。

參考解答(C#)

using System;
//Author: kgame 許智涵
//http://kgame-blog.spaces.live.com/
namespace Q128_Software_CRC
{
    class Program
    {
        static void Main()
        {
            string str;
            while ((str = Console.ReadLine()) != "#")
            {
                if (str.Length == 0)
                {
                    Console.WriteLine("00 00");
                    continue;
                }
                uint crc = 0;
                foreach (char c in str)
                    crc = ((crc << 8) | c) % 34943;
                crc = 34943 - ((crc << 16) + 34943) % 34943;
                Console.WriteLine("{0:X2} {1:X2}", (crc >> 8) & 0xFF, crc & 0xFF);
            }
        }
    }
}

參考解答(Boo)

namespace Q128_Software_CRC
#Author: kgame 許智涵
#http://kgame-blog.spaces.live.com/
import System

while (str = gets()) != "#":
    if str.Length == 0:
        print "00 00"
        continue
    crc as uint = 0
    for c in str:
        crc = ((crc << 8) | cast(uint, c)) % 34943
    crc = 34943 - ((crc << 16) + 34943) % 34943
    print "${(crc >> 8) & 0xFF:X2} ${crc & 0xFF:X2}"

Read Full Post »

[ACM]Q101 The Blocks Problem

在早期人工智慧的領域中常常會用到機器人,在這個問題中有一支機器手臂接受指令來搬動積木,而你的任務就是輸出最後積木的情形。

一開始在一平坦的桌面上有n塊積木(編號從0到n-1)0號積木放在0號位置上,1號積木放在1號位置上,依此類推,如下圖。

p101

機器手臂有以下幾種合法搬積木的方式(a和b是積木的編號):

  • move a onto b
    在將a搬到b上之前,先將a和b上的積木放回原來的位置(例如:1就放回1的最開始位罝)
  • move a over b
    在將a搬到b所在的那堆積木之上之前,先將a上的積木放回原來的位罝(b所在的那堆積木不動)
  • pile a onto b
    將a本身和其上的積木一起放到b上,在搬之前b上方的積木放回原位
  • pile a over b
    將a本身和其上的積木一起搬到到b所在的那堆積木之上
  • quit
    動作結束

前四個動作中若a=b,或者a, b在同一堆積木中,那麼這樣的動作算是不合法的。所有不合法的動作應該被忽略,也就是對各積木均無改變。

Input

輸入含有多組測試資料,每組測試資料的第一列有一個正整數n(0 < n < 25),代表積木的數目(編號從0到n-1)。接下來為機器手臂的動作,每個動作一列。如果此動作為 quit ,代表此組測試資料輸入結束。你可以假設所有的動作都符合上述的樣式。請參考Sample Input。

Output

每組測試資料輸出桌面上各位置積木的情形(每個位置一列,也就是共有n列),格式請參考Sample Output。

Sample Input

10
move 9 onto 1
move 8 over 1
move 7 over 1
move 6 over 1
pile 8 over 6
pile 8 over 5
move 2 over 1
move 4 over 9
quit
4
pile 0 over 1
pile 2 over 3
move 1 onto 3
quit

Sample Output

0: 0
1: 1 9 2 4
2:
3: 3
4:
5: 5 8 7 6
6:
7:
8:
9:
0: 0
1:
2: 2
3: 3 1

解題思考

  這題我採用雙向連結串列(Double Linked List)來做,其中move動作會清空 a 上方的積木、onto動作會清空 b 上方的積木,剩下的動作就是將 a 移動到 b 上 。

參考解答(C#)

using System;
//Author: kgame 許智涵
//http://kgame-blog.spaces.live.com/
namespace Q101_The_Blocks_Problem
{
    class Program
    {
        static Box[] boxes;
        static void Main()
        {
            string str;
            while ((str = Console.ReadLine()) != null)
            {
                int n = int.Parse(str);
                boxes = new Box[n];
                for (int i = 0; i < n; i++)
                    boxes[i] = new Box(i);

                while ((str = Console.ReadLine()) != "quit")
                    Act(str);
                for (int i = 0; i < n; i++)
                {
                    Console.Write("{0}:", i);
                    if (boxes[i].Under == null)
                        for (Box p = boxes[i]; p != null; p = p.Above)
                            Console.Write(" {0}", p.N);
                    Console.WriteLine();
                }
            }
        }

        static void Act(string m)
        {
            string[] strArr = m.Split(' ');
            Box a, b;
            a = boxes[int.Parse(strArr[1])];
            b = boxes[int.Parse(strArr[3])];
            if (a.Top == b.Top)
                return; //判斷是否在同一疊上.
            if (strArr[0] == "move")
                a.ClearAbove();
            if (strArr[2] == "onto")
                b.ClearAbove();
            a.MoveTo(b);
        }
    }

    class Box
    {
        /// <summary>
        /// 編號.
        /// </summary>
        public int N;
        /// <summary>
        /// 上面的積木.
        /// </summary>
        public Box Above;
        /// <summary>
        /// 下面的積木.
        /// </summary>
        public Box Under;
        public Box(int n)
        { N = n; }
        /// <summary>
        /// 此堆最頂端的積木.
        /// </summary>
        public Box Top
        {
            get
            {
                Box p = this;
                while (p.Above != null)
                    p = p.Above;
                return p;
            }
        }
        /// <summary>
        /// 清除上方的積木.
        /// </summary>
        public void ClearAbove()
        {
            Box p = this.Above;
            this.Above = null;
            while (p != null)
            {
                Box pn = p.Above;
                p.Under = p.Above = null;
                p = pn;
            }
        }
        /// <summary>
        /// 移動置目標.
        /// </summary>
        /// <param name="t">目標</param>
        public void MoveTo(Box t)
        {
            if (this.Under != null)
                this.Under.Above = null;
            t = t.Top;
            t.Above = this;
            this.Under = t;
        }
    }
}
參考解答(C++)
#include <iostream>
using namespace std;

class Box
{
public:
    int N;
    Box* Above;
    Box* Under;
    Box()
    { Under = Above = NULL; }

    Box* Top()
    {
        Box* p = this;
        while (p->Above != NULL)
            p = p->Above;
        return p;
    }

    void ClearAbove()
    {
        Box* p = this->Above;
        this->Above = NULL;
        while (p != NULL)
        {
            Box* pn = p->Above;
            p->Under = p->Above = NULL;
            p = pn;
        }
    }

    void MoveTo(Box* t)
    {
        if (this->Under != NULL)
            this->Under->Above = NULL;
        t = t->Top();
        t->Above = this;
        this->Under = t;
    }
};

int main()
{
    int n;
    while (cin >> n)
    {
        Box* boxes = new Box[n];
        for (int i = 0; i < n; i++)
            boxes[i].N = i;
        while (true)
        {
            char c1[5], c2[5];
            cin >> c1;
            if (c1[0] == 'q') //quit
                break;
            int an, bn;
            cin >> an >> c2 >> bn;
            Box* a = &boxes[an];
            Box* b = &boxes[bn];
            if (a->Top() == b->Top())
                continue; //判斷是否在同一疊上.
            if (c1[0] == 'm') //move
                a->ClearAbove();
            if (c2[1] == 'n') //onto
                b->ClearAbove();
            a->MoveTo(b);
        }
        for (int i = 0; i < n; i++)
        {
            cout << i << ':';
            if (boxes[i].Under == NULL)
                for (Box* p = &boxes[i]; p != NULL; p = p->Above)
                    cout << ' ' << p->N;
            cout << endl;
        }
        delete [] boxes;
    }
}

參考解答(Boo)

namespace Q101_The_Blocks_Problem
#Author: kgame 許智涵
#http://kgame-blog.spaces.live.com/
import System

def Main():
    while (str = gets()) != null:
        n = int.Parse(str)
        boxes = array(Box, n)
        for i in range(0, n):
            boxes[i] = Box(i)
        while (str = gets()) != "quit":
            s = str.Split(char(' '))
            a = boxes[int.Parse(s[1])]
            b = boxes[int.Parse(s[3])]
            continue if a.Top == b.Top
            a.ClearAbove() if s[0] == "move"
            b.ClearAbove() if s[2] == "onto"
            a.MoveTo(b)
        for i in range(0, n):
            Console.Write("{0}:", i)
            if boxes[i].IsBottom:
                p = boxes[i]
                while p != null:
                    Console.Write(" {0}", p.Number)
                    p = p.Above
            Console.WriteLine()

class Box:
    [Getter(Number)]
    _n as int
    [Property(Above)]
    _above as Box
    [Property(Under)]
    _under as Box
    
    def constructor(n as int):
        _n = n
    
    Top as Box:
        get:
            p = self
            p = p._above while p._above != null
            return p
    
    IsBottom as bool:
        get:
            return _under == null
    
    def ClearAbove():
        p = _above
        _above = null
        while p != null:
            pn = p._above
            p._under = p._above = null
            p = pn
    
    def MoveTo(t as Box):
        _under._above = null if _under != null
        t = t.Top
        t.Above = self
        _under = t

Read Full Post »

[ACM]Q118 Mutant Flatworld Expolrers

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

一個機器人的位置狀況包括了其坐標( 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
解題思考
  這題步驟雖然多,但每步都很簡單,這就不詳細說明了,請觀詳以下的程式碼。
參考解答(C#)
using System;
using System.Collections.Generic;
//Author: kgame 許智涵
//http://kgame-blog.spaces.live.com/
namespace Q118_Mutant_Flatworld_Expolrers
{
    class Program
    {
        /// <summary>
        /// 土地邊界.
        /// </summary>
        public static Point s;
        /// <summary>
        /// 死亡BOT紀錄.
        /// </summary>
        static List<Point> scent = new List<Point>();
        /// <summary>
        /// BOT的座標.
        /// </summary>
        static Point Location;
        /// <summary>
        /// BOT的方向.
        /// </summary>
        static char V;
        static void Main()
        {
            string str = Console.ReadLine();
            string[] strArr = str.Split(' ');
            s.X = int.Parse(strArr[0]);
            s.Y = int.Parse(strArr[1]);
            while ((str = Console.ReadLine()) != null)
            {
                strArr = str.Split(' ');
                Location.X = int.Parse(strArr[0]);
                Location.Y = int.Parse(strArr[1]);
                V = strArr[2][0];
                str = Go(Console.ReadLine());
                Console.WriteLine(str);
            }
        }

        /// <summary>
        /// 出發並回傳結果.
        /// </summary>
        /// <param name="acts">指令集</param>
        /// <returns></returns>
        static string Go(string acts)
        {
            foreach (char a in acts)
            {
                switch (a)
                {
                    case 'L':
                        TurnLeft();
                        break;
                    case 'R':
                        TurnRight();
                        break;
                    case 'F':
                        if (Forward())
                            break;
                        return string.Format("{0} {1} {2} LOST", Location.X, Location.Y, V);
                }
            }
            return string.Format("{0} {1} {2}", Location.X, Location.Y, V);
        }

        static void TurnLeft()
        {
            switch (V)
            {
                case 'N':
                    V = 'W';
                    break;
                case 'W':
                    V = 'S';
                    break;
                case 'S':
                    V = 'E';
                    break;
                case 'E':
                    V = 'N';
                    break;
            }
        }

        static void TurnRight()
        {
            switch (V)
            {
                case 'N':
                    V = 'E';
                    break;
                case 'E':
                    V = 'S';
                    break;
                case 'S':
                    V = 'W';
                    break;
                case 'W':
                    V = 'N';
                    break;
            }
        }

        static bool Forward()
        {
            if ((V == 'W' && Location.X == 0) || (V == 'S' && Location.Y == 0) ||
               (V == 'E' && Location.X == s.X) || (V == 'N' && Location.Y == s.Y))
            {
                if (scent.Contains(Location))
                    return true;
                else
                {
                    scent.Add(Location);
                    return false;
                }
            }
            switch (V)
            {
                case 'N':
                    ++Location.Y;
                    break;
                case 'S':
                    --Location.Y;
                    break;
                case 'E':
                    ++Location.X;
                    break;
                case 'W':
                    --Location.X;
                    break;
            }
            return true;
        }
    }

    struct Point
    {
        public int X, Y;
    }
}

Read Full Post »

[ACM]Q102 Ecological Bin Packing

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

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
解題思考
  我先列舉出三個桶子可以分配成6種狀態,分別檢察這些狀態所移動瓶子量的總和,找出最小值即可。
參考解答(C#3.0)
using System;
using System.Linq;
//Author: kgame 許智涵
//http://kgame-blog.spaces.live.com/
namespace Q102_Ecological_Bin_Packing
{
class Program
{
static void Main()
{
string str;
string[] results = { "BCG", "BGC", "CBG", "CGB", "GBC", "GCB" };
int[,] selections = { { 0, 5, 7 }, { 0, 4, 8 }, { 2, 3, 7 },
{ 2, 4, 6 }, { 1, 3, 8 }, { 1, 5, 6 } };
while ((str = Console.ReadLine()) != null)
{
int[] p = str.Split(' ')
.Select(m => int.Parse(m))
.ToArray();
int min = int.MaxValue, sum = p.Sum();
string r = "";
for (int i = 0; i < 6; i++)
{
int c = sum;
for (int j = 0; j < 3; j++)
c -= p[selections[i, j]];
if (c < min)
{
min = c;
r = results[i];
}
}
Console.WriteLine("{0} {1}", r, min);
}
}
}
}
參考解答(Boo)
namespace Q102_Ecological_Bin_Packing
#Author: kgame 許智涵
#http://kgame-blog.spaces.live.com/
import System

results = ( "BCG", "BGC", "CBG", "CGB", "GBC", "GCB" )
selections = ( ( 0, 5, 7 ), ( 0, 4, 8 ), ( 2, 3, 7 ), ( 2, 4, 6 ), ( 1, 3, 8 ), ( 1, 5, 6 ) )
while (str = gets()) != null:
p = array(int, map(str.Split(char(' ')), { m | return int.Parse(m) }))
#p = array(int, int.Parse(i) for i in str.Split(char(' ')))
 
min = int.MaxValue
sum = 0
for i in p:
sum
+= i
r = ""
for
i in range(6):
c = sum
for j in range(3):
c
-= p[selections[i][j]]
if c < min:
min
= c
r
= results[i]
print r, min

Read Full Post »

[ACM]Q113 Power of Cryptography

給你兩個整數 n(n >= 1)和 p(p >=1),你必須寫一個程式來計算出 p 的正 n 次方根。在這個問題裡,p 皆可表成 kn 的形式,其中 k 為整數。(k也就是你的程式所要求的)

Input

每組測試資料2列,第1列有1個整數 n(1 <= n <= 200),第2列有1個整數 p(1 <= p <= 10101)。 並且存在一個整數 k,(1 <= k <= 109),使得 kn=p。

Output

每組測試資料請輸出 k。

Sample Input

2
16
3
27
7
4357186184021382204544

Sample Output

4
3
1234
解題思考

  這題困擾了我好久,在想100位數的整數要開n次方根要怎麼搞,大數嗎?會吐血啦,突然頓悟Math.Pow靜態方法的第2個參數-指數,可以放浮點數來達成開指定方根的功能,只要傳入這個 1 / n 引數,答案就出來了。

參考解答(C#)
using System;
//Author: kgame 許智涵
//http://kgame-blog.spaces.live.com/
namespace Q113_Power_of_Cryptography
{
    class Program
    {
        static void Main()
        {
            string str;
            while ((str = Console.ReadLine()) != null)
            {
                int n = int.Parse(str);
                double p = double.Parse(Console.ReadLine());
                Console.WriteLine(Math.Pow(p, 1.0 / n));
            }
        }
    }
}

參考解答(Boo)

namespace Q113_Power_of_Cryptography
#Author: kgame 許智涵
#http://kgame-blog.spaces.live.com/
import System

while (str = gets()) != null:
    n = int.Parse(str)
    p = double.Parse(gets())
    print(p ** (1.0 / n))

Read Full Post »

Older Posts »