# 國立成功大學資訊工程學系 112 學年度個人申請智慧系統組 - 程式設計測驗 >註：題目為成大學長提供，著作、所有權皆屬於成功大學。 ### 題目: 戶口名簿管理程式 #### 綜合目標 實現一個可以管理各種資料的程式，並透過一些簡易的演算法與資料結構思考如何對程式的效能做有效的提升。 #### 前置準備 這一個程式的一開始，必須先讓使用者輸入一個正整數，這一個正整數表示接下來將會執行的操作次數，舉個例子來說，如果輸入 $5$，那就表示接下來會有 $5$ 個操作要執行。 :::warning 由於我們是使用評測系統做測試，你不需要輸出任何滿足使用者體驗的內容，例如，你不需要輸出 "請輸入一個整數，表示接下來會有幾筆操作" 等，類似內容，只需要直接讓使用者輸入一個正整數即可。 ::: :::warning 我們的測試資料會保證，第一個輸入的數字都是正整數，且數字大小不會超過 $10^5$ ::: :::danger 評分階段時，你的程式的執行時間不能超過 $5$ 秒。 ::: #### 人員基本資料 一個人員的基本資料有以下內容 - 名字 (大小寫英文字母組成，長度不超過 $10$ 個字) - 編號 (編號會是一個正整數，這個正整數的大小不超過 $10^{18}$) - 顏色 (顏色我們用正整數來表示，這一個數字不超過 $100$ ) :::warning 我們會保證在同一時間點，兩個不同人員的名字與編號不會發生重複的情況 ::: #### 每組操作的基本輸入 每組操作的一開始，我們都先讓使用者輸入一個正整數，這一個正整數表示操作的類型。 也就是說，輸入 $2$ 就表示要執行第 $2$ 種操作 (操作二) ##### 範例輸入 ``` 3 1 此行內容省略... 3 此行內容省略... 4 此行內容省略... ``` 以上面這一個例子來說，第一行的數字表示我們要執行的操作次數，下面三行的那三個數字就表示我們依序要執行的操作類型，因此我們會依序執行操作一、三、四。 ### 操作一 : 新增資料 依序輸入人員的名字、編號、顏色，並將此使用者新增至戶口名簿之中 :::warning 請注意，戶口名簿只是一個外部功能的統稱，程式裡面不會內建戶口名簿這個東西，請安心服用。 ::: #### 範例輸入 ``` 3 1 Colten 1001 20 1 Apple 1003 70 1 Bob 1007 20 ``` 以上面的範例來說，我們新增了三個新資料，名字依序分別是 Colten、Apple、Bob，他們三個人的編號依序是 $1001,1003,1007$，顏色分別是 $20,70,20$ :::warning 測試資料當中，保證第一組操作都是操作一。 ::: ### 操作二: 改名 輸入一個編號與新名字，請你將該編號的人的名字改名成新輸入的名字。 :::warning 我們的測試資料會保證目前一定存在此編號。 ::: #### 範例輸入 ``` 3 1 Colten 1001 20 1 Apple 1003 70 2 1001 ColtenOuO ``` 以上方的範例來說，我們在第三次操作的時候將編號 $1001$ 的人名字更改成 ColtenOuO。因此目前資料內兩個人的名字分別為 ColtenOuO 與 Apple。 ### 操作九: 顏色查詢 輸入一個名字，查詢目前這一個人的顏色為多少 :::warning 我們的測試資料會保證目前一定存在此名字。 ::: #### 範例輸入 ``` 4 1 Colten 1001 20 9 Colten 2 1001 ColtenOuO 9 ColtenOuO ``` #### 範例輸出 ``` 20 20 ``` ### ## Subtask 1-A (操作一、二、九) - 10 分 此組子任務會測試你的這三種操作是否為正確的，通過此組內所有測試資料後即可活得對應的分數。 :::warning 額外限制：總操作次數不會超過 $100$，且操作只會出現 $1,2,9$ 其中一個 這意味著我們這組測試資料的第一個輸入的數字不會超過 $100$，你不需要做額外的特判 ::: ## Subtask 1-B (操作一、二、九) - 10 分 1-B 這一個子任務，我們取消了操作總次數不會超過 $100$ 的這一個額外限制，這也意味著在操作數量多的情形下，你必須也考慮到程式的效率。 :::warning 額外限制：操作只會出現 $1,2,9$ 其中一個 ::: 在這裡你會遇到的瓶頸可能是不知道該如何快速的尋找到要修改的資料，可以試著使用一些資料結構輔助。 **提示：HashMap** ### 操作四: 建立朋友關係 :::success Disjoint Set 是一個非常經典的資料結構，可以利用他做到關係建立、查詢與合併，在這裡我們也要實作一個來維護朋友關係。 ::: 依序輸入兩個名字，將這兩個人建立朋友關係 :::warning 測試資料會保證這兩個名字一定存在。 ::: #### 範例輸入 ### 操作三: 朋友圈查詢 依序輸入兩個編號，查詢這兩個人是否是在同一個朋友圈，是的話輸出 YES，否則輸出 NO。 :::warning 朋友圈的定義如下，如果 $a$ 與 $b$ 是朋友，且 $a,b$ 其中一個人是 $c$ 的朋友，那麼 $a,b,c$ 的所有朋友都在同一個朋友圈當中。 ::: #### 範例輸入 ``` 8 1 Colten 1001 1 1 sakinu 1002 2 1 Alice 1003 3 3 1002 1003 4 sakinu Alice 3 1002 1003 4 Colten sakinu 3 1001 1002 ``` #### 範例輸出 ``` NO YES YES ``` ## Subtask 2-A (操作一、三、四) - 10 分 此組子任務會測試你的這三種操作是否為正確的，通過此組內所有測試資料後即可活得對應的分數。 :::warning 額外限制：每次操作只可能是 $1,3,4$ 的其中一種，編號範圍不會超過 $2 \times 10^6$ ::: ## Subtask 2-B (操作一、二、三、四、九) - 10 分 此組子任務會測試你的這五種操作是否為正確的，通過此組內所有測試資料後即可活得對應的分數。 :::warning 額外限制：每次操作只可能是 $1,2,3,4,9$ 的其中一種，編號範圍不會超過 $2 \times 10^6$ ::: ### 操作五 - 新增一個新的資料並輸出所有名字字典序比這一個資料小的人當中，字典序最大的那一個 此組操作的輸入跟操作一相同，唯一不一樣的地方是，必須輸出所有名字字典序比這一個資料的名字小的人當中，字典序最大的那一個名字，如果新輸入進來的這一個人就是字典序最小的那一個人，則輸出 $-1$。 :::warning 字典序比大小的方式為由左到右比較 ASCII 碼的大小，第一個位置如果一樣大就比第二位以此類推，直到比出大小為止，如果已經比到其中一方沒有字元了，則沒有字元的那一方比較小。 ::: #### 範例輸入 ``` 3 1 Colten 1001 1 5 Dad 1002 2 5 Apple 1003 3 ``` #### 範例輸出 ``` Colten -1 ``` ## Subtask 3 (操作一、五) - 10 分 此組子任務會測試你的這兩種操作是否為正確的，通過此組內所有測試資料後即可活得對應的分數。 :::warning 額外限制：每次操作只可能是 $1,5$ 的其中一種 ::: ### 操作六 - 找出最長共同前綴 輸入一個字串，這一個字串由英文字母大小寫組成，且不會超過 $10$ 個字，請你找出目前所有人裡面，哪一個人的名字與這一個字串有最長共同前綴。 :::warning 前綴指的是從最左邊到某一個任意位置，最長共同前綴你可以想像成從左邊開始，直到遇到不一樣的字元停止，能移動最多的就會是最長共同前綴。 舉個例子來說，abbc 與 abbd 的共同前綴長度是 $3$，abbcd 與 abbc 的共同前綴長度是 $4$，因此 abbc 與 abbcd 有著最長共同前綴。 ::: :::warning 如果有多個人的名字是最長共同前綴，請你輸出字典序最大的那一個。 ::: #### 範例輸入 ``` 4 1 Colten 1001 1 1 Colttn 1002 2 6 Colt 6 Colte ```` #### 範例輸出 ``` Colttn Colten ``` ## Subtask 4 (操作一、六) - 15 分 此組子任務會測試你的這兩種操作是否為正確的，通過此組內所有測試資料後即可活得對應的分數。 :::warning 額外限制：每次操作只可能是 $1,6$ 的其中一種 ::: ### 操作七: 給定一個區間，查詢有幾個人編號在此區間內 這一個操作會輸入兩個不超過 $10^{18}$ 的正整數，請你輸出一個數字，表示有幾個人的編號在此區間內。 #### 範例輸入 ``` 5 1 Colten 100 1 1 Apple 300 2 1 Gino 1000 3 7 100 1000 7 200 1200 ``` #### 範例輸出 ``` 3 2 ``` ## Subtask 5 (操作一、七) - 10 分 此組子任務會測試你的這兩種操作是否為正確的，通過此組內所有測試資料後即可活得對應的分數。 :::warning 額外限制：每次操作只可能是 $1,7$ 的其中一種 ::: ### 操作八: 用名字或編號更改某個人的顏色 同一行先輸入名字或編號，接下來輸入一個顏色，請將該資料的顏色更改 :::warning 測試資料保證此名字或編號一定存在。 ::: ### 範例輸入 ``` 3 1 Colten 1001 1 8 Colten 2 8 1001 3 ``` 第二次操作時會將 Colten 的顏色編號變成 $2$，第三個操作時變成 $3$。 ### 操作十: 查詢某個顏色中，有多少對朋友關係 輸入一個大小不超過 $100$ 的正整數，請你回答這一個顏色中有幾對朋友關係。 :::warning 只要在同一個朋友圈內的人都互有朋友關係。 ::: #### 範例輸入 ``` 11 1 Alice 1 1 1 Bob 2 1 1 Colten 3 1 1 Duck 4 1 10 1 4 Alice Bob 10 1 4 Colten Duck 10 1 4 Alice Colten 10 1 ``` #### 範例輸出 ``` 0 1 2 6 ``` 在範例中，第二次操作 $4$ 時，顏色 $1$ 中有一對朋友關係 Alice - Bob，第四次操作 $4$ 時，顏色 $1$ 中有四個人處於相同朋友圈，所以共有6對朋友關係。 特別注意：同一組朋友只能計算一次朋友關係，所以如 Colten - Alice 與 Alice - Colten 這樣的關係只會被計算一次。 ## Subtask 6-A 綜合測試 (所有操作都必須正確) - 15 分 此組子任務會測試你的所有操作是否為正確的，通過此組內所有測試資料後即可活得對應的分數。 :::warning 額外限制：總操作次數不會超過 $20000$，且編號的最大值為 $1000000$ ::: 這意味著只要能在不要太差的複雜度下完成所有操作，即可拿到該分數 ## Subtask 6-B 綜合測試 (所有操作都必須正確) - 10 分 此組子任務的限制等同於題目限制，只有在能用夠好的複雜度正確完成所有操作的前提下，才能獲得對應的分數。