99模擬 Problem 4：排列組合的應用

Problem 4：排列組合的應用

子題1（11%）：一個菜販有「肉」、「菜」、「蛋」、「果」4 類商品，在菜攤上「分類」排列出售，各項商品可由輸入檔讀入其「每公斤利潤」。有一天，菜販忘了商品在菜攤的排列方式，只知道今天各類商品由左至右出售的「公斤數」，其資料選手也可由輸入檔讀入。在不知道今天商品排列的情況下，請選手將所有的排列方式逐一代入計算，依總利潤之高低順序，由高而低，輸出所有排列方式及其總利潤。

輸入說明：

第1 行有4 組數字，以逗號隔開，分別表示「肉」、「菜」、「蛋」、「果」每公斤的利潤。

第2 行有4 組數字，以逗號隔開，表示今天菜攤由左至右各類商品出售之公斤數。

輸出說明：

依總利潤之高低順序，每1 行輸出1 組排列方式及其總利潤，資料間至少以1 個空白隔開。

若有總利潤相同者，其前後輸出順序不拘。

輸入範例：【檔名：in-4-1.txt】

70, 32, 18, 42

43, 24, 21, 39

輸出範例：【檔名：out-4-1.txt】

肉菜蛋果 5794

肉蛋菜果 5752

果菜蛋肉 5682

肉果蛋菜 5644

果蛋菜肉 5640

肉蛋果菜 5572

菜果蛋肉 5492

菜蛋果肉 5420

肉果菜蛋 5392

肉菜果蛋 5362

蛋果菜肉 5184

蛋菜果肉 5154

果肉蛋菜 5112

菜肉蛋果 5072

果蛋肉菜 4956

菜蛋肉果 4916

果肉菜蛋 4860

蛋肉菜果 4764

果菜肉蛋 4746

蛋菜肉果 4650

菜肉果蛋 4640

蛋肉果菜 4584

菜果肉蛋 4556

蛋果肉菜 4500

戰艦謎題

內容 ：
在一個2x2的格子圖形中，有三艘各佔一個格子的戰艦，戰艦的位置均在格子的範圍內。三艘戰艦重量皆不同，從1噸到3噸各有一艘，因為大霧瀰漫不知正確位置，僅知道每一列與每一行的總重量，請問聰明的你，知道每一艘戰艦的正確位置嗎？
舉例來說，如果我們知道每一列與每一行的總重量如下圖：
囗囗５
囗囗１
４２

那麼這個戰艦謎題的一組正確答案如下圖：
３２５
１０１
４２

注意：我們給的輸入資料不一定只有一組正確答案，這時候你只需輸出其中一組正確答案即可。此外，我們給的輸入資料有可能沒有正確的答案，這時候只需輸出"No solutions."即可。

輸入說明 ：
總共有四個整數，每個數值間以一個空白字元隔開，這些數字個值均介於0到5之間。前2個整數依序表示每一列(row)的總重量，接下來的2個整數依序表示每一行(column)的總重量。
輸出說明 ：
請輸出4個整數，分成兩列，每列含有2個整數，整數中間以一個空白隔開，表示2x2的格子中，停在每個位置的戰艦重量。其中以0表示沒有戰艦。(範例一就是上圖的例子)如果沒有解答請輸出 "No solutions."
範例輸入 ：

輸入範例一： 
5 1 4 2 
輸入範例二： 
3 3 1 5 
輸入範例三： 
3 2 3 4
範例輸出 ：

輸出範例一： 
3 2 1 0 
輸出範例二： 
0 3 1 2 
輸出範例三： 
No solutions.

國際資訊奧林匹亞獎牌計算

參加國際資訊奧林匹亞(IOI)競賽者大約有一半的選手可以獲得獎牌。In_d.txt即為被評為可以獲獎的名單（第１欄為國家代碼，第２欄為選手姓名，第３欄為其成績），在此名單中，金、銀、銅牌的分配約為１：２：３。試寫一程式依得分高任分配獎牌。輸出包括四部分： 
由高至低排序，並將得獎類別寫在分數旁[G(金)、S(銀)、B(銅)]( 如輸出範例1)。 
獎牌分配，即獲得金、銀、銅牌的個數 (如輸出範例2)。 
得獎牌最多的國家，寫出國家代碼及獎牌 (不分類別) 數 (如輸出範例3)。 
所有得獎者分數之平均數、最高分、最低分及全距 (即最高分與最低分的差距)(如輸出範例4)。

輸入範例(in_d.txt)：
RSA Bruce Merry 333
HUN Balazs Racz 250
UKR Oleksandr lotko 230
ROM Bogdan Dumitru 360
VIE Nguyen N. Huy 430
SUI Peter Kaufmann 266
CRO Frane Saric 268
ROM Radu A. Stefan 150
BLR Ivan Miatselski 226
AUS Peter Hawkins 225
SVK Jan Senko 210
BUL Svetlin Nakov 208

輸出範例１
VIE Nguyen N. Huy 430 G
ROM Bogdan Dumitru 360 G
RSA Bruce Merr 333 S
CRO Frane Saric 268 S
SUI Peter Kaufmann 266 S
HUN Balazs Racz 250 S
UKR Oleksandr lotko 230 B
BLR Ivan Miatselski 226 B
AUS Peter Hawkins 225 B
SVK Jan Senko 210 B
BUL Svetlin Nakov 208 B
ROM Radu A. Stefan 150 B

輸出範例２
G 2
S 4
B 6

輸出範例３
ROM 2

輸出範例４
263.00 430.00 150.00 280.00

田鼠與狗

在田野中有一隻田鼠和一隻狗。狗想要吃掉田鼠，而田鼠則要儘速的逃進鼠洞中（田表面有許多鼠洞）。狗和田鼠都不是數學專家，但是也都不笨。當田鼠決定了某一個鼠洞後，就以一定的速度直線的跑去。而狗則非常擅長解讀肢體語言，當他一知道田鼠要往那個洞跑，就以田鼠2 倍的速度直線奔去，想要抓住田鼠。假如狗先到達那個洞，田鼠就會被吃掉，否則，田鼠就可安全逃走。
你必須幫田鼠選一個洞，使他可以逃離狗的魔掌（如果這樣的洞存在的話）。

輸入規範

輸入檔案中包含好幾組測試資料，每組測試資料的第一列有一個整數n 和4 個浮點數x1,y1,x2,y2。n（n £ 1000）代表本組測試資料有多少個鼠洞，4 個浮點數（均介於-10000 及+10000之間）代表田鼠(x1,y1)及狗(x2,y2)的x-y 座標。接下來的n 列，每列有2 個浮點數，代表每個鼠洞的座標。（所有的浮點數都到小數點後3 位測試資料組間有一空白列（請參考輸入範例）

輸出規範

每組測試資料輸出一列。如果田鼠可以逃走，請輸出"田鼠可由(x,y)的鼠洞逃走"。(x,y)是某一個洞的座標。如果田鼠無法逃走，請輸出"田鼠無法逃走"請注意：如果田鼠可以從不只一個洞逃走，請輸出在輸入中最前的洞。

輸入範例(test7.txt)
1 1.000 1.000 2.000 2.000
1.500 1.500
3 2.000 2.000 1.000 1.000
1.500 1.500
2.500 2.500
3.500 3.500
輸出範例(result7.txt)
田鼠無法逃走
田鼠可由(2.500,2.500)的鼠洞逃走

我愛偶數

我愛偶數

內容 ：

文文很喜歡偶數，他甚至有收集偶數的習慣。你給他一個範圍的連續整數，他就會把其中的偶數留下來收藏。如今他又拿到了一個範圍的整數，請問他這次收藏了幾個偶數？對文文來說，0 也算是一個偶數哦！ 

 

輸入說明 ：

輸入只有一行，其中含有兩個由空白隔開的整數 a, b (0 ≤ a ≤ b ≤ 2147483647)。

 

輸出說明 ：

輸出一個整數，代表 a 與 b 之間 (含 a 與 b) 一共有多少個偶數。

 

範例輸入 ：

若題目沒有特別說明，則應該以多測資的方式讀取，若不知如何讀取請參考 a001 的範例程式。

1 4

範例輸出 ：

2

提示 ：

你可以只用算術運算子，而不用 if 指令來完成這題嗎？

任意進位轉任意進位

輸入說明:

輸入可能有無限多行
輸入 a,b,c 。a為原進位，b為目標進位，c為原數 （1 ≦ a ≦ 36)&（1 ≦ b ≦ 36)

輸入範例:
10 2 81
8 3 52
9 5 97
2 6 100
6 8 64
8 9 85
9 15 69
9 16 168
8 32 648
2 36 1000
16 10 4EB

輸出範例:
1010001
1120
323
4
50
76
43
8F
D8
8
1259

門牌號碼

有一個程式設計師住在一條街上，這條街上的房子都在路的同一邊且門牌號碼是從1-2-3-4-....連續下來。有一天晚上他牽著他的狗出門散步，出門之後往左邊走，因為溜狗有點無聊，所以她順便把經過的房子的門牌號碼都加起來。隔天晚上他又出門溜狗，但這一次她往右走並且也把經過的門牌號碼加起來。讓他很驚訝的是：這兩次的數字竟然一樣。
當然，這個巧合現象跟這條街共有幾間房子(n)，以及他住在第幾間房子(k)有關係。請寫出一個程式找出前十個滿足這樣條件的數對(k,n)。在輸出中有前2個這樣的數對。
每一對數字k,n的長度均為10，向右靠齊。請將檔案輸出至"out.txt"。 ※此題無須"in.txt"

輸出範例：
6 8
35 49