顯示具有 2011/10月 標籤的文章。 顯示所有文章
顯示具有 2011/10月 標籤的文章。 顯示所有文章

2011年10月21日 星期五

97正式 Problem7:正多邊形的面積(14%)

Problem7:正多邊形的面積

已知圓的半徑r,和內接正多邊形的邊數n,請計算出正多邊形的面積,而圓週率設為3.14

輸入說明:

每組輸入包含兩個數字rnr ( 0 < r < 10000 ) 代表圓半徑,n ( 2 < n < 10000 )代表內接正多邊形的邊數。

輸出說明:

對於每組測試資料,輸出圓內接正多邊形的面積,請四捨五入到整數位。

輸入範例:

2 2000

10 3000

輸出範例:

13

314

97正式 Problem6:因數

Problem6因數(11%)

已知兩個整數nd,請你找出n這個值,會有多少個因數可以被d整除。

輸入說明:

每組輸入包含兩個以空白隔開的數字nd,其n ( 0 < n < 1000000 ),而d ( 2 ≤ d < 1000 )

輸出說明:

對於每組測試資料,輸出n這個值,會有多少個因數可以被d整除。

輸入範例:

36 2

64 8

輸出範例:

6

4

97正式 Problem5:兩直線間的關係

Problem5:兩直線間的關係(14%)

2維平面中兩條直線間的關係共有三種:

1. 相交於一點

2. 重疊(無限多交點)

3. 平行(沒有交點)

輸入4個點,分別代表兩條直線。請輸出這兩條直線間的關係。

輸入說明:

每組輸入包含8個以空白隔開的數字x1 y1 x2 y2 x3 y3 x4 y4,分別代表4個點 (x1, y1)(x2, y2)(x3, y3)(x4, y4)。其中第一條直線會通過 (x1, y1)(x2, y2);第二條直線會過通 (x3, y3)(x4, y4)。

輸出說明:

請輸出這兩條直線的關係,如果是相交於一點,請輸出I;如果這兩條線是重疊,請輸出L;如果這兩條線是平行,請輸出N

輸入範例:

5 0 7 6 1 0 2 3

5 0 7 6 3 -6 4 -3

2 0 2 27 1 5 18 5

輸出範例:

N

L

I

97正式 Problem3:黑盒子

Problem3黑盒子(12%)

有一個黑盒子支援 Insert, Inquire, Clean, End四種指令:

l Insert x:將x放入黑盒子中。

l Inquire k:輸出黑盒子當中第k大的數字,若找不到該數,則不輸出。

l Clean:更換另一組測試資料,清空黑盒子。

l End:結束程式。

輸入說明:

請參考範例輸入,所有數字都為整數。一組測試資料的指令數不會超過1000個。

輸出說明:

請將每一個合法的Inquire k值輸出。

輸入範例:

Insert 4

Inquire 1

Insert 1

Inquire 2

Insert -3

Insert 3

Insert 7

Insert -99

Inquire 4

Clean

Insert 3

Inquire 2

Inquire 1

END

輸出範例:

4

1

1

3

97正式 Problem4:排列最小值

Problem4:排列最小值(13%)

一串數字內有n個正整數。試著利用連接字串的方式去排列這n個正整數,使其值最小。

輸入說明:

每組輸入包含一串數字,內有n個正整數,數字與數字間以一個空白隔開。

輸出說明:

每組輸出排列後的最小正整數。

輸入範例:

1 36 3647

8 79 797 799

輸出範例:

1363647

797797998

97正式 Problem2:極大值問題

Problem2:極大值問題(11%)

有一個n位數的正整數A,請問刪除其中k個連續或不連續的位數 (k < n)、將剩下的數字依序合併形成一個新的正整數BB的最大可能值是多少?(請注意,AB的首位都不能是0)。

輸入說明:

奇數列有兩個以空白隔開的正整數nk (1 ≤ k < n ≤ 1000000)。偶數列會有一個長度為n的正整數A

輸出說明:

請輸出B的最大可能值。

輸入範例:

6 4

268574

5 2

41235

輸出範例:

87

435

97正式 Problem1:等差數列或等比數列

Problem1:等差數列或等比數列(10%)

在數列中有等差數列及等比數列,若已知數列的前四項,請判斷出此數列是等差或是等比數列,並求出公差或公比。

輸入說明

第一行是數列的數目t0 ≤ t ≤ 10)。以下每行均包含四個以空白隔開的整數,表示數列的前四項。數列的前四項均為不大於10000的自然數,等比數列的比值也是自然數。

輸出說明:

對輸入的每個數列,輸出兩個欄位,欄位與欄位之間以一個空白隔開,若是等差數列則第一欄輸出A,若為等比數列則第一欄輸出G;第二欄則根據數列的判斷結果,輸出其公差或是公比。

輸入範例:

2

2 4 6 8

2 4 8 16

輸出範例:

A 2

G 2

2011年10月18日 星期二

96正式 Problem 7 (密碼解密

Problem 7 (密碼解密 8%)

在密碼學裡面有一種很簡單的加密方式,就是把原始資料的每個字元通通加上某一個整數K而得到密碼的字元(原始資料及密碼字元一定都在ASCII碼中可列印的範圍內)。例如若K=2,那麼apple經過加密後就變成crrng了;解密則是反過來做。
輸入說明:第一列為加密的K值,第二列為要解密的列數,第三列及以後就是需要解密的字串。(請參照輸入範例)
輸入範例:test7.txt
7
3
1JKJ'pz'{ol'{yhklthyr'vm'{ol'Jvu{yvs'Kh{h'Jvywvyh{pvu5
1PIT'pz'h'{yhklthyr'vm'{ol'Pu{lyuh{pvuhs'I|zpulzz'Thjopul'Jvywvyh{pvu5
1KLJ'pz'{ol'{yhklthyr'vm'{ol'Kpnp{hs'Lx|pwtlu{'Jvywvyh{pvu5
輸出說明:對每一測試資料,請輸出解密後的原始資料。(請參照輸出範例)
輸出範例:result7.txt
*CDC is the trademark of the Control Data Corporation.
*IBM is a trademark of the International Business Machine Corporation.
*DEC is the trademark of the Digital Equipment Corporation.




今天早上把96正式歷屆作完囉 :)

96正式 Problem 6 (關係運算子

Problem 6 (關係運算子 7%)

請設計一個程式,能判斷出兩個數值之間三種狀態的關係運算子:
(1)第一個數字大於第二個數字。
(2)第二個數字小於第一個數字。
(3)兩個數字一樣大。
第 4 頁/共 5 頁
輸入說明:每一列由二個數字所組成,為一組測試資料。每個數字與數字間的區隔為一個空白符號,當為0 0時表示結束。(請參照輸入範例)
輸入範例:test6.txt
10 20
20 10
10 10
0 0
輸出說明:對於每組測試資料,輸出『>』、『<』、『=』,代表該二數字的關係。(請參照輸出範例)
輸出範例:result6.txt



96正式 Problem 5 (尋找第K大的位置

Problem 5 (尋找第K大的位置 12%)

請設計一個程式,能在一個數列中,找出此數列第K大數字的位置。例如,有一個數列為8,20,27,17,13,28,35,31,第三大的數字為28,此數字的位置在串列中的第6個位置;第5大的數字為20,此數字的位置在串列中的第2個位置。
輸入說明:輸入之第一列為下一列數列中的個數。第二列為數列資料。每個數字與數字間的區隔為一個空白符號。第三列及以後的資料為要尋找第K大數字的K值,當為0時表示結束。(請參照輸入範例)
輸入範圍:輸入的數列最少為2個,最多不超過100個。每個數列中的數字皆大於0,小於1000,且不重覆。
輸入範例:test5.txt
8
8 20 27 17 13 28 35 31
3
5
10
0
輸出說明:輸入的每個K值皆有一個位置的輸出結果,若超過數列的個數則輸出-1。(請參照輸出範例)
輸出範例:result5.txt
6
2
-1

96正式 Problem 4 (借盤子

Problem 4 (借盤子 13%)

張三把所持有的1000個盤子分別裝在10個箱子裡,每個箱子分別裝進1、2、4、8、16、32、64、128、256、及489個盤子。張三將這些箱子依序標上1~10的號碼。有天,李四想找張三借N個盤子,張三知道每個箱子的編號與箱子內所放盤子的個數,但如何設計一個程式,在不拆開箱子重新組合盤子的情況下,告訴張三應拿出那些箱子給李四,才能得到李四要借的盤子數目呢?
輸入說明:每列中的數字代表要借的盤子數,當為0時表示結束。(請參照輸入範例)
輸入範圍:每列中的數字皆大於0,小於等於1000。
輸入範例:test4.txt
717
329
0
第 3 頁/共 5 頁
輸出說明:每個數字代表箱子的編號,每個數字與數字間的區隔為一個空白符號,請由大到小排列。(請參照輸出範例)
輸出範例:result4.txt
10 8 7 6 3
9 7 4 1

96正式 Problem 3 (數獨

Problem 3 (數獨 23%)

「數獨sudoku」來自日文,但概念源自「拉丁方塊」,是十八世紀瑞士數學家歐拉發明的。其遊戲規則為: 在九個九宮格裡,填入1到9的數字,讓每個數字在每個行、列及九宮格裡都只出現一次。謎題中會預先填入若干數字,其他宮位則留白,玩家得依謎題中的數字分佈狀況,邏輯推敲出剩下的空格裡是什麼數字,範例如下圖所示。請設計一個程式,可以幫助玩家提示空格中尚可填入的數字。例如:第5行第3列的位置尚可填入1這個數字;第6行第7列的位置尚可填入7與8這兩個數字;而第5行第5列的位置已有數字填入則輸出0。

輸入說明:輸入的第一列到第九列為數獨資料,每一列由九個數字所組成。數字1到9為已填入的數值,0代表尚未填入數值的空格,每個數字與數字間的區隔為一個空白符號。第十列及以後的資料為要提示位置的座標(座標的定義方式為右上角為9 1,左下角為1 9,第一個數字代表行,第二個數字代表列),當為0 0時表示結束。(請參照輸入範例)

輸入範例:test3.txt
4 0 0 8 0 5 0 1 0
2 0 0 0 0 9 0 8 0
6 0 8 0 0 3 4 9 0
0 0 5 0 2 0 6 0 0
0 0 1 0 7 0 9 0 0
0 0 7 0 8 0 3 0 0
0 9 0 1 0 0 0 0 2
0 8 0 4 0 0 0 0 9
0 3 0 6 0 2 0 0 7
5 3
6 7
5 5
0 0

輸出說明:每個提示位置有一列輸出結果,表示尚可填入的數字,請由小到大排列。每個數字與數字間的區隔為一個空白符號。若該位置已有填入數字,或找不到提示的數字則輸出0。(請參照輸出範例)
輸出範例:result3.txt
1
7 8
0

96正式 Problem 2 (總和檢查

Problem 2 (總和檢查 16%)

請檢查一個數列中,尋找任兩個數字相加後的和是否會等於輸入的檢查值。例如,有一個數列為8,20,27,17,13,28,35,31,若輸入的檢查值為48,會找到20及28兩個數,相加的和為48;反之若輸入的檢查值為50,則會找不到配對的數字。
輸入說明:輸入之第一列為下一列數列中的個數,第二為列為數列資料。每個數字與數字間的區隔為一個空白符號。第三列及以後的資料為輸入的檢查值,每一列有一個檢查值,當為0時表示結束。(請參照輸入範例)
第 1 頁/共 5 頁
輸入範圍:輸入的數列最少有2個數字,最多不超過100個。每個數列中的數字皆大於0,小於1000,且不重覆。
輸入範例:test2.txt
8
8 20 27 17 13 28 35 31
48
50
0
輸出說明:每個檢查值有一個輸出結果,若有匹配的檢查值,則輸出為1,反之為-1。(請參照輸出範例)
輸出範例:result2.txt
1
-1

96正式 Problem 1 (最長遞增子序列

Problem 1 (最長遞增子序列 21%)

考慮一個數列在刪除最少個數的情況下,使得剩下的數字呈現遞增狀態。例如,有一個數列為8,20,27,17,13,28,35,31,若保留前三個數字,其餘的全部刪除,剩下的就是一個遞增序列;或者是保留第一、第三、第六及第七,其餘的全部刪除,剩下的也是一個遞增序列,但是與前一個例子相比,其遞增的序列較長。
輸入說明:輸入之奇數列為下一行數列中的個數,偶數列為數列資料,代表一組測試資料。每個數字與數字間的區隔為一個空白符號,當奇數列為0時表示結束。(請參照輸入範例)
輸入範圍:每個數列最少有2個數字,最多不超過100個。每個數列中的數字皆大於0,小於1000,且不重覆。

輸入範例:test1.txt
8
8 20 27 17 13 28 35 31
15
13 14 55 21 66 72 23 73 1 2 88 83 84 24 7
0
輸出說明:每組測試的數列皆要輸出欲刪除的個數。(請參照輸出範例)

輸出範例:result1.txt
3
7

2011年10月17日 星期一

二分搜尋法

請以二分搜尋法的方式,求2的平方根及3的三次方根。
說明:1,本題限制不能使用內定的函數來求解。(就是不能用sqrt(x)函數)
2,提示,在1和2之間,以二分搜尋法找x,然後比較x*x 和 2的大小關係。(另一個,當然就是x*x*x和3的大小關係啦。)

96模擬 Problem 5 (最小距離

Problem 5 (最小距離 14%)

請設計一個程式,能在一個數列中,找出相鄰兩數的最小距離。例如,有一個數列為8,20,27,17,13,28,35,31,8與20的距離為12;20與27的距離為7,與前一個例子相比,其距離較小。

輸入說明:輸入之奇數列為下一行數列中的個數,偶數列為數列資料,代表一組測試資料。每個數字與數字間的區隔為一個空白符號,當奇數列為0時表示結束。(請參照輸入範例)
輸入範圍:每個數列最少有2個數字,最多不超過100個。每個數列中的數字皆大於0,小於1000,且不重覆。
輸入範例:test5.txt
8
8 20 27 17 13 28 35 31
15
13 14 55 21 66 72 23 73 1 2 88 83 84 24 7
0

輸出說明:每組測試的數列皆要輸出最小距離。(請參照輸出範例)
輸出範例:result5.txt
4
1

96模擬 Problem 4 (數學遊戲

Problem 4 (數學遊戲 18%)

在英國有一個數學遊戲,給參賽者一些正整數和一個目標數,參賽者必須在這些正整數間插入+、-、*或 / 的符號,使得最後計算的結果等於目標數。計算的方式是由左到右,而且不必管運算的優先順序(就是不管先乘除後加減那一套)。
在這個數學運算式中,有三個限制:
1. 正整數出現的次序不可改變,也就是說要與輸入的順序相同。
2. 因為目標數也是一個正整數,所以在運算的過程中,你只有在可以整除的情況下,才可以使用除法。
在運算的過程中,如果你用某一個運算符號,會導致產生的數超出-32000 ~ +32000的範圍,那麼你不可以採用此運算符號(也就是說,在運算的過程中都不允許有超出範圍的數出現)。

輸入說明:輸入檔案的第一列是1個整數n,代表接下來有多少組測試資料。每組測試資料一列。每列的第一個整數 p(0 < p 100),代表要做運算的數有多少個。接下來有p個正整數,每列的最後一個數(即p+1個)為目標數。所有的數都小於32000,而每個數字間以一個空格分開。(請參照輸入範例)
輸入範例:test4.txt
3
3 5 7 4 3
2 1 1 2000
5 12 2 5 1 2 4

輸出說明:每列測試資料輸出一列運算式,使得輸入的p個正整數運算的結果等於目標數。如果找不到這樣的運算式,請輸出『無解』。如果有多組運算式可以達成任務,請輸出任何一組均可。(請參照輸出範例)
輸出範例:result4.txt
5+7/4=3
無解
12-2/5*1*2=4

2011年10月12日 星期三

96模擬 Problem 2 (字串處理

Problem 2 (字串處理 10%)
輸入一段字串(String),請寫出一個程式,計算此字串中阿拉伯數的字元有幾個?

輸入說明:第一列為要計算的列數,第二列及以後就是需要計算的字串。(請參照輸入範例)
輸入範例:test2.txt
2
a9sj2k13ckdi7
ba429gcbgq1

輸出說明:對每一測試資料,輸出字串中阿拉伯數字的個數。(請參照輸出範例)
輸出範例:result2.txt
5
4