INPUT
輸入資料的第一列為一整數T(T <= 1000)表示測試資料的組數，接下來每列有兩個六位數字的整數，每一個位數依序表示骰子上、下、前、左、後、右面的點數。OUTPUT
若該組骰子一樣請輸出"Equal"，否則請輸出"Not Equal"。SAMPLE INPUT
3 345678 345678 123123 123456 123456 351624
SAMPLE OUTPUT
Equal Not Equal Equal
原文出處
2011年9月29日 星期四
11959 - Dice
給定兩顆骰子六個面的點數資料，請你判斷這兩顆骰子是否一樣。骰子每一面的點數可能為1~9。
原文出處
原文出處
11961 - DNA
DNA有四種鹼基：A, C, G, T。給定長度為N的DNA序列，我們說此DNA的「第K突變(K-th mutation)」表示此DNA可藉由原始DNA改變K個元素來得到，例如GAT為GGT的第一突變，為TTT的第二突變。
給定一原始的DNA序列，及最大的突變數K，請你列出所有可能的組合(包含第0~K突變)。
原文出處
給定一原始的DNA序列，及最大的突變數K，請你列出所有可能的組合(包含第0~K突變)。
INPUT
輸入的第一列有一整數T(T <= 50)表示測試資料的組數，每組資料兩列，第一列有兩個整數N(N <= 10)，K(K <= 5)，第二列為長度N的原始DNA序列。OUTPUT
請每組測試資料輸出所有組合的總數，並以字典順序由小到大輸出所有組合。SAMPLE INPUT
1 3 1 AAA
SAMPLE OUTPUT
10 AAA AAC AAG AAT ACA AGA ATA CAA GAA TAA
原文出處
11979 - Hamming Base
給定N個以N進制表示的整數，每個整數有M個位數(包含前導的零)，我們定義兩個整數為「K階相似(K-similar)」表示他們剛好有K個位數值是一樣的，例如321與213為零階相似，3456與6453與二階相似，123與453與一階相似。你的目標是一步步改變這N個整數，使得任兩個整數為零階相似，每一步限定為只能改變某個整數的某個位數，使其加一或減一，當該位數值為0則無法作減一的動作，若為N-1則無法做加一的動作。
請你用最少的步驟來達成這項目標。
Input
輸入的一開始會給定整數T(<= 50)表示測試資料的組數。每組資料的第一列有兩個整數N(2 <= N <= 2000)與M(1 <= M <= 10)，接下來的N列每列有M個其值介於 0 ~ N-1 的整數，每列的M個整數組成有M個位數，且以N進制表示的整數。
Output
請每組測試資料輸出資料編號與達成這項目標的最少步驟數。
Sample Input | Output for Sample Input |
2 3 3 0 0 0 0 0 0 0 0 0 4 2 0 0 0 0 0 2 2 0 | Case 1: 9 Case 2: 8 |
11986 - Save from Radiation
有一瓶被輻射污染的水被放置在N瓶乾淨的水中，所有水瓶的外觀皆相同，已經無法分辨哪一瓶是被污染的水了，若真的不小心喝了那瓶被污染的水就會在五分鐘內死亡，現在我想用白老鼠來做檢驗，請問我最少需要多少隻白老鼠？
只要給白老鼠餵食一滴水就可以分辨該瓶水是否被污染，你也可以給同一隻白老鼠許多不同瓶的水，只要其中一瓶有毒該隻老鼠就會死掉。
Input
輸入一開始會有一個整數T(<= 3000)表示測試資料的組數。每組資料一列會有一個整數N(0 <= N <= 10^16)。
Output
請每組測試資料輸出資料編號與最少所需的老鼠總數。
Sample Input | Output for Sample Input |
112 | Case 1: 1 Case 2: 2 |
11987 - Almost Union-Find
你也許知道Union-Find這種資料結構，本題請你實作類似的資料結構。本資料結構有三種操作方式：
1 p q：將包含 p 的集合與包含 q 的集合作聯集，若 p 與 q 在同一集合中則忽略此項操作。
2 p q：將 p 移到包含 q 的集合中，若 p 與 q 在同一集合中則忽略此項操作。
3 p：回傳 p 所在集合的元素個數，以及該集合所有元素的總和。
一開始共有 n 個集合：{1}, {2}, {3}, ..., {n}.
執行指令 1 1 2 之後: {1,2}, {3}, {4}, {5}
執行指令 2 3 4 之後: {1,2}, {3,4}, {5} (我們允許產生空集合的操作，例如將3從{3}中移除)
執行指令 1 3 5 之後: {1,2}, {3,4,5}
執行指令 2 4 1 之後: {1,2,4}, {3,5}
原文出處
1 p q：將包含 p 的集合與包含 q 的集合作聯集，若 p 與 q 在同一集合中則忽略此項操作。
2 p q：將 p 移到包含 q 的集合中，若 p 與 q 在同一集合中則忽略此項操作。
3 p：回傳 p 所在集合的元素個數，以及該集合所有元素的總和。
一開始共有 n 個集合：{1}, {2}, {3}, ..., {n}.
Input
輸入有多組測試資料，每組資料一開始給定兩個整數 n, m (1 <= n, m <= 100,000)，n 表示一開始的集合數，m 表示操作的指令數，接下來的 m 列每列一道指令，指令滿足 1 <= p, q <= n。輸入資料大小最多5MB，並以EOF表示結束。Output
當遇到第三種操作指令的時候，輸出兩個整數分別表示元素個數與元素總和。Sample Input
5 7 1 1 2 2 3 4 1 3 5 3 4 2 4 1 3 4 3 3
Output for the Sample Input
3 12 3 7 2 8
Explanation
一開始: {1}, {2}, {3}, {4}, {5}執行指令 1 1 2 之後: {1,2}, {3}, {4}, {5}
執行指令 2 3 4 之後: {1,2}, {3,4}, {5} (我們允許產生空集合的操作，例如將3從{3}中移除)
執行指令 1 3 5 之後: {1,2}, {3,4,5}
執行指令 2 4 1 之後: {1,2,4}, {3,5}
原文出處
11988 - Broken Keyboard (a.k.a. Beiju Text)
你用了一個有點壞掉的鍵盤打字，該鍵盤會自動按下”Home”鍵與"End"鍵，直到打完整個內容以前，你都沒有發現到這個問題。本題給定鍵盤輸出的字串(包含Home與End)，請你輸出該字串在螢幕顯示的內容。
原文出處
Input
輸入有多組測試資料，每組一列，其長度介於1 ~ 100,000之間，包含小寫的字母及兩個符號 '[' 與 ']'，'['表示Home鍵(被鍵盤自動按下)，']'表示End鍵。輸入資料以EOF表示結束，其資料長度不超過5MB。Output
請你輸出該字串在螢幕上顯示的內容。Sample Input
This_is_a_[Beiju]_text [[]][][]Happy_Birthday_to_Tsinghua_University
Output for the Sample Input
BeijuThis_is_a__text Happy_Birthday_to_Tsinghua_University
原文出處
11957 - Checkers
給定一個 n x n 大小的棋盤，棋盤上有一個白子與許多黑子，請你計算白子移動到最上方一列的所有可能路徑總數，只有白子可以移動，黑子永遠停留在原處，白子移動的規則如下：
原文出處
- 移動到的目標位置必須是空的。
- 位於(x, y)的白子只能向前移動對角的一格，即移動到(x+1, y+1), 或(x-1, y+1)。
- 若在位置(x+1, y+1), (x-1, y+1)上有棋子存在，請跨過移動到(x+2, y+2), 或(x-2, y+2)的位置。
INPUT
輸入資料的第一列有一整數T(T <= 100)表示測試資料的組數。每組資料的一開始給定一整數N(1 <= N <= 100)表示棋盤的大小，接下來的N列每列有N個字元表示棋盤的佈局，其中W表示白子，B表示黑子，. 表示空的位置。每組資料只會有一個白子。OUTPUT
請每輸測試資料輸出格式："Case T: S"，其中T表示測試資料編號(由1開始)，S表示白子移動到最上方一列的可能路徑總數，由於其值可能極大，請你取除以1000007的餘數。SAMPLE INPUT
2 4 .... .... .... ..W. 8 .B.B.B.. ........ ........ ..B..... ........ ..B..... .W...... ........
SAMPLE OUTPUT
Case 1: 5 Case 2: 1
原文出處
11956 - Brainfuck
你的朋友Bob最近買了一組可用「Brainfuck」程式語言控制的LED顯示器，但是直接在該LED顯示器開發、執行程式並不是很有效率，為了測試與除錯上的需要，他決定在PC上開發該顯示器指令集的轉譯器，但是他只會寫brainfuck程式語言，所以需要你來幫他完成這項工作。
顯示器的程式是一道道循序執行的指令，僅包含五個brainfuck指令：'>', '<', '+', '-', '.'，請見下表說明。該顯示器的記憶體大小為100位元(byte)，記憶體內容皆被初始化為0，並有一個指標暫存器(一開始指向最左邊的位元)，當指標暫存器指向最右邊的位元時，在加1後變為指向最左邊的位元，反正亦然。每一個位元值則是在0到255之間作循環。
原文出處
顯示器的程式是一道道循序執行的指令，僅包含五個brainfuck指令：'>', '<', '+', '-', '.'，請見下表說明。該顯示器的記憶體大小為100位元(byte)，記憶體內容皆被初始化為0，並有一個指標暫存器(一開始指向最左邊的位元)，當指標暫存器指向最右邊的位元時，在加1後變為指向最左邊的位元，反正亦然。每一個位元值則是在0到255之間作循環。
| 指令 | 說明 |
| > | 指標暫存器加1(指向右邊下一個位元)。 |
| < | 指標暫存器減1(指向左邊上一個位元)。 |
| + | 指標指向的位元值加1。 |
| – | 指標指向的位元值減1。 |
| . | 輸出指標所指到的位元值。 |
INPUT
輸入的第一列有一整數T(T <= 100)表示測試資料的組數，接下來有T組測試資料，每組一列表示程式碼，每列長度不會超過100000個字元。OUTPUT
每組測試資料輸出格式為"Case T: D"，T表示測試資料編號，D表示該顯示器在執行完程式後的記憶體傾印資料(以16進制表示)，每個位元須以空白字元隔開，請參考範例資料。請注意輸入與輸出的範例資料為了方便閱讀已被分為許多列，實際資料並非如此。SAMPLE INPUT
1 ..++<><<+++>>++++++++++++++++++++++++++>>>+++ <+...++<><<+++>>++++++++++++++++++++++++++>>> +++<+...++<><<+++>>++++++++++++++++++++++++++ >>>+++<+.
SAMPLE OUTPUT
Case 1: 1F 00 20 03 1D 03 01 03 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 03 00
原文出處
11955 - Binomial Theorem
本題請你將 (a+b)^k 乘開，寫出等式：
(a+b)k = x1ak + x2ak−1b + x3ak−2b2 + … + xk+1bk
其中 x1 … xk+1 為二項式係數，即 xi = Cki .
原文出處
(a+b)k = x1ak + x2ak−1b + x3ak−2b2 + … + xk+1bk
其中 x1 … xk+1 為二項式係數，即 xi = Cki .
INPUT
輸入資料的第一列為一整數T(T <= 100)表示測試資料的組數。每組資料一列，其格式為(a+b)^k，其中 a 與 b 為變數名稱，變數名稱以'a' ~ 'z'的小寫字母所組成，且 k (1 <= k <= 50)為其次方。每列的長度不會起過100個字元。OUTPUT
請每組資料輸出格式"Case N: T"，其中N表示測試資料編號(由1開始)，T表示乘開的式子。你不應該輸出係數或指數上多餘的1。SAMPLE INPUT
3 (a+b)^1 (alpha+omega)^2 (acm+icpc)^3
SAMPLE OUTPUT
Case 1: a+b Case 2: alpha^2+2*alpha*omega+omega^2 Case 3: acm^3+3*acm^2*icpc+3*acm*icpc^2+icpc^3
原文出處
11945 - Financial Management
請你寫程式幫Michael計算他一年12個月的銀行帳戶平均餘額。
Input
輸入的第一列有一整數N(1 <= N <= 100)，表示測試資料的組數。每組資料有12列數值，分別表示12個月的帳戶餘額，每個數值皆為正值，且精確到小數點後二位，不會有$符號。
Output
請對每組測試資料輸出資料編號、一個空白字元、一個$符號，及一個數值表示12個月的平均餘額，請四捨五入到小數點後兩位。請注意會計上每仟位分隔符號的使用。
原文出處
Input
輸入的第一列有一整數N(1 <= N <= 100)，表示測試資料的組數。每組資料有12列數值，分別表示12個月的帳戶餘額，每個數值皆為正值，且精確到小數點後二位，不會有$符號。Output
請對每組測試資料輸出資料編號、一個空白字元、一個$符號，及一個數值表示12個月的平均餘額，請四捨五入到小數點後兩位。請注意會計上每仟位分隔符號的使用。Sample Input
1 100.00 489.12 12454.12 1234.10 823.05 109.20 5.27 1542.25 839.18 83.99 1295.01 1.75
Sample Output
1 $1,581.42
原文出處
11935 - Through the Desert
想像你正要開著吉普車橫越沙漠，沙漠中有許多危險正等著你，你必須與你的吉普車相依為命，雖然你的吉普車可以放置很大的油箱，但是你不知道到底需要多大，你需要計算能成功橫越沙漠所需的最小油箱容量。
Fuel consumption n
表示吉普車每行進100公里耗的油量(公升)為 n (1 <= n <= 30)，旅途中的耗油率隨時都可能改變，例如上坡或下坡。
Leak
漏油，你的油箱被尖銳物品劃到而開始緩緩漏油，每道傷痕都會產生每公里一公升的漏油，愈多漏洞漏油的速度愈快。
Gas station
加油站，能幫你把油加滿。
Mechanic
維修站，會幫你把油箱所有漏洞都補起來。
Goal
目的地，終於抵達目的地了，呼~~
Input
輸入會有多組測試資料，每組資料最多有50個事件，每個事件以一個整數(表示與起點的距離)與事件的類別(如上面說明)來表示。每組測試資料的第一個事件一定是"0 Fuel consumption n"，最後一個事件一定是"d Goal"，d表示與起點的距離。
所有事件會以與起點的距離由小到大排序，相同距離可能會發生多起事件，請以出現的順序依序處理。
當出現"0 Fuel consumption 0"表示測試資料結束，此筆資料不做輸出。
Output
請針對每組測試資料輸出保證能順利到達終點所需的最小油箱容量(體積)。請以公升為單位輸出到小數點後三位。Sample Input
0 Fuel consumption 10 100 Goal 0 Fuel consumption 5 100 Fuel consumption 30 200 Goal 0 Fuel consumption 20 10 Leak 25 Leak 25 Fuel consumption 30 50 Gas station 70 Mechanic 100 Leak 120 Goal 0 Fuel consumption 0
Sample Output
10.000 35.000 81.000
原文出處
11908 - Skyscraper
有一棟超高大樓的管理委員會打算在他們大樓的外牆設置廣告，他們找來的客戶要求把特定大小的廣告放置在特定的高度，且願意付出不同的價格。每個廣告主要求放置廣告在特定的高度(由廣告版面所在最低的樓層開始算起)、特定大小(廣告版面所佔據的樓層數)，且必須完整地佔據整層大樓的外牆，不會有多個廣告在同一層的情況。每個廣告都有其價格，當然，廣告不能被分割、不能被放置在非指定樓層，否則拿不到廣告收益。
問題是有許多廣告可能會涵蓋相同樓層而產生衝突，這時候就必須做取捨，本題請你在符合廣告配置規定的情況下，選出最佳的配置方式以達到收益最大化。
Input
輸入的第一列有一個整數T(<= 50)表示測試資料的組數。
每組測試資料一開始會給定整數N(1 <= N <= 30000)表示廣告的數量，接下來會有N列分別為各個廣告的資訊，每則廣告以三個整數表示，A(0 <= A <= 10^5)，B(1 <= B <= 10^5)，C(1 <= C <= 1000)，分別表示最低所在樓層、佔據的樓層數與廣告收益。
Output
請輸出每組測試資料的最大廣告收益。
Sample Input | Output for Sample Input |
1 3 1 5 1 2 10 3 7 12 1 | Case 1: 3 |
11902 - Dominator
在圖論中，我們說節點X「支配(dominate)」節點Y，表示由某特定節點(起點)出發，到達節點Y的所有路徑必定會經過節點X，若由起點出發並不存在任何路徑到達節點Y，則節點Y並不被任何節點所支配。並且我們定義可從起點到達的所有節點被自身所支配。本題給定一有向圖，請你找出所有節點的支配節點， 並且我們定義第零節點為起點。例如右圖中的節點3即為節點4的支配節點，因為從節點0到節點4的所有路徑必通過節點3，而節點1並非節點3的支配節點，因為路徑 0 2 3 並不通過節點1。
Input
輸入資料的第一列為整數T(<= 100)表示測試資料的組數。
每組資料的第一個整數N(0 < N < 100)表示圖中節點的總數，接下來的N列，每列有N個整數，若第 i 列中的第 j 個(由0開始)整數為1，表示由節點 i 到節點 j 有一有向的邊，若為0則否。
Output
請每組測試資料輸出其資料編號，並在接下來的2N+1列中輸出任兩節點的支配關係，若節點A支配節點B請在(A, B)的位置上輸出"Y"，否則請輸出"N"，(A, B)的位置表示第A列的第B欄，其格式請參考範例資料。
Sample Input | Output for Sample Input |
2 5 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 | Case 1: +---------+ |Y|Y|Y|Y|Y| +---------+ |N|Y|N|N|N| +---------+ |N|N|Y|N|N| +---------+ |N|N|N|Y|Y| +---------+ |N|N|N|N|Y| +---------+ Case 2: +-+ |Y| +-+ |
2011年9月24日 星期六
11995 - I Can Guess the Data Structure!
對於某些資料結構，我們提供兩種操作方式：
(1 x)：表示將元素值 x 丟進資料結構中。
(2 y)：表示將元素值 y 從資料結構中取出。
給定一連串的操作步驟，請你猜測該資料結構為何，可能為 1. 堆疊(stack，後進先出)，2. 佇列(queue，先進先出)，3. 優先佇列(priority-queue，總是先取最大的數值)。或是其他未知的資料結構。
stack：表示該結構為stack。
queue：表示該結構為queue。
priority queue：表示該結構為priority queue。
impossible：非以上三種。
not sure：超過一種可能的答案。
原文出處
(1 x)：表示將元素值 x 丟進資料結構中。
(2 y)：表示將元素值 y 從資料結構中取出。
給定一連串的操作步驟，請你猜測該資料結構為何，可能為 1. 堆疊(stack，後進先出)，2. 佇列(queue，先進先出)，3. 優先佇列(priority-queue，總是先取最大的數值)。或是其他未知的資料結構。
Input
輸入有多組測試資料，每組資料的第一列有一個整數 n (1 <= n <= 1000)表示接來下有 n 組操作步驟，每個步驟一列，步驟的格式請參考上面的說明，元素值不會超過100。Output
請對每組測試資料輸出其資料結構為何，其可能的答案如下：stack：表示該結構為stack。
queue：表示該結構為queue。
priority queue：表示該結構為priority queue。
impossible：非以上三種。
not sure：超過一種可能的答案。
Sample Input
6 1 1 1 2 1 3 2 1 2 2 2 3 6 1 1 1 2 1 3 2 3 2 2 2 1 2 1 1 2 2 4 1 2 1 1 2 1 2 2 7 1 2 1 5 1 1 1 3 2 5 1 4 2 4
Output for the Sample Input
queue not sure impossible stack priority queue
原文出處
11977 - Story of Tomisu Ghost
n! (n階乘) 以 b 進制的數字系統表示時，最後面最少有 t 個零。本題給定 n 與 t，請你計算 b 最大可能的值為何。
Input
輸入資料的第一列有一個整數T( <= 4000)，表示測試資料的組數。每組資料有兩個整數 n (1 < n <= 100000)，t (0 < t <= 1000)，n與t皆以十進制表示(base 10)。
Output
請針對每組測試資料輸出資料編號與最大可能的 b 值，由於 b 可能非常大，故請取 b 除10000019的餘數。若無法找到任一個 b 值，請輸出 -1。
Sample Input | Output for Sample Input |
4 1000 1000 1000 2 10 8 4 2 | Case 1: -1 Case 2: 5227616 Case 3: 2 Case 4: 2 |
11968 - In The Airport
Bob在機場等待前往立陶宛的班機，時間很晚，他已經很累了，他走到餐廳想吃塊蛋糕喝杯飲料，服務生給了他菜單，但他已經累得無法思考，所以他請服務生幫他選擇價格上「最接近菜單上所有商品平均價格」的蛋糕與飲料，若有多種選擇，請幫他選較便宜的那一個。請你幫服務生寫一個程式做選擇。
原文出處
INPUT
輸入的第一列有一個整數T( <= 100)表示測試資料的組數，每組資料兩列，第一列有三個整數N(2 <= N <= 1000), M(1 <= M <= N), K(1 <= K <= N)，N表示菜單上所有商品的數量，M表示蛋糕的數量，K表示飲料的數量。第二列有N個整數分別表示所有商品的價格，其中前M個為蛋糕價格，之後的K個為 飲料的價格，最後則為其他商品的價格。OUTPUT
請對每組測試資料輸出格式為"Case #T: A B"，其中T表示資料編號，A表示最接近所有商品平均價格的蛋糕價格，B表示最接近所有商品平均價格的飲料價格。SAMPLE INPUT
2 4 1 1 1 2 3 4 5 1 2 500000000 5 6 1000000000 1000000000
SAMPLE OUTPUT
Case #1: 1 2 Case #2: 500000000 6
原文出處
11953 - Battleships
「戰艦遊戲」為Clifford Von Wickler於二十世紀初發明的紙上遊戲，遊戲中兩位玩家分別有一張N x N的方格，方格上會標示我方戰艦的所在位置與被敵方炮擊的位置，戰艦的大小為 1 x 1 到 1 x N/2，可垂直或水平放置。當戰艦的每一位置都被炮擊則該戰艦就沈沒了，否則該戰艦還"存活"。我方可能會有多艘大小不一的戰艦，不會有任兩艘戰艦重疊或相互接觸。
本題給你方格的資訊，請你計算還有幾艘戰艦存活在戰場上。
原文出處
本題給你方格的資訊，請你計算還有幾艘戰艦存活在戰場上。
INPUT
輸入資料的第一列有一個整數T(T <= 100)表示測試資料的組數，每組資料有一個正整數N(N <= 100)表示方格的大小，接下來有N列每列有N個字元，表示戰場的資訊，"."表示空格，"x"表示戰艦的一部分，"@"表示戰艦被炮擊的部位。OUTPUT
請每組資料輸出格式"Case T: N"，T表示測試資料編號(由1開始)，N表示還存活在戰場上的戰艦數目。SAMPLE INPUT
2 4 x... ..x. @.@. .... 2 .. x.
SAMPLE OUTPUT
Case 1: 2 Case 2: 1
原文出處
11952 - Arithmetic
愛莉絲的計算能力很差，她甚至於不會做加法運算，為了避免尷尬，她準備了一套說詞，例如上次有人指出她計算錯誤：5 + 4 = 10，愛莉絲就說：這是九進位就沒錯了！
本題請你判斷一個等式是否成立。等式成立是指：可以找到B進制來表示該等式，使得等號兩邊相等，且B>=1。(1進制僅會以'1'字元來表示，例如2+3=5的1進制表示為11+111=11111)。
原文出處
本題請你判斷一個等式是否成立。等式成立是指：可以找到B進制來表示該等式，使得等號兩邊相等，且B>=1。(1進制僅會以'1'字元來表示，例如2+3=5的1進制表示為11+111=11111)。
INPUT
輸入資料的第一列為整數T( <= 100)表示測試資料的組數，接下來有T列等式，其格式為 A + B = C，其中A, B, C(0 <= A + B, C <= 10^5)為以十進制表示的非負正數。OUTPUT
請對每組測試資料輸出最小的B值使得等式成立，若不存在則輸出"0"。SAMPLE INPUT
4 155 + 102 = 301 1022 + 221 = 1303 6502 + 6800 = 11202 515 + 7 = 522
SAMPLE OUTPUT
6 4 0 10
原文出處
11949 - Calculating IRR
Johnny是一位成功的投資者，他有眼光能辨別好的投資機會，為了評估一個商業活動獲利的可能性，Johnny會從預測的現金流來計算「內部投資報酬率(IRR)」，若IRR高於任一家銀行的貸款利率，則該項投資是可行的。
更具體地說，一項投資的IRR等於未來每一期的獲利(benefits)或損失(costs)的現值(present value)之總和等於初始投資額時的利率。例如當利率為10%時，則在第三期發生的$100元損失之現值(present value)為$75.13。
本題給定一項投資案的初始投資金額與未來數期的現金流，請你計算IRR值為多少。以一個例子來作說明：假設初始投資金額為$4,000.00，且未來五期的預測現金收支分別為：$3,852.56, -$2,954.21, $1,500.00, $2,120.86, $2,890.64，這個案子適合投資嗎？為了回答這個問題，我們需要找出使每一期收支金額的現值(present value)之總和等於初始投資金額的利率。下表為利率分別為0%(Actual), 10%, 20%, 30%, 22.294%時試算出來的投資報酬，我們可以發現，當利率為22.294%時，每一期收支的現值總和約等於初始投資金額。22.294%的投資報酬率對 Johnny來說是很吸引人的。
| Actual | 10% | 20% | 30% | 22.294% | |
| 1 | $ 3,852.56 | $ 3,502.33 | $ 3,210.47 | $ 2,963.51 | $ 3,150.24 |
| 2 | -$ 2,954.21 | -$ 2,441.50 | -$ 2,051.53 | -$ 1,748.05 | -$ 1,975.29 |
| 3 | $ 1,500.00 | $ 1,126.97 | $ 868.06 | $ 682.75 | $ 820.12 |
| 4 | $ 2,120.86 | $ 1,448.58 | $ 1,022.79 | $ 742.57 | $ 948.18 |
| 5 | $ 2,890.64 | $ 1,794.86 | $ 1,161.68 | $ 778.53 | $ 1,056.74 |
| Sum | $ 7,409.85 | $ 5,431.24 | $ 4,211.46 | $ 3,419.31 | $ 3,999.99 |
| Sum - Inv | $ 3,409.85 | $ 1,431.24 | $ 211.46 | $ -580.69 | $ 0.01 |
建議你可以把本題當作是對多項式求根的問題，尤其是可用數值方法來求解，例如用「二分法」，重覆地把所有可能的利率集合分成兩半，找出利率落在哪個集合，逐步地縮小尋找範圍。本題假定IRR值會落在-100% ~ 100%的區間，把這個區間當作是一開始的利率集合空間，當每期的現值總和($7,409.85)大於初始投資金額時，選擇「正半部」，否則選擇「負半部」。
Input
輸入資料的第一列有一個整數N( > 0)，表示測試資料的組數，接下來的N列，每列的第一個數為初始投資金額，其後為每一期的現金流，正值表示收入，負值表示支出。每個數值以空白字元隔開。Output
請輸出每組資料的IRR值，其值介於(-100.0, 100.0)之間，請精確到小數點後三位，並顯示百分比符號 % 。請無條件進位到小數點後三位。
Sample Input
3 500.00 75.60 174.40 -60.75 319.25 84.63 31.17 100.00 42.27 35.00 -22.35 10.00 4000.00 3852.56 -2954.21 1500.00 2120.86 2890.64
Sample Output
6.873% -26.369% 22.294%
原文出處
11947 - Cancer or Scorpio
Alice與Michael是一對年輕的夫婦，他們計劃生小孩，已知懷孕需要40週的時間，從最後一次經期的第一天開始算起。本題給定該天的日期，請你推算出預產日為何，並輸出該日的星座。12星座的開始與結束日期如下表：
Input
輸入的第一列有一個整數N(1 <= N <= 1000)表示測試資料的組數。接下來每組資料格式為MMDDYYYY表示經期的第一天。
請注意潤年。
原文出處
| 星座 | 啟始日 | 結束日 |
| Aquarius | 一月, 21 | 二月, 19 |
| Pisces | 二月, 20 | 三月, 20 |
| Aries | 三月, 21 | 四月, 20 |
| Taurus | 四月, 21 | 五月, 21 |
| Gemini | 五月, 22 | 六月, 21 |
| Cancer | 六月, 22 | 七月, 22 |
| Leo | 七月, 23 | 八月, 21 |
| Virgo | 八月, 22 | 九月, 23 |
| Libra | 九月, 24 | 十月, 23 |
| Scorpio | 十月, 24 | 十一月, 22 |
| Sagittarius | 十一月, 23 | 十二月, 22 |
| Capricorn | 十二月, 23 | 一月, 20 |
Input
輸入的第一列有一個整數N(1 <= N <= 1000)表示測試資料的組數。接下來每組資料格式為MMDDYYYY表示經期的第一天。Output
請針對每組測試資料，輸出資料編號、預產期(格式為MM/DD/YYYY)、該日星座，請參考範例資料。請注意潤年。
Sample Input
2 01232009 01232008
Sample Output
1 10/30/2009 scorpio 2 10/29/2008 scorpio
原文出處
訂閱：
文章 (Atom)