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$個字元。僅含有#及19。#代表該格子為障礙物。方陣中至少會有一個格子為數字19。 當$R=C=0$時,代表輸入結束。

Output Format

每筆測資輸出一列,輸出你可以走出來最大的數字。

Sample Input

3 7
##9784#
##123##
##45###
2 5
#3#12
#####
0 0

Sample Output

791452384
21

UVa - 11882