2017年第八屆藍橋杯國賽試題及詳解（Java B組）

• 結果填空 (滿分17分)
• 結果填空 (滿分45分)
• 代碼填空 (滿分23分)
• 程式設計（滿分43分）
• 程式設計（滿分71分）
• 程式設計（滿分101分）

1. 標題：平方十位數

由0~9這10個數字不重復、不遺漏，可以組成很多10位數字，

這其中也有很多恰好是平方數（是某個數的平方），

比如：1026753849，就是其中最小的一個平方數，

請你找出其中最大的一個平方數是多少？

注意：你需要提交的是一個10位數字，不要填寫任何多余內容，

答案決議

答案：9814072356

如果直接從 9876543210 遍歷到 1026753849，未免太暴力了，可以遍歷平方根，然后再平方判斷是否有重復的數位，

public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        boolean[] vis = new boolean[10];
        long maxx = (int) Math.sqrt(9876543210.0);
        for (long i=maxx;i>=32043;i--) {
            long k = i*i;
            int flag = 1;
            for (int j=0;j<=9;j++) {
                vis[j] = false;
            }
            while(k>0) {
                int temp = (int) (k%10);
                if (vis[temp]) {
                    flag = 0;
                    break;
                }
                else {
                    vis[temp] = true;
                }
                k/=10;
            }
            if(flag==1) {
                System.out.println(i);
                System.out.println(i*i);
                break;
            }
        }
    }
}

2. 標題：生命游戲

康威生命游戲是英國數學家約翰·何頓·康威在1970年發明的細胞自動機，
這個游戲在一個無限大的2D網格上進行，

初始時，每個小方格中居住著一個活著或死了的細胞，
下一時刻每個細胞的狀態都由它周圍八個格子的細胞狀態決定，

具體來說：

1. 當前細胞為存活狀態時，當周圍低于2個（不包含2個）存活細胞時， 該細胞變成死亡狀態，（模擬生命數量稀少）
2. 當前細胞為存活狀態時，當周圍有2個或3個存活細胞時， 該細胞保持原樣，
3. 當前細胞為存活狀態時，當周圍有3個以上的存活細胞時，該細胞變成死亡狀態，（模擬生命數量過多）
4. 當前細胞為死亡狀態時，當周圍有3個存活細胞時，該細胞變成存活狀態， （模擬繁殖）

當前代所有細胞同時被以上規則處理后, 可以得到下一代細胞圖，按規則繼續處理這一代的細胞圖，可以得到再下一代的細胞圖，周而復始，

例如假設初始是:(X代表活細胞，.代表死細胞)

.....
.....
.XXX.
.....

下一代會變為:

.....
..X..
..X..
..X..
.....

康威生命游戲中會出現一些有趣的模式，例如穩定不變的模式：

....
.XX.
.XX.
....

還有會回圈的模式：

......      ......       ......
.XX...      .XX...       .XX...
.XX...      .X....       .XX...
...XX.   -> ....X.  ->   ...XX.
...XX.      ...XX.       ...XX.
......      ......       ......

本題中我們要討論的是一個非常特殊的模式，被稱作"Gosper glider gun"：

......................................
.........................X............
.......................X.X............
.............XX......XX............XX.
............X...X....XX............XX.
.XX........X.....X...XX...............
.XX........X...X.XX....X.X............
...........X.....X.......X............
............X...X.....................
.............XX.......................
......................................

假設以上初始狀態是第0代，請問第1000000000(十億)代一共有多少活著的細胞？

注意：我們假定細胞機在無限的2D網格上推演，并非只有題目中畫出的那點空間，
當然，對于遙遠的位置，其初始狀態一概為死細胞，

注意：需要提交的是一個整數，不要填寫多余內容，

答案決議

4.標題：小計算器

模擬程式型計算器，依次輸入指令，可能包含的指令有

1. 數字：‘NUM X’，X為一個只包含大寫字母和數字的字串，表示一個當前進制的數
2. 運算指令：‘ADD’,‘SUB’,‘MUL’,‘DIV’,‘MOD’，分別表示加減乘，除法取商，除法取余
3. 進制轉換指令：‘CHANGE K’，將當前進制轉換為K進制(2≤K≤36)
4. 輸出指令：‘EQUAL’，以當前進制輸出結果
5. 重置指令：‘CLEAR’，清除當前數字

指令按照以下規則給出：
數字，運算指令不會連續給出，進制轉換指令，輸出指令，重置指令有可能連續給出
運算指令后出現的第一個數字，表示參與運算的數字，且在該運算指令和該數字中間不會出現運算指令和輸出指令
重置指令后出現的第一個數字，表示基礎值，且在重置指令和第一個數字中間不會出現運算指令和輸出指令
進制轉換指令可能出現在任何地方

運算程序中中間變數均為非負整數，且小于2^63，
以大寫的’A’ ~ ‘Z’ 表示10 ~ 35

[輸入格式]

第1行：1個n，表示指令數量
第2…n+1行：每行給出一條指令，指令序列一定以’CLEAR’作為開始，并且滿足指令規則

[輸出格式]

依次給出每一次’EQUAL’得到的結果

[樣例輸入]

7
CLEAR
NUM 1024
CHANGE 2
ADD
NUM 100000
CHANGE 8
EQUAL

[樣例輸出]

2040

補充說明：

1. n 值范圍: 1<= n < 50000
2. 初始默認的進制是十進制

資源約定：
峰值記憶體消耗 < 256M
CPU消耗 < 1000ms

請嚴格按要求輸出，不要畫蛇添足地列印類似：“請您輸入…” 的多余內容，

所有代碼放在同一個源檔案中，除錯通過后，拷貝提交該原始碼，
注意：不要使用package陳述句，不要使用jdk1.7及以上版本的特性，
注意：主類的名字必須是：Main，否則按無效代碼處理，