Ruby兔的ACM園地: # 800 ~ 899

顯示具有 # 800 ~ 899 標籤的文章。顯示所有文章

2011年10月22日星期六

897 - Anagrammatic Primes

一個質數表示該數只能被1與自已整除，若將一數的十進位數字重新排列可能會改變該數的質數性質，例如53是質數但35並不是質數。若我們可以任意將一個質數的十進位數字作重新排列，且不管怎麼排列所得到的新的數字皆為質數，則我們稱該數為"anagrammatic prime"，例如113, 131, 311即為anagrammatic prime。

Input

輸入資料的每一列皆有一個整數 n，其值小於10,000,000，請你找出最接近 n 且比 n 大，且位數長度與 n 等長的anagrammatic prime。當 n = 0 表示測試資料結束。

Output

請每組測試資料輸出要求範圍內的anagrammatic prime，若範圍內無任何anagrammatic prime請輸出0。

Sample Input

Sample Output

原文出處

871 - Counting Cells in a Blob

Background
在二維的方格內每個格子可能是空的或是已被填滿，被填滿的格子會與四周其他也被填滿的格子相結合變成更大一團，兩個被填滿的方格若水平、垂直或對角地相鄰，則可互相結合。本題請你找出最大一團的方格總數為何。

如下圖中有三團，最大團的方格數為5。

Input
輸入資料的第一列有一個整數表示測試資料的組數，每組資料格式如下段所述，且每組之前皆有一空白列。

每組方格以0表示空的，以1表示被填滿，請參考範例資料，最大方格規模為25x25。

Output
請輸出每組測試資料中最大團的方格總數，並以一列空行隔開。

Sample Input
1

11000
01100
00101
10001
01011
Sample Output
5

原文出處

869 - Airline Comparison

Background
航空公司對於航班的編排會定義城市間的航程，由A城市到B城市之間的航程可能需要轉機。我們定義兩間航空公司提供相同的航程，表示這兩間航空公司提供對所有城市間的連結皆相同，僅管需要轉機的次數或距離並不相同。

Problem
給定兩間航空公司的航班資訊，請你判斷這兩間航空公司是否提供相同的航程。
輸入資料的第一列有一個整數表示測試資料的組數，每組資料前皆有一列空行，其資料格式如下：

第一列有一整數N，表示第一間航空公司航班的數目。
接下來有N列航班資訊，每列有兩個字元分別表示出發城市與目地城市的名稱，並以一個空白字元隔開。
第N+2列有一整數M，表示第二間航空公司航班的數目。
接下來有M列航班資訊，每列有兩個字元分別表示出發城市與目地城市的名稱，並以一個空白字元隔開。

若兩航空公司提供相同的航程請輸出"YES"，否則請輸出"NO"，每組輸出資料間以一列空行隔開。
Sample Input
1

6
A B
B E
A E
C F
E C
D A
7
A B
D A
E C
C F
D B
B E
D F
Sample Output
YES

原文出處

865 - Substitution Cypher

字母變換可說是一種最簡單的加密方式，本題給定字母的變換方式，請你對明文做加密。

Input

輸入資料的第一列有一個整數表示測試資料的組數，每組資料前皆有一列空行，其格式如下所述：

第一列為明文字母的資料
第二列為變換後字母的資料
接下來會有多列待加密的資料

Output

每組資料間以一列空行隔開，每組資料輸出格式如下：

第一列輸出變換後字母的資料
第二列輸出明文字母的資料
接下來輸出加密後的資料

Sample Input

1

abcdefghijklmnopqrstuvwxyz
zyxwvutsrqponmlkjihgfedcba
Shar's Birthday:
The birthday is October 6th, but the party will be Saturday,
October 5.  It's my 24th birthday and the first one in some
years for which I've been employed.  Plus, I have new clothes.
So I have cause to celebrate.  More importantly, though,
we've cleaned the house!  The address is 506-D Albert Street.
Extra enticement for CS geeks:  there are several systems in
the house, and the party is conveniently scheduled for 3 hours
after the second CSC programming contest ends (not to mention,
within easy walking distance)!

Sample Output

zyxwvutsrqponmlkjihgfedcba
abcdefghijklmnopqrstuvwxyz
Sszi'h Brigswzb:
Tsv yrigswzb rh Oxglyvi 6gs, yfg gsv kzigb droo yv Szgfiwzb,
Oxglyvi 5.  Ig'h nb 24gs yrigswzb zmw gsv urihg lmv rm hlnv
bvzih uli dsrxs I'ev yvvm vnkolbvw.  Pofh, I szev mvd xolgsvh.
Sl I szev xzfhv gl xvovyizgv.  Mliv rnkligzmgob, gslfts,
dv'ev xovzmvw gsv slfhv!  Tsv zwwivhh rh 506-D Aoyvig Sgivvg.
Ecgiz vmgrxvnvmg uli CS tvvph:  gsviv ziv hvevizo hbhgvnh rm
gsv slfhv, zmw gsv kzigb rh xlmevmrvmgob hxsvwfovw uli 3 slfih
zugvi gsv hvxlmw CSC kiltiznnrmt xlmgvhg vmwh (mlg gl nvmgrlm,
drgsrm vzhb dzoprmt wrhgzmxv)!

原文出處

855 - Lunch in Grid City

在某個城市中，所有街道像是棋盤方格似地彼此以橫向或直向地錯開，並保持相等的距離，如下圖所示。圖中的紅點表示一個人所在的位置，且必為橫、直向街道的交點。圖中的橫、直向街道皆被賦予編號。本題請你找出一個交點位置，使得該位置距離所有人的總距離為最短(此位置被視為最佳的聚會位置)，若有多組可能的解，則依序選擇最小的橫向編號位置與最小的直向編號位置。

以下圖為例，對於這11個人而言的最佳聚會位置為橫向街道編號3與直向街道編號4的交點位置。

Problem

給定城市的大小與所有人的位置，請找出最佳的聚會位置。

Input

輸入資料的第一列有一個整數T表示測試資料的組數。

每組測試資料的第一列有三個整數：S, A, F，S表示橫向街道的數目，A表示直向街道的數目(S, A <= 1000)，F表示人數(0 < F <= 50000)，接下來的F列分別表示每人的位置，每列有兩個整數分別表示該人所在的橫、直向街道編號位置。

Output

請參考範列資料輸出最佳的會議地點，每組測試資料必須獨立一列。

Sample Input

Sample Output

(Street: 1, Avenue: 1)
(Street: 3, Avenue: 4)

原文出處

850 - Crypt Kicker II

有一種簡單但不安全的加密方式是將一段文字的字母作變換，也就是將每個字母以另一個不同的字母作取代，為了保證可對密文解密，我們必須避免不同的字母以相同的字母取代。

本題請你對密文作解密，且假設密文中的每一列皆採用相同的字母變換方式，且其中有一列是由下列明文加密而來(此明文稱為關鍵句)：

the quick brown fox jumps over the lazy dog

Input

輸入資料的第一列有一個整數表示測試資料的組數，每組測試資料的格式如下段所述，並注意每組測試資料前有一列空行。

一組測試資料有許多列，每列皆以相同的變換方式加密，每列僅包含小寫字母及空白字元，且長度不超過80個字元，每組測試資料不超過100列。

Output

請對每組測試資料作解密，並在每組之間以一列空行隔開。若有多種可能的解密方式(即有多列可被解密為關鍵句)則選擇第一個找到的關鍵句來作解密。若該組資料無解，請輸出"No solution."

Sample Input

1

vtz ud xnm xugm itr pyy jttk gmv xt otgm xt xnm puk ti xnm fprxq
xnm ceuob lrtzv ita hegfd tsmr xnm ypwq ktj
frtjrpgguvj otvxmdxd prm iev prmvx xnmq

Sample Output

now is the time for all good men to come to the aid of the party
the quick brown fox jumps over the lazy dog
programming contests are fun arent they

原文出處

843 - Crypt Kicker

有一種簡單但不安全的加密方式是將一段文字的字母作變換，也就是將每個字母以另一個不同的字母取代，為了保證可對密文作解密，我們必須避免不同的字母以相同的字母取代。

本題請你對每一列密文作解密，並假設每一列密文有其不同的字母變換方式，且所有加密的字串皆從一部已知的字典中的單字所選出。

Input

輸入資料的第一列有一個整數 n 表示接下來有 n 個小寫的單字，每個單字一列，並以字典順序排列。這 n 個單字組成一部字典，即為加密的原始資料。在這 n 個單字之後有多列資料分別表示加密後的密文。字典最多不超過1000個單字，每個單字不超過16個字母。加密後的資料僅包含小寫字母與空白字元，其長度不超過80個字元。

Output

請對每一列密文作解密，若同時有多組可能的解則任一種皆可，若無可能的解則請將每個字母以星號取代作輸出。

Sample Input

6
and
dick
jane
puff
spot
yertle
bjvg xsb hxsn xsb qymm xsb rqat xsb pnetfn
xxxx yyy zzzz www yyyy aaa bbbb ccc dddddd

Sample Output

dick and jane and puff and spot and yertle
**** *** **** *** **** *** **** *** ******

原文出處

839 - Not so Mobile

下圖為秤，亦可被視為一個天平，由力矩原理可知，為了使天平兩端平衡，兩端的物重及其到支點的距離必須滿足下列關係式：Wl x Dl = Wr x Dr，其中Dl為支點左邊的長度，Dr為右邊的長度，Wl為左端的物重，Wr為右端的物重。

$\epsfbox{p839a.eps}$

若把兩端的物體以另一組天平取代，可以組成一個更複雜的天平。本題提供天平的資訊，請你寫程式判斷該組天平是否平衡。

$\epsfbox{p839b.eps}$

Input

輸入資料的第一列有一個整數，表示測試資料的組數，每組資料格式如下段所述，且每組資料前面都會有一列空行。

每組測試資料由許多列組成，每列有四個以空白字元隔開的整數，分別表示Wl Dl Wr Dr。若Wl或Wr為零，表示該端懸吊著另一個天平，且下一列即為該天平的資訊，本題視天平本身的重量為零。若Wl與Wr皆為零，則下面會有兩列天平的資訊，左邊先於右邊。

Output

若該組測試資料的天平兩端平衡，請輸出"YES"，否則請輸出"NO"，請在連續的兩組輸出之間以一列空白行隔開。

Sample Input

Sample Output

YES

原文出處

833 - Water Falls

考慮下圖中的三個線段P1, P2, P3，請將它們視為平面，假設雨水Sa從天空中垂直落下，碰到P3與P1後會沿著平面流動，最終落在地平面Ga處，同理，由Sb處掉落的雨水最終會落在Gb處。

$\epsfbox{p833a.eps}$

給定多條線段與多個點，本題請你計算落點在何處，為了簡化本問題，你可以假設不會有水平線段或是交叉的線段，且所有點(包含線段的端點)的垂直投影皆不相同。

Input

輸入的一開始會給定一個正整數，表示接下來有幾組測試資料，每組測試資料前面皆會有一空白列。
每組測試資料的一開始會給定整數NP，表示接下來有NP條線段，每條線段以兩個端點座標表示，分別為x1 y1 x2 y2(以一個空白字元隔開)。接下來會有一個整數NS表示有幾組雨水的初始位置，接下來NS列，每列有一整數對x y(以一個空白字元隔開)表示雨水的位置。

Output

請在每組測試資料中間輸出一列空白。
每組測試資料請輸出NS列分別表示落點的 x 座標。

Sample Input

1

4
14 7 3 4
11 13 16 11
1 10 6 7
2 1 4 3
3
10 4
14 14
2 13

Sample Output

10
16
2

上例的圖形繪出如下：

$\epsfbox{p833b.eps}$

原文出處

821 - Page Hopping

最新的報導指出，平均而言只需19次點擊即可從任一網頁連結到www上的任何其他網頁，也就是說，如果把每一個網頁視為圖論中的一個節點，則任兩個節點的平均路徑長度為19。

給定一張圖，可由該圖中任一啟始節點拜訪其他所有節點，你的工作是要從中找出任兩個節點的平均最短路徑長度，以下圖為例，各節點間以有向邊所連接，這表示由 a 節點連到 b 節點的邊，並不表示 b 節點連得到 a 節點。

上圖中由節點1連接到節點2, 3, 4的最短長度分別為1, 1, 2；由節點2連接到節點1, 3, 4的最短長度分別為3, 2, 3；節點3連到節點1, 2, 4的最短長度為1, 2, 3；節點4連到節點1, 2, 3的最短長度為2, 3, 1。這些長度的總和為：1 + 1 + 2 + 3 + 2 + 1 + 1 + 2 + 3 + 2 + 3 + 1 = 22，由於共有12種可能的組合，故平均長度為22/12 = 1.833(精確到小數點後三位)。

Input

輸入會有多組測試資料，每組測試資料會有任意多組整數對 a 與 b，每組整數對表示編號 a 網頁連接到編號 b 網頁，所有網頁編號皆在1 ~ 100的範圍間，每組測試資料以一對零表示資料結束，並且在最後一組資料後會有一對零表示所有測試資料結束。所有網頁皆不會有連結到自已的情況，且每一節點致少會有一條路徑可以連結到其他節點。

Output

請針對每組測試資料輸出任兩節點間的平均最短路徑長度，請輸出到小數點後三位，請參考範例資料格式。

Sample Input	Output for the Sample Input
1 2 2 4 1 3 3 1 4 3 0 0 1 2 1 4 4 2 2 7 7 1 0 0 0 0	Case 1: average length between pages = 1.833 clicks Case 2: average length between pages = 1.750 clicks

原文出處

815 - Flooded!

為了幫助欲買房的客戶評估房子淹水的風險，房地產公司將旗下的一大塊土地區分為一塊塊長寬皆為十公尺的正方形面積，提供每一小塊土地的海跋高度。由於水往低處流，所以高度較低的土地會先積水。為了簡化問題，我們假設該區域有良好的下水道管線，會把高處的積水導引到高度較低的土地，並假設積水不會被地表所吸收。

給定該地域的雨量資訊，請你計算出淹水的高度為何，及淹水的面積佔總面積的百分比率(低於水面的土地才會被水淹到)。

Input

輸入會有多組測試資料，每組資訊會給定區域中所有小塊土地的高度及雨量資訊，每組資料的一開始會給定兩個整數m, n (m, n < 30)，接下來會有 m 列，每列有 n 個整數，分別表示該區域每一塊土地的高度(每塊土地的面積為10m x 10m)，單位為公尺，正值表示高於海平面，負值表示低於海平面。最後一個整數表示該區域共累積多少立方公尺的雨量。當 m = n = 0 表示測試資料結束。

Output

請對每組測試資料輸出資料編號、淹水的高度、淹水面積佔總面積的百分比率。其格式請參考範例資料。後兩項數值請輸出到小數點後兩位，請每組資料後輸出一列空行。

Sample Input

Sample Output

Region 1
Water level is 46.67 meters.
66.67 percent of the region is under water.

原文出處

808 - Bee Breeding

下圖為正六邊形蜂巢圖案，對每一個六邊形賦予一個編號，如下圖所示：

$\epsfbox{p808.eps}$

本題給定任兩個編號，請你計算彼此之間的距離為何。例如給定編號19與30，其距離為5。

Input

輸入有許多列，每列有兩個整數a與b(a, b <= 10000)，分別表示六邊形的編號，其值皆為正整數。當a = b = 0時表示測試資料結束。

Output

請輸出每測試資料(a, b)之間的(最短)距離。

Sample Input

19 30
0 0

Sample Output

The distance between cells 19 and 30 is 5.

原文出處

2011年7月2日星期六

895 - Word Problem

美國報紙上常見到填字謎遊戲，這種遊戲要從特定幾個字母中組合出單字，如果能知道所有可能的單字總數就能簡化遊戲。

Input

輸入資料包含兩部份，第一部份為一部字典，每列一個單字表示所有可能的單字集合，且不會超過1000列，每列單字不會超過10個字元，且全為小寫字母，每個單字會照字典順序排列，最後一列為單一個 '#' (井號字元)表示字典結束。

第二部份為字謎，每個字謎一列，一個字謎最多由7個字母組成，字母間以一或多個空白字元隔開，你的目的是要判斷字典中共有多少個單字可由字謎中的字母排列組合而成。最後一列為單一個'#'表示資料結束。

Output

對於第二部份的每一個字謎請分別在不同列輸出一個整數，表示字謎可組成字典中單字的總數。

字謎中的字母不能重複使用，例如'b b o'可以組成"bob"，但不能組成"bobb"。

Sample Input

ant
bee
cat
dog
ewe
fly
gnu
#
b e w
b b e e w w
t a n c u g d
#

Sample Output

0
2
3

原文出處

訂閱：文章 (Atom)

網頁

2011年10月22日 星期六

Input

Output

Sample Input

Sample Output

Input

Output

Sample Input

Sample Output

Problem

Input

Output

Sample Input

Sample Output

Input

Output

Sample Input

Sample Output

Input

Output

Sample Input

Sample Output

Input

Output

Sample Input

Sample Output

Input

Output

Sample Input

Sample Output

Input

Output

Input

Output

Sample Input

Sample Output

Input

Output

Sample Input

Sample Output

2011年7月2日 星期六

Input

Output

Sample Input

Sample Output

2011年10月22日星期六

2011年7月2日星期六