?? ?? 題一 ? ?? “自身數字”問題

?

??? 源文件： self???????? 輸入文檔：沒有 ???????? 輸出：屏幕 ??????????????? 50 分

?

? 問題描述

?

1949 年，印度數學家D.R.Kaprekar發現了一類被稱作“自身數值”的數字：

?

對于任一個正整數n，定義函數d（n）為n加上它的各位數字的和。（d代表digitadition，是kaprekar造出來的術語）。

?

舉例來說，d（75）=75+7+5=87。以任意一個正整數n為起點，可以構造一個無窮的遞增的整數序列：n,d（n），d（d（n）），d（d（d（n））），……

?

例如：以33為起點，下一個數字是33+3+3=39，再下一個數字是39+3+9=51，再下一個數字是51+5+1=57，以此類推可以產生序列：

33 ，39，51，57，69，84，96，111，114，120，123，129，141，……

?

?n 被稱作d（n）的“產生者”。

在上面的序列中，33是39的“產生者”，39是51的“產生者”，51是57的“產生者”，……。

?

有些數字會有不止一個“產生者”：舉例來說，101有兩個“產生者”，它們是91和100。

?

如果一個數字沒有“產生者”，那么這個數字叫做“自身數字”。在小于100的數字中有13個“自身數字”：1，3，5，7，9，20，31，42，53，64，75，86，和97。

?

請寫一個程序，按遞增順序輸出所有大于0小于10000的所有的“自身數字”，每一行輸出10個數字（最后一行可少于10個）。

?

? 示范輸出

?

1? 3? 5? 7?? 9?? 20?? 31?? 42?? 53??? 64

?

?|

?|?????? <-- a lot more numbers

?|

?

?

?

?

?

?

?

?

??????? ?????????????? 題二 ??????? ?? 尋找長方形

?? 源文件 :rect.?????????? 輸入文檔 :rect.in???????????? 輸出：屏幕 ????????? 150 分

?

? 問題描述

觀察圖1a,2a,3a 中的圓點。圖1b,2b和3b中畫出了所有水平方向和垂直方向上均以所給出的圓點為頂點的長方形。圖4中的點不能組成任何的長方形。

? ??????????????

請寫一個程序：對于給定的一組圓點，找出所有可能的長方形。下面將給出關于上面幾個圖的輸入和輸出的示例。

?

輸入文檔要包含1個以上的圓點集合，最后以0結尾表示輸入文檔結束。每一個圓點集合的第一行是正整數n，表示共有圓點的數目，其后的n行表示圓點的狀態。每個圓點的表示格式是：先用一個大寫字母來代表一個圓點，其后空格，然后是該圓點的橫坐標，再空格，最后是該圓點的縱坐標。每一組圓點集合中，表示圓點的大寫字母應按字母表的順序使用。注意，因為每個點需要用一個大寫字母表示，所以至多可以有26圓點。所有的坐標是小于50的非負整數。每組集合的各個圓點彼此是獨立的。

每組圓點集合的輸出要以“point set”作為開始，后面加上一個表示該組圓點編號的數字和一個冒號。如果不能組成長方形，則在冒號后面輸出“no rectangles”。如果可以組成長方形，則另起一行，列出這些長方形。每個長方形前面先空一格。長方形以它頂點的字母來表示，從左上角開始，按順時針順序列出。即列出頂點的順序是：左上角 à 右上角 à 右下角 à 左下角。每一行列出十個長方形，最后一行可以列出少于10個長方形。按字母表的順序列出長方形。

?

? 示范輸入

7????????

A 1 1????

B 2 1????

C 3 1????

D 2 3??? ?

E 3 3????

F 1 4????

G 3 4????

8????????

B 1 1?????

D 2 1?????

F 4 1?????

J 4 4?????

L 2 4

M 2 3

N 4 3?????

P 1 2?????

12

A 1 5

B 2 5

C 1 4

D 2 4

E 1 3

F 2 3

G 1 2

H 2 2

I 1 1

J 2 1

K 1 0

L 2 0

5

B 1 1

D 2 1

L 2 4

N 2 3

P 1 2

0

?

? 示范輸出

Point set 1:

?DECB FGCA

Point set 2:

?LJFD LJNM MNFD

Point set 3:

?ABDC ABFE ABHG ABJI ABLK CDFE CDHG CDJI CDLK EFHG

?EFJI EFLK GHJI GHLK IJLK

Point set 4: No rectangles

?

?

???????????????? 題三 ??? ?? 交換比率問題

?? 源文件 : exchange.????? 輸入文檔 : exchange.in ??????? 輸出 : 屏幕 ?????? ????250 分

?

? 問題描述

用紙幣來支付商品和服務的費用可以使生活方便，可是人們有時希望能夠直接交換物品而不使用錢幣來作媒介。為了確保一致的“價格”，商人們制訂了一個關于商品的交換比率。我們用正整數m和n來表示商品A和B的交換比率，并說m個商品A等價于n個商品B。舉例來說，2個火爐應該等價于3個冰箱(從數學的角度來說，1個火爐等價于1.5個冰箱,但是要拿出半個冰箱不是件容易的事,交換比率總是那些有實際意義的整數)。

請寫一個程序,對于給出的交換比率表，計算出任意兩件商品的交換比率。

輸入文檔中的第一行為一個整數，表示測試數據的組數。每組數據中均要包含至少一個命令，結尾用一個“$ ” 號來表示輸入文檔的結束。每個命令獨占一行，命令可以是一個斷言或一個疑問。如果是斷言，則以感嘆號開頭，并按如下格式： ! m itema = n itemb

itema 和itemb應是具體的商品名稱，m和n都是不大于100的正整數。這個命令斷言了m個itema等價于n個itemb。如果命令是一個疑問，則以問號開頭，并按如下格式：

? itema = itemb

表示詢問itema和itemb之間的交換比率，itema和itemb是在上文的斷言中曾出現過的具體的商品名稱（itema和itemb不一定要在同一斷言中出現）。對于每個疑問，根據所有的有關的斷言，輸出itema和itemb之間的交換比率。交換比率必須是整數形式而且應該盡可能的小。如果不能找到相應的交換比率，用問號代替整數來表示。請嚴格按照下面例子輸出。注意：

商品名字只能用不多于20個小寫字母來表示。

商品的名字用單數表示（不要用復數形式）。

最多有60種不同的商品。

對于每一對不同的商品，最多只能有一個斷言。

可能有永假的斷言，舉例來說, "2 pig = 1 cow", "2 cow = 1 horse", and "2 horse = 3 pig" 是永假，不成立。若在一組數據中發現有永假的斷言，則不作任何處理，只需輸出一個組號+“：”+“ERROR！”。 斷言中的比率不一定要是最小的，但是輸出的比率一定要是最小的形式。雖然斷言中不能有大于100的數字，但疑問中可以出現比100大的數字。疑問的答案化成最小后輸出。

? 示范輸入

1

! 6 shirt = 15 sock

! 47 underwear = 9 pant

? sock = shirt

? shirt = pant

! 2 sock = 1 underwear

? pant = shirt

$

? 示范輸出 ?

5 sock = 2 shirt

? shirt = ? pant

45 pant = 188 shirt

? ??? ?????????

????????????????????? 題四 ? ????? ??? 象棋中“車”的避開問題

源文件 :rook???????? 輸入文檔 :rook.in????????? 輸出 : 屏幕 ????????????? 150 分

?

? 問題描述

?

在象棋中, ” 車 ” 是一種能夠在水平和垂直方向上移動任意空格數的棋子.在這個問題中,我們將討論在設有阻止 ” 車 ” 前進的 ” 墻 ” 的小棋盤上放置 ” 車 ” 的問題:在任意兩個 ” 車 ” 不能捉到對方的前提下,向棋盤上放入盡量多的 ” 車 ” . 按照要求可知,如果任意兩個 ” 車 ” 都不在同一橫行或同一豎行,或者至少有一面 ” 墻 ” 將它們隔開,則棋盤上 ” 車 ” 的擺置是合法的.

?

下面的圖反映了同一棋盤上放置 ” 車 ” 的5種情況.

?

第一幅圖是一個空的棋盤；

第二和第三幅圖是合法的放置 ” 車 ” 的情況；

第四和第五幅圖是不合法的放置 ” 車 ” 的情況。

?

對于這個棋盤來說,合法地放置 ” 車 ” 的最大數量是5;

?

有多種不同的方法來放置最多的 ” 車 ” , 第二幅圖的方法是其中的一種.

?

?

請寫一個程序:對于給定的一個棋盤,計算出能夠在棋盤上合法地放置 ” 車 ” 的最大數.

?

輸入文檔要包含一個以上的棋盤的描述,最后一行以0來表示輸入文檔的結束。

?

. 每個棋盤的描述的第一行是一個正整數n,表示棋盤的大小;n不超過10；

?

接下來的n行,每一行描述棋盤上的一行,用 ” . ” 來表示一個空格,用大寫字母 ” X ” 來表示一面 ” 墻 ” .

?

輸入文檔中不出現空格.

?

對于每個測試案例,輸出能夠在棋盤上合法地放置 ” 車 ” 的最大數,同時輸出最小能控制棋盤上“車”的數量，這兩個數字獨自占一行.

?

?

? 示范輸入

?

4

.X..

....

XX..

....

2

XX

.X

3

.X.

X.X

.X.

3

...

.XX

.XX

4

....

....

....

....

0

?

?

? 示范輸出 :

?

5?? 3

1?? 1

5?? 5

2?? 1

4?? 4