顯示具有 # 700 ~ 799 標籤的文章。 顯示所有文章
顯示具有 # 700 ~ 799 標籤的文章。 顯示所有文章

2011年10月22日 星期六

785 - Grid Colouring

本題請你對平面圖形作填滿色彩的動作，圖形中以 X 表示輪郭，以空白字元表示未被填入色彩的區塊，並以其他字元表示「被標示的區塊」。

每一個圖塊定義為被封閉輪廓包圍的所有相連的部份，請你將一個圖塊以其中的「被標示」字元來填滿。

Input

每組測試資料以一列底線( _ )隔開，每組最多30列，每列最多80個字元，每列的長度不見得相同。

Output

請與輸入資料完全相同的格式輸出已被填滿色彩的圖形。

Sample Input 

  XXXXXXXXXXXXXXXXXXXX
  X      X           X
  X # #  XXXXXXXX /  X
  X             X    X
  XXXXXXXXXXXXXXXXXXXX
_____________________________

   XXXXXXXXXXXX       XXXXXX
  X       #   XXX  XXX   X X
  X  XX         X  X     X X
 X  X  X  XXXXXXX  XXXXXXX
 X   XX   X
  X       X  XXXX  XXXXXXXX
   XX     XXXX  X  X  /   X
    X           X  X    / X
    XXXXXXXXXXXXX  XXXXXXXX
_____________________________

Sample Output 

  XXXXXXXXXXXXXXXXXXXX
  X######X///////////X
  X######XXXXXXXX////X
  X#############X////X
  XXXXXXXXXXXXXXXXXXXX
_____________________________

   XXXXXXXXXXXX       XXXXXX
  X###########XXX  XXX   X X
  X##XX#########X  X     X X
 X##X  X##XXXXXXX  XXXXXXX
 X###XX###X
  X#######X  XXXX  XXXXXXXX
   XX#####XXXX##X  X//////X
    X###########X  X//////X
    XXXXXXXXXXXXX  XXXXXXXX
_____________________________

原文出處
沒有留言:

759 - The Return of the Roman Empire


Input and Output

請你寫一個程式將羅馬數字轉換成阿拉伯數字輸出。羅馬數字中 I=1, V=5, X=10, L=50, C=100, D=500, M=1000，且IV=4, IX=9, XL=40, XC=90, CD=400, CM=900。當羅馬數字格式錯誤時請輸出"This is not a valid number"。

Sample Input 

MCMXCVIII
CCM

Sample Output 

1998
This is not a valid number

原文出處
沒有留言:

737 - Gleaming the Cubes


本題請你計算一組位方體彼此之間重疊的體積為何。

Input and Output

輸入包含多組測試資料，每組測試資料的第一列有一個整數 n (2 <= n <= 1000)表示立方體的數目，接下來有 n 列，每列有四個整數分別表示立方體的位置與大小，前三個整數表示座標 (x, y, z)，第四個整數表示立方體的大小，立方體必然平行於三個座標軸。當 n = 0 表示測試資料結束。
測試資料最少有一組，且每組重疊的體積必不超過1,000,000單位體積。

Sample Input 

2
0 0 0 10
9 1 1 5
3
0 0 0 10
9 1 1 5
8 2 2 3
0

Sample Output 

25
9

原文出處
沒有留言:

732 - Anagrams by Stack


堆疊式的操作如何使一個字串轉換成另一個字串呢？下面是將TROT轉換成TORT的兩個例子：
[
i i i i o o o o
i o i i o o i o
]
以 i 表示放入推疊(Push)，以 o 表示從推疊中取出(Pop)。給定兩個字串，請你計算能將第一個字串轉換成第二個字串的所有堆疊式操作方式。

Input 

測試資料兩兩一組，每組的第一個字串視為原始字串，第二個字串視為目標字串。

Output 

請輸出能將原始字串轉換為目標字串的所有操作方式，每一組操作方式請以下列符號區隔：
[
]
每組輸出請以字串順序排列，每一個 i, o 之間請以一個空白字元隔開，如範例資料所示。

Sample Input 

madam
adamm
bahama
bahama
long
short
eric
rice

Sample Output 

[
i i i i o o o i o o
i i i i o o o o i o
i i o i o i o i o o
i i o i o i o o i o
]
[
i o i i i o o i i o o o
i o i i i o o o i o i o
i o i o i o i i i o o o
i o i o i o i o i o i o
]
[
]
[
i i o i o i o o
]

原文出處
沒有留言:

711 - Dividing up

馬修與比爾兩人共同擁有一堆彈珠，他們打算平分所有彈珠，但是因為每顆彈珠的價值都不一樣，所以平分所有彈珠的工作並非那麼簡單。他們為每顆彈珠分別賦與1~6的價碼，希望平分後兩人所擁有的彈珠總值是一樣的。

不過用這種方式並不保證一定能將所有彈珠分成等值的兩堆，例如價值1~6的彈珠顆數分別為：1, 0, 1, 2, 0, 0時就無法等值平分。請你寫一個程式判斷是否存在能等值平分彈珠的方式。

Input

輸入的每一列表示一組測試資料，分別為價值1~6的彈珠數目，總彈珠數目不會超過20000顆。以六個零表示測試資料結束。

Output

每組測試資料的第一列請輸出"Collection #k:"，其中 k 表示測試資料的編號，若該組資料可被平分則在第二列輸出"Can be divided."，否則請輸出"Can't be divided."。請在每組測試資料後輸出一列空行。

Sample Input 

1 0 1 2 0 0
1 0 0 0 1 1
0 0 0 0 0 0

Sample Output 

Collection #1:
Can't be divided.

Collection #2:
Can be divided.

原文出處
沒有留言:

705 - Slash Maze


利用斜線(/)與反斜線(\)可用來產生一組迷宮，如下圖所示：

本題著重在探討迷宮中的封閉路徑，計算封閉路徑總數及其中最長的路徑長度，如上圖中有兩個封閉路徑，路徑長度是以小方格的數目來做計算。上圖中的最長路徑長度為16，最短的路徑長度為4。

Input

輸入資料會包含多組迷宮資訊，每組迷宮的第一列有兩個整數 w 與 h (1 <= w, h <= 75)，表示迷宮的寬度與長度。接下來的 h 列，每列有 w 個'/'或'\'字元表示迷宮。當 w = h = 0 表示測試資料結束。

Output

請對每組測試資料輸出一列"Maze #n:"，其中 n 表示迷宮編號，接下來輸出"k Cycles; the longest has length l."，其 中 k 表示封閉路徑數，l 表示最長封閉路徑長度。若迷宮中沒有任何封閉路徑，請輸出"There are no cycles."。

請在每組輸出資料後多輸出一空白列。

Sample Input 

6 4
\//\\/
\///\/
//\\/\
\/\///
3 3
///
\//
\\\
0 0

Sample Output 

Maze #1:
2 Cycles; the longest has length 16.

Maze #2:
There are no cycles.

原文出處
沒有留言:

2011年7月27日 星期三

739 - Soundex Indexing

本題請你利用Sundex Index System來進行編碼，你的任務是要把許多名字編碼成soundex code，並將名字與編碼的結果輸出。

輸入的名字為長度1~20的全大寫字串，且不會有空白字元。

 

How to generate the Soundex Code: 

Sundex Code編碼一定是一個字母後面接三個位數的數字，編碼的原則如下：
  1. 名字的第一個字母就是編碼後的第一個字母，而且也是唯一一個字母。
  2. 字母A, E, I, O, U, Y, W, H不作編碼，但具有區隔連續數字編碼的作用(請參考下一個規則)。
  3. 除上述幾個字母不作編碼外，其他字母皆需進行編碼，但有一個例外是：如果該字母與上一個字母的編碼一致(包含第一個字母)，則不進行編碼。
  4. 若編碼後的長度太短，請用0補滿到三個位數。
  5. 編碼到3個位數之後則結束，請捨棄剩下的字母。
  6. 編碼表如下：
CodeKey Letters and Equivalents
1B, P, F, V
2C, S, K, G, J, Q, X, Z
3D, T
4L
5M, N
6R


Input 

輸入的每一列都會有一個名字，每個名字不超過20個字元，且只會有大寫字母。讀到EOF表示輸入資料結束。

 

Output 

輸出的資料會有兩欄，第一欄為編碼前的名字，第二欄為編碼後的資料，請在第一列輸出兩欄位的標頭"NAME"與"SOUNDEX CODE"，且請對齊從左邊數來第10與第35個字元的位置，每筆資料請以此方式對齊輸出。並請在最後一列第20個字元的位置輸出"END OF OUTPUT"。

Sample Input 

LEE
KUHNE
EBELL
EBELSON
SCHAEFER
SCHAAK

Sample Output 

         NAME                     SOUNDEX CODE
         LEE                      L000
         KUHNE                    K500
         EBELL                    E140
         EBELSON                  E142
         SCHAEFER                 S160
         SCHAAK                   S200
                   END OF OUTPUT
         |         |              |
         |         |              |__ 位置35
         |         |__ 位置20
         |__ 位置10

原文出處
沒有留言:

2011年7月26日 星期二

784 - Maze Exploration

下圖a的四方形迷宮是由多個3x3的房間所組成，房間以通道連接。迷宮的牆面以任意字元表示，但表示牆面的字元不會是'*', '_', ' '(空白字元)，例如下圖中以'x'表示牆面，房間與通道的地方以空白字元表示。
XXXXXXXXXXXXXXXXXXXXX             XXXXXXXXXXXXXXXXXXXXX
X   X   X   X   X   X             X###X###X###X   X   X
X           X   X   X             X###########X   X   X
X   X   X   X   X   X             X###X###X###X   X   X
XXXXXX XXX XXXXXXXXXX             XXXXXX#XXX#XXXXXXXXXX
X   X   X   X   X   X             X   X###X###X###X###X
X   X     *         X             X   X###############X
X   X   X   X   X   X             X   X###X###X###X###X
XXXXXXXXXXXXXXXXXXXXX             XXXXXXXXXXXXXXXXXXXXX
a) 輸入迷宮                                                         b) 輸出迷宮
Figure 1. 由3x3大小的房間所組成的迷宮

每個房間四週的寬度為3，且牆的厚度為1，這表示房間大小皆為3x3，且通道為1x1，而通道的門一定是在牆壁的中央。迷宮的四週不會有對外的通道。

有三個門的房間：
                       |
                     XX XX
                     X . X
               door - ...--  房間大小為3x3
                     X . X__
                     XXXXX  |
                       |___  牆的厚度為1
Figure 2. 有三個門的房間

本題請你表示出：從特定房間出發所能走訪的房間與通道，出發的房間的正中央會以'*'來表示，兩個房間必須要有通道連接才能相通，可走訪的房間與通道請以'#'來取代原先的空白字元。如上圖 b 所示。

Input

輸入的第一列有一個表示迷宮數量的整數，接下來每一列用來表示所有迷宮的地圖。
每組迷宮的大小可能不會相同，且不同迷宮以一列由'_'底線字元組成的字串隔開，每個迷宮最多以30列字串表示，且每列不超過80個字元。

Output

請以'#'標記出可走訪的房間與通道，並輸出此迷宮，輸出必須包含以底線組成的分隔線，請參考範例輸出。

Sample Input 

2
XXXXXXXXX
X   X   X
X *     X
X   X   X
XXXXXXXXX
X   X
X   X
X   X
XXXXX
_____
XXXXX
X   X
X * X
X   X
XXXXX
_____

Sample Output 

XXXXXXXXX
X###X###X
X#######X
X###X###X
XXXXXXXXX
X   X
X   X
X   X
XXXXX
_____
XXXXX
X###X
X###X
X###X
XXXXX
_____

原文出處
沒有留言:

2011年6月17日 星期五

701 - The Archeologists' Dilemma

為了尋找外星人曾存在地球的證據，考古學家們正在研究一道半毀的牆，牆上畫有一串奇怪的數字，所有數字的左半部都是完整的，但右半部則由於牆壁長久以來侵蝕的結果已經變得不可辨認，但由於少部分完全未被侵蝕的數字全為2的指數倍，所以他們推斷所有數字亦為2的指數倍(2的E次方)。為了確認這點，考古學家選擇一些左半部(可見)長度小於右半部(不可見)的數字，請你找出這些數是否可能為2的E次方？求最小的E值。

本題會提供一些整數給你，並要求你寫一個程式找出最小的E值，使得2^E的最前面的數字等於提供給你的整數(注意，這些數值後半部不可見的長度大於前半部可見的長度)。

Input 

輸入的每一列會有一個正整數N，最大不會超過2147483648。

Output 

對於每個輸入N，請你找最小的E值，使得2^E的最前面的數字完全等於N。若找不到請輸出"no power of 2"。

Sample Input 

1
2
10

Sample Output 

7
8
20

hint: 單純使用double可能會有問題，請改用 long double
原文出處
沒有留言:
訂閱： 文章 (Atom)