?? ?? 題一 ? ?? “自身數(shù)字”問題

?

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

?

? 問題描述

?

1949 年，印度數(shù)學(xué)家D.R.Kaprekar發(fā)現(xiàn)了一類被稱作“自身數(shù)值”的數(shù)字：

?

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

?

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

?

例如：以33為起點(diǎn)，下一個(gè)數(shù)字是33+3+3=39，再下一個(gè)數(shù)字是39+3+9=51，再下一個(gè)數(shù)字是51+5+1=57，以此類推可以產(chǎn)生序列：

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

?

?n 被稱作d（n）的“產(chǎn)生者”。

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

?

有些數(shù)字會(huì)有不止一個(gè)“產(chǎn)生者”：舉例來說，101有兩個(gè)“產(chǎn)生者”，它們是91和100。

?

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

?

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

?

? 示范輸出

?

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

?

?|

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

?|

?

?

?

?

?

?

?

?

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

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

?

? 問題描述

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

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

請(qǐng)寫一個(gè)程序：對(duì)于給定的一組圓點(diǎn)，找出所有可能的長方形。下面將給出關(guān)于上面幾個(gè)圖的輸入和輸出的示例。

?

輸入文檔要包含1個(gè)以上的圓點(diǎn)集合，最后以0結(jié)尾表示輸入文檔結(jié)束。每一個(gè)圓點(diǎn)集合的第一行是正整數(shù)n，表示共有圓點(diǎn)的數(shù)目，其后的n行表示圓點(diǎn)的狀態(tài)。每個(gè)圓點(diǎn)的表示格式是：先用一個(gè)大寫字母來代表一個(gè)圓點(diǎn)，其后空格，然后是該圓點(diǎn)的橫坐標(biāo)，再空格，最后是該圓點(diǎn)的縱坐標(biāo)。每一組圓點(diǎn)集合中，表示圓點(diǎn)的大寫字母應(yīng)按字母表的順序使用。注意，因?yàn)槊總€(gè)點(diǎn)需要用一個(gè)大寫字母表示，所以至多可以有26圓點(diǎn)。所有的坐標(biāo)是小于50的非負(fù)整數(shù)。每組集合的各個(gè)圓點(diǎn)彼此是獨(dú)立的。

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

?

? 示范輸入

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 分

?

? 問題描述

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

請(qǐng)寫一個(gè)程序,對(duì)于給出的交換比率表，計(jì)算出任意兩件商品的交換比率。

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

itema 和itemb應(yīng)是具體的商品名稱，m和n都是不大于100的正整數(shù)。這個(gè)命令斷言了m個(gè)itema等價(jià)于n個(gè)itemb。如果命令是一個(gè)疑問，則以問號(hào)開頭，并按如下格式：

? itema = itemb

表示詢問itema和itemb之間的交換比率，itema和itemb是在上文的斷言中曾出現(xiàn)過的具體的商品名稱（itema和itemb不一定要在同一斷言中出現(xiàn)）。對(duì)于每個(gè)疑問，根據(jù)所有的有關(guān)的斷言，輸出itema和itemb之間的交換比率。交換比率必須是整數(shù)形式而且應(yīng)該盡可能的小。如果不能找到相應(yīng)的交換比率，用問號(hào)代替整數(shù)來表示。請(qǐng)嚴(yán)格按照下面例子輸出。注意：

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

商品的名字用單數(shù)表示（不要用復(fù)數(shù)形式）。

最多有60種不同的商品。

對(duì)于每一對(duì)不同的商品，最多只能有一個(gè)斷言。

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

? 示范輸入

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 分

?

? 問題描述

?

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

?

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

?

第一幅圖是一個(gè)空的棋盤；

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

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

?

對(duì)于這個(gè)棋盤來說,合法地放置 ” 車 ” 的最大數(shù)量是5;

?

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

?

?

請(qǐng)寫一個(gè)程序:對(duì)于給定的一個(gè)棋盤,計(jì)算出能夠在棋盤上合法地放置 ” 車 ” 的最大數(shù).

?

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

?

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

?

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

?

輸入文檔中不出現(xiàn)空格.

?

對(duì)于每個(gè)測(cè)試案例,輸出能夠在棋盤上合法地放置 ” 車 ” 的最大數(shù),同時(shí)輸出最小能控制棋盤上“車”的數(shù)量，這兩個(gè)數(shù)字獨(dú)自占一行.

?

?

? 示范輸入

?

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