Ruby兔的ACM園地: # 500 ~ 599

顯示具有 # 500 ~ 599 標籤的文章。顯示所有文章

2011年11月18日星期五

585 - Triangles

請參考下圖，本題請你找出類似下圖結構中最大面積的白色三角形由幾塊白色小三角形所組成，下圖中為九塊小三角形組成最大的一個三角形。

Input

輸入會有多組測試資料，每組給定一個圖形，每組的第一列有一個整數 n (1 <= n <= 100)表示三角形圖形的高度，接下來的 n 列每列分別以空白字元 # - 符號所組成，以 # 表示黑色區塊，以 - 表示白色區塊，空白字元用於讓圖形看起來像是個三角形。

三角形中每一列的 # - 字元的長度為奇數，且由2n - 1 遞減至1。

當 n = 0 表示測試資料結束。

Output

請參考範列資料格式輸出測試資料編號及其最大的三角形面積，三角形的頂點可能向上或向下。

請在每組測試資料之後輸出一列空行。

Sample Input

5
#-##----#
 -----#-
  ---#-
   -#-
    -
4
#-#-#--
 #---#
  ##-
   -
0

Sample Output

Triangle #1
The largest triangle area is 9.

Triangle #2
The largest triangle area is 4.

原文出處

2011年8月26日星期五

曼哈頓計劃初期，人們並不確切知道放射性物質的危險性，大量的工廠被建造出來提煉鈾原料與鈽原料，這些放射性物質的半成品混合物與完成品被裝在金屬桶子、玻璃瓶或紙箱中，且被放置在水泥地板的儲藏室內。工人們並不清楚他們可能會被這些放射性物質所感染，甚致引起核反應。知道事情嚴重性的工廠高階主管認為只要照著物理學家的建議，避免混合過量到足以達到臨界質量的放射性物質，就可以避免災難發生。但事情並非這麼簡單，因為人們總是會犯錯，不知道事情嚴重性的工人們粗心大意地處理核物質，過量推積可能誘發核反應的原料，災難隨時可能發生，

幸運的是，有物理學家發現事情的嚴重性，他們制定工作守則來避免過量堆積可能引發臨界反應的核物質。放置鈾塊的方法很簡單，以"U"表示鈾塊，以"L"表示鉛塊，鈾塊與鉛塊交互堆疊，鈾塊不能連續疊超過兩個，藉由這種方式可以避免鈾塊引發臨界反應(連續三個鈾塊疊在一起可能會達到臨界質量)。另外，一堆鈾、鉛塊的高度不會超過30個，因為樓層的高度最多只能疊30個。

其中有一位物理學家對此解決方案還是感到不安，他認為工人們還是可能因為粗心、教育訓練不足…等等原因導致核反應發生。他提出一個問題：工人以隨機的方式堆疊放射性鈾塊與非放射性鉛塊，使高度達到 n 塊，共有幾種可能的排列組合方式使得危險再次發生？

例如假設堆疊高度為3，則只有一種可能的組合的方式使鈾塊連續疊超過兩個：
1: UUU

若堆疊高度為4，則共有3種可能的組合方式：
1: UUUL
2: LUUU
3: UUUU

Input

輸入的每一列都有一個整數 n，每個整數表示堆疊的最大高度，0 < n <= 30。當 n = 0 表示測試資料結束。

Output

針對每組測試資料，請輸出共有幾種不同的危險組合方式。

Sample Input

4
5
0

Sample Output

3
8

原文出處

542 - France '98

世界盃足球賽已經進行到最後16強，其賽程表如下：

 1 Brazil -----+
               +-- ? --+
 2 Chile ------+       |
                       +-- ? --+
 3 Nigeria ----+       |       |
               +-- ? --+       |
 4 Denmark ----+               |
                               +-- ? --+
 5 Holland ----+               |       |
               +-- ? --+       |       |
 6 Yugoslavia -+       |       |       |
                       +-- ? --+       |
 7 Argentina --+       |               |
               +-- ? --+               |
 8 England ----+                       |
                                       +-- 世界杯冠軍
 9 Italy ------+                       |
               +-- ? --+               |
10 Norway -----+       |               |
                       +-- ? --+       |
11 France -----+       |       |       |
               +-- ? --+       |       |
12 Paraguay ---+               |       |
                               +-- ? --+
13 Germany ----+               |
               +-- ? --+       |
14 Mexico -----+       |       |
                       +-- ? --+
15 Romania ----+       |
               +-- ? --+
16 Croatia ----+

對於所有A vs. B 的對戰組合中，給定A贏B的機率，可以算出每一隊贏得世界盃冠軍的機率，例如德國贏墨西哥的機率為80%，羅馬尼亞贏克羅埃西亞的機率為60%，德國贏羅馬尼亞的機率為70%，德國贏克羅埃西亞的機率為90%，則德國贏得半準決賽的機率為 80% * (70% * 60% + 90% * 40%) = 62.4%。

請你寫一個程式計算這16隊贏得世界盃冠軍的機率為何。

Input

輸入僅包含一組測試資料。
前16列為參賽國家的名稱，同上面的賽程表。接下來有一個16 x 16 矩陣P，每個矩陣元素pij分別表示國家#i 贏國家#j的百分比勝率，例如上表中Brazil表示#1，Germany表示#13，則 p1, 13 = 55表示Brazil贏Germany的機率為55%。對於所有i, j，pij + pji = 100成立。

Output

請輸出16列，其格式為"XXXXXXXXXX p=Y.YY%"表示每一隊的勝率，其中XXXXXXXXXX表示隊名，以十個字元寬向左對齊，Y.YY表示勝率，請輸出到小數點後兩位。每一列的輸出順序比照輸入資料國家的順序。

Sample Input

Brazil
Chile
Nigeria
Denmark
Holland
Yugoslavia
Argentina
England
Italy
Norway
France
Paraguay
Germany
Mexico
Romania
Croatia
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50
35 50 35 45 40 35 35 50 30 40 25 40 25 40 35 35
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50
40 55 40 50 45 40 40 55 35 45 30 45 30 45 40 40
45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50
35 50 35 45 40 35 35 50 30 40 25 40 25 40 35 35
55 70 55 65 60 55 55 70 50 60 45 60 45 60 55 55
45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45
60 75 60 70 65 60 60 75 55 65 50 65 50 65 60 60
45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45
60 75 60 70 65 60 60 75 55 65 50 65 50 65 60 60
45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50

Sample Output

Brazil     p=8.54%
Chile      p=1.60%
Nigeria    p=8.06%
Denmark    p=2.79%
Holland    p=4.51%
Yugoslavia p=7.50%
Argentina  p=8.38%
England    p=1.56%
Italy      p=9.05%
Norway     p=3.23%
France     p=13.72%
Paraguay   p=3.09%
Germany    p=13.79%
Mexico     p=3.11%
Romania    p=5.53%
Croatia    p=5.53%

原文出處

539 - The Settlers of Catan

1995年推出的遊戲"卡坦島拓荒"(Settlers of Catan)曾榮獲德國年度遊戲大賞，玩家們必須在資源豐沛的荒島上拓荒，在未知的領域上開拓殖民地、建造道路與城市。你現在被雇用來設計該遊戲的電腦版本，並請你實作該遊戲的的一項特殊規則：路王

遊戲結束時，擁有最長道路的玩家為路王，並獲得額外的三分獎勵。

問題是每個玩家所建造的道路網路較為複雜，並非只是直線路段，所以決定最長路徑並非一項易事(但通常人眼可以直覺的分辨出來)。
不同於原始遊戲有制定許多額外的規則，例如當道路被對方玩家以城市截斷時，不計入總長度，在此我們不必考慮這些額外的規則，只需考慮最簡化的情況：給定一些節點(城市)與連接節點且長度為1的邊(路段)，最長的路徑限定為網路內同一個邊只計算一次的路徑，但同個節點可拜訪超過一次。
例如下圖網路中，最長路徑長為12。

o        o -- o        o
 \      /      \      /
  o -- o        o -- o
 /      \      /      \
o        o -- o        o -- o
               \      /
                o -- o

Input

輸入有多組測試資料。每組測試資料的第一列有兩個整數：n (2 <= n <= 25)表示節點數，m (1 <= m <= 25)表示邊數，接下來有 m 列，每列表示一個連接兩個節點的邊，節點的編號為0 ~ n-1，邊沒有方向性，一個節點最多連接三個邊，網路並非是連通的。
當 n = m = 0 表示測試資料結束。

Output

請針對每組測試資料輸出最長路徑長度。

Sample Input

Sample Output

2
12

原文出處

531 - Compromise

有兩組單字集合，請你找出最長的共同單字子序列(the longest common subsequence of words)。

Input Specification

輸入有多組測試資料。每組資料有兩段文字，每段文字僅包含小寫的單字，並以空白字元隔開，且不會有任何標點符號。每個單字最長30個字元，每段文字最多有100個單字，並以一列#符號表示結束。

Output Specification

請每組測試資料輸出這兩段文字的最長子序列單字，若有多組不同的解，輸出任何一組都可以。每個單字請以空白字元隔開，最後一個單字後請輸出換行符號。

Sample Input

die einkommen der landwirte
sind fuer die abgeordneten ein buch mit sieben siegeln
um dem abzuhelfen
muessen dringend alle subventionsgesetze verbessert werden
#
die steuern auf vermoegen und einkommen
sollten nach meinung der abgeordneten
nachdruecklich erhoben werden
dazu muessen die kontrollbefugnisse der finanzbehoerden
dringend verbessert werden
#

Sample Output

die einkommen der abgeordneten muessen dringend verbessert werden

原文出處

2011年8月13日星期六

507 - Jill Rides Again

吉兒喜歡騎著她的折疊式腳踏車兜風，她會帶著腳踏車搭上公車，然後選擇一個停靠站下車之後，開始沿著公車行駛路徑騎著她的腳踏車，然後在另一個停靠站搭公車回家。事實上，她會從公車行駛路線上的停靠站中選擇起點與終點來騎車。
兩個相鄰停靠站間的路線景色有好有壞，吉兒對停靠站間的每一小段路的喜好程度並不相同，我們用"偏好值"來表示，偏好值愈大表示吉兒愈喜歡騎那一段路。偏好值為正或負值，但不為零。由於吉兒會從某一個停靠站下公車之後，沿路騎腳踏車，然後再到之後的停靠站搭車回家，她希望她騎的那一段路之偏好值之總和最大，本題會給你各站牌間所有路段的偏好值，請你幫吉兒選擇起點站與終點站，使得路線上之偏好值總和最大化。

Input

輸入會有多組測試資料，分別為公車路線資料訊。輸入的第一列有一個整數 b 表示公車路線總數，接下來共有 b 組公車路線。每組路線的第一列會給定站牌總數 s (2 <= s <= 20,000)，之後會有 s-1 列，每列分別表示站牌間路段的偏好值，以 ni 表示(1 <= i < s)。

Output

請針對每組測試資料 r (1 <= r <= b)，輸出起點站 i 與終點站 j，使得 i j 之間的路徑之偏好值總合最大化，即 max = n(i) + n(i+1) + ... + n(j-1)。若有多組符合要求的路徑，請輸出 j - i 最大的那組，若還是有多組選擇，請輸出 i 值最小的那組，其輸出格式為：
The nicest part of route r is between stops i and j

然而，如果最佳路徑之偏好值總合小於或等於零，請輸出：
Route r has no nice parts

Sample Input

Sample Output

The nicest part of route 1 is between stops 2 and 3
The nicest part of route 2 is between stops 3 and 9
Route 3 has no nice parts

原文出處

2011年8月12日星期五

558 - Wormholes

西元2163年，人類發現蟲洞，蟲洞是一條時空隧道，可以穿梭於星系間的時空，它有幾個特點：

蟲洞是單向的。
蟲洞內的移動時間可被忽略。
蟲洞有兩個端點，分別處在兩個不同的星系。
一個星系可能會有多條蟲洞的端點。
基於某種不明的原因，由我們地球所處的星系出發，一定可以藉由一或多條蟲洞到達其他任一星系。
由A星系到B星系的蟲洞最多只有一條。
不會有起點與終點皆在同一星系的蟲洞。

蟲洞的兩個端點間會有時差，例如，某條蟲洞可以讓人穿越到15年後的未來，而另一條蟲洞可以讓人回到42年前的過去。

有一位住在地球上的天才物理學家，她想藉由蟲洞旅行回到宇宙創始的時候，親自到那個時空研究大爆炸理論(Big Bang)。她想找出是否有一條循環路徑可以讓她回到無止盡的過去，帶她回到宇宙創始之際。請你寫一個程式判斷這樣的循環是否存在。

Input

輸入的第一列有一個整數 c 表示測試資料的組數。每組測試資料的第一列有兩個整數 n 與 m，分別表示星系總數n(1 <= n <= 1000)與蟲洞總數m(0 <= m <= 2000)。星系的編號由 0 開始到 n-1 結束(以編號 0 的星系為出發點)，接下來有 m 列表示蟲洞的資料，每列有三個整數 x, y, t，分別表示由 x 星系到 y 星系的蟲洞能讓人旅行到 t 年後的未來(-1000 <= t <= 1000)。

Output

輸出共有 c 列，每列表示每組測試資料的結果，若可以找到無止盡回到過去的循環請輸出"possible"，若不行請輸出"not possible"。

Sample Input

Sample Output

possible
not possible

原文出處

2011年5月21日星期六

545 - Heads

投擲一枚公平的硬幣使其連續出現n次正面的機率為 2^-n

Input

第一列有一整數r，指示接下來有 r 個整數 n，其中: $0< n \le 9000$ .

Output

對於所有r個n值，請輸出2^-n的值，其格式為：

2^-n = x.xxxE-y

其中x為0~9的整數(譯注：限制 x.xxx >= 1 才會與y有唯一解，故小數點前面的整數不可為零)，y為整數。

Sample Input

Sample Output

2^-6 = 1.563E-2
2^-8271 = 1.517E-2490
2^-6000 = 6.607E-1807
2^-1 = 5.000E-1

請特別注意當n=6時的答案
與474題是一樣的題目，只差在輸出格式中e與E的不同，但是兩邊的解在n=6是不同的。
原文出處

2010年9月8日星期三

567 - Risk

有一種桌上型遊戲叫Risk，玩家們要彼此攻城略地征服全世界，遊戲桌上有一個世界地圖，地圖上有許多國家。遊戲進行中，玩家的軍隊會駐紮在某一個國家，該軍隊只能攻擊鄰近的國家，隨著遊戲的進行不斷侵略與擴張，軍隊能在已被征服的國家間自由地移動。

隨著遊戲的進行，玩家們若需要調度兵力由一處移到另一處，就必須將路途上所有國家一一征服，通常玩家都會優先選擇介於兩地之間的國家，這樣能使需要侵略的國家數目降到最低。給定一張地圖上20個國家的相對位置關係圖，你必須寫一個程式計算從一地到另一地最少需要征服幾個國家，你不需要列出侵略的順序，只需要計算侵略國家的總數即可，例如，若起點位置與終點位置相鄰，則你的程式要輸出1。

第一組測試資料的位置關係如下圖所示：

Input

輸入會有多組測試資料，每組測試資料一開始會有19列，分別表示與前19個國家相鄰的國家，例如第一列會列出與編號1的國家互為鄰國關係的所有國家。為了避免列出重覆的資料，所列出與國家 I 相鄰的國家 J 必定是 I < J，在第 I 列上(I小於20)會有一個整數X，表示該列接下來會有X個整數，每個整數必定大於 I 且不會超過20。一組測試資料的第20列會是一個整數N( $1 \le N \le 100$ ) ，表示接下來會有N對整數，每一對整數表示侵略國家的起點與終點位置。( $1 \le A,B \le 20; A \ne B$ )。

輸入檔案會有多組測試資料，你的程式必須持續讀入直到遇見EOF為止。所有給定的國家之間必定存在最少一條路徑。

Output

輸出的資料請參考Sample Output，其格式為"Test Set #T"，T表示測試資料的編號，請靠#字號對齊。

接下來的N列請輸出由起點到終點最少需征服的國家數目，其格式請參考Sample Output，第一、二個字元為起始國家，第七、八個字元為終點國家，兩國的最小移動距離請在第11個字元處靠左對齊。每組測試資料之後請輸出一列空行。

Sample Input

1 3
2 3 4
3 4 5 6
1 6
1 7
2 12 13
1 8
2 9 10
1 11
1 11
2 12 17
1 14
2 14 15
2 15 16
1 16
1 19
2 18 19
1 20
1 20
5
1 20
2 9
19 5
18 19
16 20
4 2 3 5 6
1 4
3 4 10 5
5 10 11 12 19 18
2 6 7
2 7 8
2 9 10
1 9
1 10
2 11 14
3 12 13 14
3 18 17 13
4 14 15 16 17
0
0
0
2 18 20
1 19
1 20
6
1 20
8 20
15 16
11 4
7 13
2 16

Sample Output

Test Set #1
 1 to 20: 7
 2 to  9: 5
19 to  5: 6
18 to 19: 2
16 to 20: 2

Test Set #2
 1 to 20: 4
 8 to 20: 5
15 to 16: 2
11 to  4: 1
 7 to 13: 3
 2 to 16: 4

原文出處

2010年9月6日星期一

594 - One Little, Two Little, Three Little Endians

寫一個能完全相容於不同作業系統、不同系統版本與硬體平台的程式是一件困難的事，其中一個困難點在於不同的硬體製造商會選擇不同的方式來儲存記憶體中的整數資料，由於不同的平台有不同的表示方式，所以平台間的資料傳輸必須考慮到彼此間的差異並做出調整。

幸運的是，目前硬體製造商之間普遍存在一種共識，皆把記憶體以8個位元(8-bit)為一個位元組(byte)的方式定址，但是當整數資料長度超過8-bits時(例如2 bytes, 4 bytes, 8 bytes)，就沒有固定的定址方式，這衍生出兩種不相容的儲存格式，第一種整數的儲存方式是把最低的字元組(least significant byte)定址在較底的記憶體位置，並把最高的字元組(most significant byte)定址在較高的記憶體位置，而另一種方式則剛好相反，最低的字元組(least significant byte)定址在較高的記憶體位置，並把最高的字元組(most significant byte)定址在較低的記憶體位置。這兩種方式分別被稱為小頭端與大頭端(Little Endian, Big Endian)。另外整數的儲存還有另一種普遍的做法是以「二進制補碼(two's complement)」表示，而本題就是用這種方式。

當整數資料分別在以不同編碼方式的機器(Little Endian and Big Endian)之間共享時，就必須把資料的各個位元組反轉，當所有位元組都被反轉之後，不同編碼方式的資料就能以正確的方式解讀。本題的目的是要寫一個程式從輸入中取得一連串的整數，並把所有整數以另一種編碼方式表示出來。

Input

輸入會有許多整數，每個整數一列，並以EOF表示檔案結束。所有整數皆能以32-bit的有號整數表示(32-bit signed integer)，也就是說其值介於-2147483648 到 2147483647之間。

Output

請將輸出以每個整數一列的方式印出來，輸出的格式請參考Sample Output。

Sample Input

Sample Output

123456789 converts to 365779719
-123456789 converts to -349002504
1 converts to 16777216
16777216 converts to 1
20034556 converts to -55365375

原文出處

2010年7月25日星期日

575 - Skew Binary

當一數值以十進位表示時，第k位數表示10^k(十進制由右至左編碼，最低有效位數為第0位)。例如：

$\begin{displaymath}81307_{10} = 8 \times 10^4 + 1 \times 10^3 + 3 \times 10^2 + ... ...mes 10^1 + 7 \times 10 0 = 80000 + 1000 + 300 + 0 + 7 = 81307. \end{displaymath}$

當一數值以二進制表示時，第k位數表示2^k。例如：

$\begin{displaymath}10011_2 = 1 \times 2^4 + 0 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 = 16 + 0 + 0 + 2 + 1 = 19. \end{displaymath}$

當一數值以"斜偏二進制(Skew Binary)"表示時，第k位數表示 2^k+1 - 1。除了最低非零的位數可能等於2之外，所有數值皆為0或1。例如：

$\begin{displaymath}10120_{skew} = 1 \times (2^5 - 1) + 0 \times (2^4-1) + 1 \tim... ...2 \times (2^2-1) + 0 \times (2^1-1) = 31 + 0 + 7 + 6 + 0 = 44. \end{displaymath}$

前十個斜偏二進制(skew binary)的數值為0, 1, 2, 10, 11, 12, 20, 100, 101, 102。(skew binary在某些領域特別有用，因為它使一數值加上1之後，最多只進位一次，但這方面的議題與本題目無關)

10120
200000000000000000000000000000
10
1000000000000000000000000000000
11
100
11111000001110000101101102000
0

Sample Output

原文出處

訂閱：文章 (Atom)

網頁

2011年11月18日 星期五

Input

Output

Sample Input

Sample Output

2011年8月26日 星期五

Input

Output

Sample Input

Sample Output

Input

Output

Sample Input

Sample Output

Input

Output

Sample Input

Sample Output

Input Specification

Output Specification

Sample Input

Sample Output

2011年8月13日 星期六

Input

Output

Sample Input

Sample Output

2011年8月12日 星期五

Input

Output

Sample Input

Sample Output

2011年5月21日 星期六

2010年9月8日 星期三

2010年9月6日 星期一

2010年7月25日 星期日

2011年11月18日星期五

2011年8月26日星期五

2011年8月13日星期六

2011年8月12日星期五

2011年5月21日星期六

2010年9月8日星期三

2010年9月6日星期一

2010年7月25日星期日