題目

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

題目

Problem#

Ulgy Number是只有$2$、$3$、$5$質因數的數字。前11項是：
$$
1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 8,\ 9,\ 10,\ 12,\ 15,\ …
$$
程式必須印出第1500項ugly number

想法#

第$n$個數字一定是前$n-1$個數字中，乘$2$、乘$3$、乘$5$得來的。
找數字的時候不用每個都從頭開始找，要找第$n$個數字，而這個數字勢必$>$第${n-1}$個數字，所以第i, j, k個數字（分別乘$2$、乘$3$、乘$5$），至少要$>$第$n-1$個數字才有可能成為第$n$個數字。在這三種可能中，挑最小的便是第$n$個數字。

Read More

題目

Problem#

有台印表機，有 $n$ 件工作等待列印($1 \le n \le 100$)，你排在第 $m$ 號位置($0 \le m \le {n-1}$)，位置從零開始。
由於實在是太多人印了，所以把每件工作都加上優先權，從1~9代表低到高。
對於是否要列印有特殊的規則：（假設佇列的頭是job j）

• 如果佇列裡頭有比job j還高優先的工作，則把job j放到佇列最後頭。
• 如果沒有，就執行job j。

你需要計算你必須花多少時間才能完成你的工作。

Read More

題目

Problem#

有種資料結構(你不知道是什麼）支援兩種操作：放入、拿出。給定一個操作的序列，你要寫支程式推測出是哪種資料結構（stack, queue, priority queue），不確定則輸出不確定，不知道輸出不知道。

輸入#

每筆測資第一行有數字 $n$($1 \le n \le{1000}$)，代表有 $n$ 筆操作
接著 $n$ 行，每行有兩個數字，第一個數字是操作，1是放入，後頭接著要放入的數字；2是拿出，後頭接著要拿出的數字。
以EOF結尾

Read More

題目

Problem#

有一疊卡，有標數字從$1$到$n$（頂端是$1$），每次從頂端丟掉一張卡片，再把一張卡片放到底部，直到卡片只剩一張。

輸入#

每行代表卡片的數量($n \le{50} $)，以0結尾。

Read More

題目

Problem#

有一排人（長度$N$），每次從一疊卡（20張）頂端抽出一張卡，點數$i$ 代表 列隊每$i$個人要去除。

比如：列隊有10人，抽到點數3的卡，則：

1
2
3
4

1 2 3 4 5 6 7 8 9 10
    x     x     x
    
x 代表去除

Read More