Uva 10685 - Nature

題目

Problem

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

輸入

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

Read More

Uva 136 - Ugly Number

題目

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

Uva 12100 - Printer Queue

題目

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

Uva 11995 - I Can Guess the Data Structure!

題目

Problem

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

輸入

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

Read More