題目

Problem#

輸入兩個數字a, b，要算a/b的小數，如果有循環小數部分出現，則只輸出一次
每筆輸出最後要輸出循環小數的長度（如果沒有則輸出This expansion terminates.)

想法#

模擬長除法，一位一位除
輸出很鳥（注意換行，每行最多50字，小數點也算）

Read More

題目

Problem#

有多種樹的名字，你要輸出每種樹佔的比例（按名稱字典序）

想法#

map練習題

Read More

題目

Problem#

有一堆電腦用網路連著，今天你是網管，你想知道電腦 $i$ 跟電腦 $j$ 是否有相連（在同個網路內），並且你也可以將兩台電腦相連。有兩個操作：

• 相連 c i j
  將電腦$i$和電腦$j$相連
• 查詢 q i j
  查詢電腦$i$和電腦$j$是否相連

程式最後輸出查詢有相連,沒相連

Read More

題目

Problem#

http://rubyacm.blogspot.com/2010/08/10033-interpreter.html

想法#

挺有趣的一題，要寫個小VM執行code，算出執行了幾個指令。

Read More

題目

Problem#

給定任意的圖形，問可不可以在每個點上著不同兩種的顏色，並且相同顏色的點不相鄰。

• 沒有自環
• 無向圖
• 強連通

想法#

Read More

題目

Problem#

有個程式要記錄眾多的事件，使用者可以輸入指令註冊要監測的事件，指令要包含事件的ID(Q_num)跟週期(Period)，格式如下：

1

Register Q_num Period

代表要註冊Q_num事件，每Period秒執行一次。而程式可以一次監測多個事件（用指令註冊），你要寫程式輸出前$k$個執行的事件。
(如果在同一秒有多個事件，則以Q_num遞增排序)

Read More

題目

Problem#

字串距離是一個代表兩個字串的非負整數。接著要轉換(transform)$a$字串至$b$字串，有三種操作：插入(Insert)、刪除(Delete)、及取代（Replace)。
字串距離就是轉換的數量，求任意$a$字串轉換至$b$字串的字串距離及如何轉換的。

輸入#

每筆case有兩行字串$a$、$b$，以EOF結尾，字串的長度不超過$80$

Read More

題目

Problem#

給定一個序列 $S = {S_1, S_2, …, S_n}$ ，找一個連續的子序列使得相乘最大。

想法#

這題可以直接做，也可以DP

Read More

題目

Problem#

(簡化)
有一組數列($a_i$)，對所有$i<j$，求最大的$a_i - a_j$

想法#

$\mathcal{O}(n^2)$暴力會TLE，但觀察可以發現，對於每個$a_j$，如果$a_i - a_j$要最大，那$a_i$一定越大越好，所以可以直接維護一個最大值($M$)，代表從$1 \sim i$的最大。
只要掃一遍，就得到答案。($\mathcal{O}(n)$)

Read More

題目

Problem#

大自然存在著食物鏈，體型大的動物吃小動物，小動物吃植物，死亡的動物被分解，作為植物的養分。
而你的任務是給定一組動物，求出最大的食物鏈動物數量為何？假如A吃B，你可以認定它們在同個食物鏈裡。

輸入#

每筆測資開頭有兩個整數 $C$ 代表有幾隻動物和 $R$ 有幾組關係；接著 $C$ 列，每列有一個名字（字串、只有小寫、不超過30字）；再接著有 $R$ 列，每列有兩個名字，代表第二個動物吃第一個動物。
你可以認定沒有一隻動物是自己的獵食者。
輸入終止在 $C = R = 0$ ，每筆測資間有空白列。

Read More