Raicom CAIP系列比賽歷年真題均在PTA教育超市售賣。本場比賽真題售賣鏈接入口

RC-u1 大家一起查作弊

分數 15

在今年的睿抗比賽上，有同學的提交代碼如下：

public asfiasfgwef12(){
int tsadflas=3;
int masf11233=2;
int[]wasdf1213= new int[10 +1];
int[] vasf124l = new int[10 + I];
int[][] ddasf1234p= new int[masf11233
...

你肯定很奇怪，這看上去代碼似乎不像是正常寫出來的代碼呀？沒錯，這是這位同學在網絡上購買了所謂的“保研綜測套餐”，商家為逃避賽后查重，給這位同學發去了經過混淆的代碼。然而經過技術支持方的努力，這位同學不僅被封禁，與 TA 購買了相同“套餐”的同學也利用技術手段全部查出，目前主辦方已向警方報案，這些同學的“保研”夢很有可能會轉變為“案底”夢……因此如果你在比賽前也購買了類似的服務，現在迷途知返還來得及——畢竟這個商家起碼還做了一些努力，許多商家號稱“一對一”，實際上將一份代碼發給了數十位同學……

回到題目，雖然具體檢查的手段無法公開，但我們可以嘗試簡化再簡化的手段來找到被這樣混淆的程序。對于給定的大量字符串，你首先要提取出所有的關鍵詞。一個關鍵詞的定義是：由大寫字母、小寫字母、數字組成的字符串，并且前后均為非大小寫字母及數字（包含開頭及換行符）。如以下的字符串：

int[] vasf124l = new int[10 + I];

關鍵詞為：int、vasf124l、new、int、10以及I。

然后對于所有關鍵詞，你需要計算可疑分數的和以及關鍵詞平均長度。其中一個關鍵詞的可疑分數如下定義：

• 如果一個關鍵詞同時包含大寫字母、小寫字母、數字，則分數 + 5 分；
• 否則，如同時包含（大寫字母、數字）或（小寫字母、數字）的，分數 + 3 分；
• 否則，如同時包含（大寫字母、小寫字母）的，分數 + 1 分；
• 其余情況不加分。

對于給定的數據，請你輸出所有關鍵詞的可疑分數的和、長度的和以及數量。

輸入格式:

輸入包含若干行字符串，表示待檢測的程序。保證每行字符串的長度不超過 1000（除了一行最后的換行符外），輸入總長度不超過 6×104，并且至少有一個關鍵詞。

輸出格式:

對于輸入的所有字符串，第一行輸出可疑分數的和，第二行輸出關鍵詞的總長度以及關鍵詞的個數（以避免計算平均值帶來的浮點誤差），用一個空格隔開。

輸入樣例:

static void nnmMNBkf3kfa(){
    int fefvB4=2;
    int [][]fsdk9A=new int[fefvB4][fefvB4];
    fsdk9A[0][0]=1;
    for (int gfdgsUB3 = 0; gfdgsUB3 < fefvB4; gfdgsUB3++) {
        for (int fdnbXZ8 = 0; fdnbXZ8<fefvB4-gfdgsUB3-1; fdnbXZ8++) {
            fsdk9A[gfdgsUB3][fdnbXZ8+1]=fsdk9A[gfdgsUB3][fdnbXZ8]+gfdgsUB3+fdnbXZ8+2;
            fsdk9A[gfdgsUB3+1][fdnbXZ8]=fsdk9A[gfdgsUB3][fdnbXZ8]+gfdgsUB3+fdnbXZ8+1;
            break;
        }
        break;
    }
}

輸出樣例:

155
276 54

代碼長度限制

16 KB

時間限制

400 ms

內存限制

64 MB

棧限制

8192 KB

RC-u2 誰進線下了？II

分數 20

Xepa Legends 是一個第一人稱射擊類大逃殺（“吃雞”）游戲，每局游戲共有 20 支 3 人小隊參加，最后獲勝的隊伍被稱為“捍衛者”。

最近 Xepa Legends 舉行了亞太地區南賽區的線上比賽，爭奪 7 個前往德國曼海姆參加線下賽的資格，國內共有 14 支隊伍參與到了其中。因為比賽十分激烈，直到最后誰進了線下仍有巨大的疑問。小 K 喜歡的國內知名戰隊 DreamTear 因其隊內選手殺馬特表現不佳，正好卡在出線分數前后，請你趕緊幫幫小 K，計算一下最后的分數情況，看看他喜歡的戰隊出線了沒有吧！

Xepa Legends 的常規賽共有 30 支隊伍參加，被分為三組，進行 N 輪比賽，每輪由三組中的兩組組成 20 支隊伍的參賽陣容，進行若干場比賽，最后每個隊伍會獲得一個當輪比賽的排名。

對于每輪比賽，隊伍會根據排名獲得一個在當輪比賽的賦分：

排名	分數
第一名	25 分
第二名	21 分
第三名	18 分
第四名	16 分
第五名	15 分
第六名	14 分
第七名	13 分
第八名	12 分
第九名	11 分
第十名	10 分
第十一名	9 分
第十二名	8 分
第十三名	7 分
第十四名	6 分
第十五名	5 分
第十六名	4 分
第十七名	3 分
第十八名	2 分
第十九名	1 分
第二十名	0 分

給定若干輪比賽隊伍獲得的當輪比賽排名，請你計算出隊伍的賦分，并在若干輪比賽后計算出總賦分，從而最終確定 DreamTear 戰隊能否進入線下，還是只能耍耍花招了。

例如，

• DreamTear 戰隊在第一輪比賽中獲得了第 17 名，第三輪比賽中獲得了第 11 名，第四輪比賽中獲得了第 11 名，那么 DreamTear 戰隊可獲 3 + 9 + 9 = 21 分的賦分；
• KV 戰隊在第一輪比賽中獲得了第 10 名，第三輪比賽中獲得了第 2 名，第四輪比賽中獲得了第 6 名，那么他們可獲得 10 + 21 + 14 = 45 分的賦分。

注：本題與實際情況無關，所有比賽規則、隊伍、隊員名稱均為虛構。

輸入格式:

輸入第一行是一個正整數 N (≤20)，表示有 N 輪比賽。

接下來有 N 部分輸入，每部分是一輪比賽的情況。對每一場比賽，信息共分 20 行，第 i 行（i=1,?,20）給出的兩個非負整數 c 和 p 表示編號為 c 的隊伍在這輪比賽里獲得了第 p 名。

數據保證所有給定的情況中，排名永遠大于等于 1 且小于等于 20，隊伍編號由 1 開始，不超過 30。

輸出格式:

輸出若干行，按分數從大到小依次輸出隊伍的編號及該隊所有輪次游戲結束后的總分。如分數相同，隊伍編號較小的先輸出。

注意由于統計的時候比賽可能并沒有完全結束，所以每個隊伍參加的比賽輪數不一定相同，此時仍然正常計分統計即可。不要輸出未參賽的隊伍分數。

輸入樣例:

3
1 1
2 2
9 3
6 4
7 5
11 6
3 7
13 8
8 9
16 10
4 11
19 12
17 13
5 14
12 15
15 16
14 17
10 18
20 19
18 20
5 11
10 12
30 13
22 14
1 1
28 20
21 16
26 17
2 2
24 3
4 4
29 5
8 6
7 15
6 7
3 8
9 9
25 10
23 19
27 18
19 20
26 19
27 18
18 17
21 16
12 15
28 14
20 13
17 12
14 11
13 10
23 9
29 8
22 7
30 6
15 5
24 4
25 3
16 2
11 1

輸出樣例:

1 50
2 42
11 39
24 34
16 31
6 29
9 29
25 28
29 27
3 25
4 25
8 25
13 22
30 21
7 20
15 19
22 19
5 15
17 15
14 12
23 12
10 10
12 10
19 8
20 8
21 8
28 6
26 4
27 4
18 3

代碼長度限制

16 KB

時間限制

400 ms

內存限制

64 MB

棧限制

8192 KB

RC-u3 勢均力敵

分數 25

用 n>2 個不同的個位數字組成一個 n 位數，顯然有 n! 個不同的結果。可以證明，這 n! 個數字可以被分為勢均力敵的兩組 —— 即平方和相等、且個數也相等的兩組。
本題就請你用程序驗證一下這個結論。
因為本題是一道簡單題，所以規模很小，只考慮 n≤4 的情況。

輸入格式：

輸入第一行給出正整數 n（2<n≤4），隨后一行給出 n 個不同的、在區間 [1, 9] 內的個位數字，其間以空格分隔。

輸出格式：

將所有組成的 n! 個不同的 n 位數分為平方和相等、且個數也相等的兩組。但你只需要輸出其中一組就可以了。每個數字占一行，共輸出 n!/2 行。
注意：解可能不唯一，輸出任何一組解就可以。

輸入樣例：

3
5 2 1

輸出樣例：

125
512
251

代碼長度限制

16 KB

時間限制

400 ms

內存限制

64 MB

棧限制

8192 KB

RC-u4 City 不 City

分數 30

“City 不 City”因為一位外國友人保保熊直播旅游時總是用奇怪的腔調說“好 city，啊！”而走紅中國社交網絡，成為網絡熱梗。事實上，有一些叛逆的年輕人在旅行時會刻意避開網紅打卡點，選擇一些小眾的特色地方小城鎮，不追求 city，而喜歡說“好 country，啊”。
下面給定各個城鎮的旅游熱度和城鎮間的旅行花銷，請你為前來咨詢的旅行者規劃一條最經濟的路線，并且盡可能避開熱度很高的網紅點。

輸入格式：

輸入第一行首先給出 4 個正整數：n 和 m（1<n≤103，1≤m≤5n），依次為城鎮數量（于是城鎮編號從 1 到 n）和城鎮間的通路條數；s 和 t 依次為旅行者的出發地和目的地的城鎮編號。
隨后一行給出 n 個不超過 100 的正整數，依次為 n 個城鎮的旅游熱度。
再后面是 m 行，每行給出一條通路連接的兩個城鎮的編號、這條通路的最小花銷（其數值為不超過 103 的正整數）。通路是雙向的，題目保證任一對城鎮間至多給出一條通路。
同一行的數字間均以空格分隔。

輸出格式：

題目要求從 s 到 t 的最小花銷路線；若這樣的路線不唯一，則取途徑城鎮的最高旅游熱度值最小的那條路線。
在一行中輸出從 s 到 t 的最小花銷、以及途經城鎮的最高旅游熱度值（若沒有途經的城鎮，則熱度值為 0）。數值間以 1 個空格分隔，行首尾不得有多余空格。
若從 s 根本走不到 t，則在一行中輸出 Impossible。

輸入樣例 1：

8 14 7 8
100 20 30 10 50 80 100 100
7 1 1
7 2 2
7 3 1
7 4 2
1 2 1
1 5 2
2 5 1
3 4 1
3 5 3
3 6 2
4 6 1
5 6 1
5 8 1
6 8 2

輸出樣例 1：

4 50

樣例解釋：

從 7 到 8 的最短路徑有 3 條，其中 2 條都經過城鎮 1，于是對應的最高旅游熱度值是城鎮 1 的熱度值 100。解路徑為 7->2->5->8，途徑城鎮 2 和 5，對應的最高旅游熱度值是城鎮 5 的熱度值 50。在最短路徑長度相等的情況下，取熱度值小的解，故輸出的熱度值為 50。

輸入樣例 2：

3 1 1 2
10 20 30
1 3 1

輸出樣例 2：

Impossible

代碼長度限制

16 KB

Java (javac)

時間限制

800 ms

內存限制

512 MB

其他編譯器

時間限制

400 ms

內存限制

64 MB

棧限制

8192 KB

RC-u5 貪心消消樂

分數 30

“消消樂”是以消去方塊贏取分數的游戲。這里介紹一種超級簡單的玩法：玩家每次按住并拖動鼠標，在屏幕上劃出一個矩形，則矩形內的方塊就被消去，玩家得到所有被消去的方塊的分數之和。
每個方塊上的小動物對應不同的得分，例如消去上圖中的綠色青蛙得 2 分、消去紫色貓頭鷹得 5 分、消去黃色小雞得 9 分、消去藍色小牛得 1 分、消去紅色狐貍得 3 分、消去棕色小熊得 8 分。有些方塊是冰塊，消去冰塊會被扣分，所以冰塊上標注了負分。有些方塊是黑洞，玩家的矩形內不能包含任何黑洞，否則所有分數都被黑洞吸走。在一個矩形被消去后，其上方的方塊會掉落以填補空缺，而多出的空缺被黑洞填補。
本題請你幫助玩家實現一個基于貪心策略的自動消除程序，每次都爭取獲得最多的分數，直到無法繼續獲得更多的分數。

輸入格式：

每個輸入包含 1 個測試用例。每個測試用例第 1 行給出一個不超過 100 的正整數 N，對應正方形游戲屏幕的高度和寬度。隨后 N 行，每行給出 N 個數字，代表對應方塊的分數，其中黑洞用 0 表示，小動物用正整數分表示，冰塊用負整數分表示。數值均在 [?100,100] 區間內。

輸出格式：

每一步的消除策略占一行，格式為：

(x1, y1) (x2, y2) 得分

其中 (x1, y1) 為矩形左上角的橫縱坐標，(x2, y2) 為矩形右下角的橫縱坐標，得分 為消去這個矩形的得分。這里我們將游戲屏幕的左上角坐標定義為 (1,1)，右下角坐標定義為 (N,N)。
最后一行給出總分。
注意：當有多個矩形同時對應最大得分時，優先選擇 x1 最小的；如果 x1 一樣，則優先選擇 y1 最小的；如果 y1 也一樣，則優先選擇 x2 最小的；如果 x2 還是一樣，則優先選擇 y2 最小的。

輸入樣例：

4
0 2 5 0
9 2 -6 2
-4 1 -4 3
-1 8 0 -2

輸出樣例：

(1, 2) (2, 4) 15
(3, 1) (3, 1) 5
(4, 2) (4, 3) 5
(2, 4) (2, 4) 2
27

樣例解釋：

游戲的初始界面如題面所示。消去過程如下：

代碼長度限制

16 KB

Java (javac)

時間限制

2000 ms

內存限制

512 MB

Python (python3)

時間限制

2000 ms

內存限制

256 MB

其他編譯器

時間限制

2000 ms

內存限制

64 MB

棧限制

8192 KB