107學年度 校內初選題目
前幾天是雄中資訊學科能力競賽初試，而下面是這次競賽的題目，其中有幾題是出自於UVa的。
Problem A
Description
給你平面上3個點的座標，請你判斷這三點是否共線。
Input Format
輸入含有多筆測資，每筆測資一列，含有6個整數$(x_1 ; y_1 ; x_2 ; y_2 ; x_3 ; y_3)$。分別代表這三個點的x,y座標。每個整數的範圍均介於-10000~10000之間。
Output Format
每筆測資輸出一列。如果這三點共線，請輸出"yes"，否則輸出"no"。
Sample Input
0 0 1 1 2 2
1 2 3 5 -1 -1
0 0 1 2 3 3
Sample Output
yes
yes
no
Problem B
Description
這是一種2個人的遊戲。開始的時候有$n$個整數在一個陣列中，兩個玩家A和B輪流去取陣列中的整數。每次每個玩家能夠從陣列的左邊或右邊（但不能同時從左邊和右邊）拿任意個連續的整數（但至少要拿一個）。
當所有的整數都被拿完時遊戲即結束。每個玩家得到的分數就是他所拿的那些整數的和。
當然，2個玩家都想要贏對方多一些。假如這2個玩家都是「超完美（optimal）」玩家，並且每次遊戲開始時都由 A 先拿，請問當遊戲結束時 A 得到的分數跟 B 得到的分數差是多少？
Input Format
輸入含有多組測試資料。每組測試資料的第一列有一個整數$n ; (0 < n \le 100)$ 代表陣列中整數的數目。接下來為$n$個陣列中的整數。 當$n=0$時代表輸入結束。
Output Format
對每組測試資料輸出一列，當遊戲結束時 A 得到的分數跟 B 得到的分數差是多少？
Sample Input
4
4 -10 -20 7
4
1 2 3 4
3
-10 -20 7
10
5 -10 -20 -40 30 -50 -100 2 -4 -7
0
Sample Output
7
10
-3
8
UVa - 10891
Problem C
Description
這是學二元一次方程式時的經典問題：
有一個籠子裡面有雞和兔。已知有$n$個頭，$m$隻腳。請問籠子裡有幾隻雞，幾隻兔？
請注意：這裡的雞和兔都是正常的。
Input Format
輸入含有多筆測資。每筆測資一列，有2個整數$n,m$。$(1\le n,m <1000)$
Output Format
每筆測資輸出一列：有幾隻雞，幾隻兔。如果沒有答案請輸出"no answer"
Sample Input
5 14
5 15
5 16
Sample Output
3 2
no answer
2 3
Problem D
Description
一個數被稱為「超級指數」，當它至少是2個不同的正整數的次方(>1)時。
例如: 64是超級指數，因為 $64=8^2$，並且$64=4^3$
你的任務是找出所有小於$2^{64}$的所有超級指數。
Input Format
本題沒有輸入。
Output Format
每個超級指數輸出一列，由小到大。前幾個數請見範例輸出。
Sample Output
1
16
64
81
256
512
.
.
.
Hint
使用unsigned long long
共有67385個超級指數
Problem E
Description
給你一個僅含有數字的字串，你的任務是在此字串中找出最大的質數。
在本問題中，質數的範圍限定在 2~100000
Input Format
輸入含有多筆測資，每筆測資一列。
每筆測資含有一字串，僅含有數字且長度最大255
當輸入測資為0時，代表輸入結束，本筆測資不須輸出。
Output Format
每筆測資輸出字串中出現最大的質數。
Sample Input
11245
91321150448
1226406
33
22331
0
Sample Output
11
1321
2
3
331
UVa - 12542
Problem F
Description
一個迴文(palindrome)是指一個字串從左到右和從又到左念起來都一樣。
例如: “上海自來水來自海上”，“madam”，“qq” 等都是迴文。
給你任一個字串，請你算出要經過多少次「交換」才能把它變成迴文。
在這裡「交換」是指將相鄰的2個字元對調。
例如: 字串 “mamad” 可以經由3次交換，使之成為迴文 “madam”，過程如下:
把ad交換，字串變成 mamda
把md交換，字串變成 madma
把ma交換，字串變成 madam
Input Format
輸入的第一列含有一個整數，代表以下有幾筆測資。
每筆測資一列，含有一字串，僅含小寫字元且長度最大100。
Output Format
每筆測資輸出一列，經過多少次「交換」才能把輸入字串變成迴文。如果不可能做到，請輸出"Impossible"。
Sample Input
3
mamad
asflkj
aabb
Sample Output
3
Impossible
2
UVa - 10716
Problem G
Description
給你一個含有障礙物及1~9數字的方陣，你可以從任何一個不為障礙物的格子開始走，最後停在某格子。
每一步你可以走到上、下、左、右四個鄰居格子其中之一。但是你不可以走到有障礙物的格子，你也不可以走到一個格子超過1次。
當你結束時，根據你剛才走過的格子的順序，你會得到一個數字。
請參考下圖：
以這圖片為例，最大數字為791452384。
Input Format
輸入含有多筆測資。
每筆測資的第一列，含有2個數字$R,C(2 \le R,C \le 15, R*C\le30)$，代表方陣的高度及長度。
接下來的$R$列，每列含有$C$個字元。僅含有#及1~9。#代表該格子為障礙物。方陣中至少會有一個格子為數字1~9。
當$R=C=0$時，代表輸入結束。
Output Format
每筆測資輸出一列，輸出你可以走出來最大的數字。
Sample Input
3 7
##9784#
##123##
##45###
2 5
#3#12
#####
0 0
Sample Output
791452384
21
UVa - 11882