Luckycat   |   來自 Lucky 貓   |   發表於   |   分類於   |   UVa

或許你曾聽過巴比倫塔的傳說，現在這個故事的許多細節已經被遺忘了。現在，我們要告訴你整個故事：

巴比倫人有 n 種不同的積木，每種積木都是實心長方體，且數目都是無限的。第 i 種積木的長寬高分別為 $(x_i,y_i,z_i)$。積木可以被旋轉，所以前面的長寬高是可以互相換的。也就是其中 2 個組成底部的長方形，剩下的一個為高度。巴比倫人想要盡可能的用積木來堆高塔，但是兩塊積木要疊在一起是有條件的：只有在第一塊積木的底部 2 個邊均小於第二塊積木的底部相對的 2 個邊時，第一塊積木才可以疊在第二塊積木上方。例如：底部為 3x8 的積木可以放在底部為 4x10 的積木上，但是無法放在底部為 6x7 的積木上。

給你一些積木的資料，你的任務是寫一個程式算出可以堆出的塔最高是多少。

Input

輸入含有多組測試資料。每組測試資料的第一列含有 1 個整數 $n$ ($n\leq{30}$)，代表以下有幾種不同的方塊。接下的 $n$ 列每列有 3 個整數 $x_i,y_i,z_i$，代表某一種積木的 3 個邊長。

$n=0$ 代表輸入結束，請參考 Sample Input。

Output

對每組測試資料輸出可以堆出的塔最高是多少。

輸出格式請參考 Sample Output。

Sample Input

1
10 20 30
2
6 8 10
5 5 5
7
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
6 6 6
7 7 7
5
31 41 59
26 53 58
97 93 23
84 62 64
33 83 27
0

Sample Output

Case 1: maximum height = 40
Case 2: maximum height = 21
Case 3: maximum height = 28
Case 4: maximum height = 342

Luckycat   |   來自 Lucky 貓   |   發表於   |   分類於   |   UVa

荷馬.辛普森 (Homer Simpson) 是一個非常聰明的傢伙。他很喜歡吃兩種漢堡 (我們稱為 A 和 B 好了)。他吃一個 A 漢堡需要 $m$ 分鐘，吃一個 B 漢堡需要 $n$ 分鐘。如果有 $t$ 分鐘時間的話，請你找出在不浪費一點點時間的情形下，辛普森先生最多可以吃多少個漢堡。如果必須要浪費時間 (這個時候辛普森會喝啤酒)，也請你找出盡可能少喝啤酒的情況下，他最多可以吃幾個漢堡，還有花多少分鐘喝啤酒。

以 Sample Input 的三組測試資料為例說明：

  • $t=54, m=3, n=5$ 我們可以找到最多吃 18 個 A 漢堡使得不浪費一點時間 ($3\times{18}=54$)。
  • $t=55, m=3, n=5$ 我們可以找到最多吃 15 個 A 漢堡和 2 個 B 漢堡使得不浪費一點時間 ($3\times{15}+2\times{5}=55$)。
  • $t=7, m=5, n=3$ 我們可以找到最多吃 2 個 B 漢堡且必須浪費 1 分鐘時間。

Input

輸入含有多組測試資料。每組測試資料一列含有 3 個整數 $m, n, t$ (均介於 1 到 9999)。

Output

對每組測試資料輸出一列，如題目所述。請參考 Sample Output。

Sample Input

3 5 54
3 5 55
5 3 7

Sample Output

18
17
2 1

Luckycat   |   來自 Lucky 貓   |   發表於   |   分類於   |   UVa

你在一家有很多個人電腦的公司上班。你的老闆，連一分都省博士，想要把這些個人電腦連線，但是他又不想要花錢買網路卡。由於你不小心告訴老闆每台電腦出廠時就有一個非同步串列埠在上面，老闆當然把腦筋動到這不用花錢的解決方案上。於是可憐的你被指派來完成這工作軟體的需求，以使這些電腦之間可以連線。

你已經讀了許多關於通訊的書並且知道在傳送及接收訊息時，確保訊息的正確性是一個重點。典型的作法是在訊息的最後加上額外的錯誤檢查碼。這個資訊允許接收程式檢查出傳送的資訊是否有錯誤（在大多數的例子）。於是，你跑到圖書館借回了一本關於通訊厚厚的書，利用週末（當然沒有加班費）研究錯誤檢查的部分。

最後，你決定CRC（cyclic redundancy check）是最適合的錯誤檢查方式。以下描述這個機制：

CRC Generation

待傳遞的訊息被視為一列長長二元數。訊息的第一個位元組（byte）被當作這二元數最重要的位元組，第二個位元組被當作第二重要的位元組，依此類推。這個二元數被稱為”m”。當傳送時會在”m”之後加上2個位元組的CRC檢查碼，然後整個二元數稱為”m2”。

這個CRC的檢查碼被產生使得”m2”可以整除某個16位元的值 “g”。所以當接收端收到一訊息，只要把他除以 “g”，如果餘數為0即代表此訊息正確。

你也注意到，大部分建議採用的g值都是奇數，所以你決定用 34943 當作 g 的值。現在你迫切的任務就是對待傳送的訊息，寫一個程式算出這個CRC的值。

例如：若要傳送的訊息為：AB（二進位的表示式為：01000001 01000010），你必須算出的CRC值應為60 1B（01100000 00011011的十六進位表示式），使得 01000001 01000010 01100000 00011011可以整除34943（10進位）。

閱讀全文 »

Luckycat   |   來自 Lucky 貓   |   發表於   |   分類於   |   UVa

Wavio 數列由一連串的整數構成的。他有一些有趣的特性。

  • 他的長度一定是奇數，也就是 $L=2\times{n}+1$
  • 在 Wavio 數列中的前 $n+1$ 個整數為嚴格遞增。
  • 在 Wavio 數列中的後 $n+1$ 個整數為嚴格遞減。
  • 在 Wavio 數列中沒有相鄰的 2 個數是一樣的。

例如：1, 2, 3, 4, 5, 4, 3, 2, 0 是一個長度為 9 的 Wavio 數列。但是 1, 2, 3, 4, 5, 4, 3, 2, 2 不是一個 Wavio 數列。在這個問題中，給你一連串的整數，請你找出在這些整數中你可以找到的一個子字串為 Wavio 數列的最大長度是多少？例如在以下一連串的整數：

1 2 3 2 1 2 3 4 3 2 1 5 4 1 2 3 2 2 1

最長的 Wavio 數列是：1 2 3 4 5 4 3 2 1，所以應該輸出 9。

Input

輸入含有多組測試資料 (最多不會超過 75 組)。

每組測試資料以 1 個正整數 $N$ ($1\leq{N}\leq{10000}$) 開始，代表給你整數的數目。從下一列開始有 $N$ 個整數。請參考 Sample Input。

Output

對每組測試資料請輸出一列 。在輸入的一連串的整數，請你找出在這些整數中你可以找到的 Wavio 數列最大的長度是多少。

Sample Input

10
1 2 3 4 5 4 3 2 1 10
19
1 2 3 2 1 2 3 4 3 2 1 5 4 1 2 3 2 2 1
5
1 2 3 4 5
20 
13 7 5 7 6 7 2 7 3 20 9 9 15 20 9 10 12 12 4 13

Sample Output

9
9
1
7

Luckycat   |   來自 Lucky 貓   |   發表於   |   分類於   |   UVa

從前有一個國家那裡的人民有非常有趣的習慣。有些人懶惰，有些人富有。有些人非常平窮，有些人小氣。明顯的有些有錢人小氣 (貧窮人絕不會小氣，因為他本來就沒多少東西) 並且懶惰，但是貧窮人也都懶惰 (這也是他們永遠都貧窮的原因)。以下的事在這個國家都是真實的：

a) 由於有錢人小氣，沒有任何東西的價格會超過 $300$ 元。
b) 由於貧窮人懶惰，每件東西的價格都是整數。(連乞丐要錢都至少要 $1$ 元)
c) 硬幣的面值從 $1$ 到 $300$ 元，所以那些懶惰的有錢人可以只用一個硬幣付任何的價錢。

你的任務是找出一個人要付一個價錢有多少種方法，條件是使用硬幣的數目是被限定的。例如：要用 $3$ 個硬幣來付 $6$ 元有 $3$ 種方法：$1+1+4$、$1+2+3$、$2+2+2$。依此類推，一個人付 $6$ 元最多使用 $6$ 個硬幣的方法有 $11$ 種。

Input

每組測試資料 $1$ 列，每列可能含有 $1$ 或 $2$ 或 $3$ 個整數。其中第一個整數一定是 $N$ ($0\leq{N}\leq{300}$)，代表要付的錢是多少。其他的數均大於等於 $0$，小於等於 $1000$。

Output

對每組測試資料輸出一列，代表付 $N$ 元有多少種方法，分為以下三種：

如果該組測試資料僅有 $1$ 個整數，請輸出付 $N$ 元的方法有多少種 (用多少個硬幣不拘)。

如果該組測試資料有 $2$ 個整數 $N$、$L1$，請輸出付 $N$ 元且最多用 $L1$ 個硬幣的方法有多少種。

如果該組測試資料有 $3$ 個整數 $N$、$L1$、$L2$，請輸出付 $N$ 元且最少用 $L1$ 個硬幣，最多用 $L2$ 個硬幣的方法有多少種。在這裡 $L1$ 一定小於等於 $L2$。

Sample Input

6
6 34
6 2 5
6 1 6
0 
0 0 
0 1 
0 0 0 
0 0 1 
0 1 1 
0 1 2 
200 30 75

Sample Output

11
7
9
11
1
1
1
1
1
0
0
2347163627458

untitled   |   來自 Lucky 貓   |   發表於   |   分類於   |   UVa

給你一個由整數組成的 m*n 方陣，你必須要寫個程式，來計算出「重量」（ weight ） 最小的路線。每條路線都是從第一直行的任何一格做為起點，走了若干步之後，至第 n 行（最後一行）的其中一格為終點。所謂的一步就是從第 i 行走至第 i+1 行，其中移動的時候只能走到原本的或是相鄰的一橫列（也就是走平的或是斜一格）。另外要注意的是，第一橫列和最後一橫列（第 m 列）也算是相鄰的，也可以這樣想，就是整個方陣是上下「包」起來的，看起來像一個倒著的圓柱體。總之，對於任何一格能夠走的下一步就如下圖所示：

所謂一個路徑的「重量」（weight）就是此路徑經過的 n 個格子裡，它們的整數總和。舉個例子，下面有兩個不同的5*6 方陣。（實際上你可以注意到它們的不同只在最後一列而已）

這兩個方陣的「最小重量路徑」（ minimal-weight path ）已經在上面分別標出來了。注意一下右邊的方陣，其利用了第一列和最後一列是相鄰的這個性質達到了最小的重量。

閱讀全文 »

Luckycat   |   來自 Lucky 貓   |   發表於   |   分類於   |   UVa

在早期人工智慧的領域中常常會用到機器人，在這個問題中有一支機器手臂接受指令來搬動積木，而你的任務就是輸出最後積木的情形。

一開始在一平坦的桌面上有n塊積木 (編號從 0 到 n-1) 0 號積木放在 0 號位置上，1 號積木放在 1 號位置上，依此類推，如下圖。

機器手臂有以下幾種合法搬積木的方式 (a 和 b 是積木的編號)：

  • move a onto b
    在將 a 搬到 b 上之前，先將 a 和 b 上的積木放回原來的位置 (例如：1 就放回 1 的最開始位罝)
  • move a over b
    在將 a 搬到 b 所在的那堆積木之上之前，先將 a 上的積木放回原來的位罝 (b 所在的那堆積木不動)
  • pile a onto b
    將 a 本身和其上的積木一起放到 b 上，在搬之前 b 上方的積木放回原位
  • pile a over b
    將 a 本身和其上的積木一起搬到 b 所在的那堆積木之上
  • quit
    動作結束

前四個動作中若 a = b，或者 a, b 在同一堆積木中，那麼這樣的動作算是不合法的。所有不合法的動作應該被忽略，也就是對各積木均無改變。

閱讀全文 »

untitled   |   來自 Lucky 貓   |   發表於   |   分類於   |   UVa

這個問題的目地在討論兩個人在所謂的「家庭樹」（family tree 即族譜）裡，他們的關係為何。給你兩組名字：第一組裡有若干對名字，就是所謂的「孩子，家長 對」（child-parent pairs），也就是一對名字，前面的名字是孩子的名字，而後面的名字為其家長的名字；第二組則也有若干對名字，是「欲查詢 對」（query pairs），其表達格式跟前面的「孩子，家長 對」一樣有兩個名字。給你這兩組若干對的名字，你必須寫個程式來判斷在「欲查詢 對」裡，每對的那兩個人彼此關係為何。在這裡我們設定一個人只會有一個家長（雖然我們都知道每個人都有父、母親二者，但是在本問題中，我們僅以其中一人代表）

在此問題裡，我們說「孩子，家長 對」p、q 表示 p 是 q 的孩子。我們為了要表示出所謂的關係，我們先看下面的定義：

  • 當在輸入檔案的「孩子，家長 對」裡有 p q （或者 q p），我們說 p 是 q 的 0 級子孫 （或者 0 級祖先）
  • 在輸入檔案的「孩子，家長 對」裡有 p r （或者 q r），而且 r 是 q 的 (k-1) 級子孫（或者 p 是 r 的 (k-1) 級祖先），則稱 p 是 q 的 k 級子孫 （或者 k 級祖先）

在這個問題裡，任兩個人 p , q 之間的關係一定可歸類到下列四種的其中之一（如果他們有關係的話）

  • 直系子孫類（child）： child、grand child、great grand child、great great grand child，依此類推。（即：孩子、孫子、曾孫、曾曾孫 …）

  • 根據定義，當輸入檔案裡的「孩子，家長 對」有 p q 存在（也就是 p 是 q 的 0 級子孫），則這時 p 是 q 的「child」─即是「孩子」；而當 p 是 q 的 1 級子孫時，我們就稱 p 是 q 的「grand child」─即是「孫子」；當 p 是 q 的 (n+1) 級子孫，則 p 是 q 的「great great … great grand child」，其中有 n 個 “ great “，然後後面接 “ grand child “，也就是「曾曾…曾孫」的意思（其中有 p 個 “ 曾 “ ）。

  • 直系長輩類（parent）： parent、grand parent、great grand parent、great great grand parent，依此類推。（即：父（母）、祖父（母）、曾祖父（母）、曾曾祖父（母））
    （注意：無論是男是女，每一個人如果有家長，則必然是恰有一個）

  • 根據定義，當輸入檔案裡的「孩子，家長 對」有 q p 存在（也就是 p 是 q 的 0 級祖先），則這時 p 是 q 的「parent」─即是「父（母）」；而當 p 是 q 的 1 級祖先時，我們就稱 p 是 q 的「grand parent」─即是「祖父（母）」；當 p 是 q 的 (n+1) 級祖先，則 p 是 q 的「great great … great grand parent」，其中有 n 個 “ great “，然後後面接 “ grand parent “，也就是「曾曾…曾祖父（母）」的意思（其中有 p 個 “ 曾 “ ）。

　

  • 旁系血親類（就是非直系的遠親）（ cousin ）：
    依兩個人對其同祖先的輩分差距，可分為 0th cousin、 1st cousin、 2nd cousin，依此類推；對於兩個人彼此的輩分差距又可分為 once removed、twice removed、three times removed，依此類推。（ removed 有類似親等遠近關係之意）

  • 根據定義，只要 p 和 q 有血緣關係，而且他們不是直系血親關係，那他們就是旁系血親的關係。（或者也可以這樣講，如果把 family tree 當作是一個無向圖，則存在一條路徑連通 p 與 q）今天將 p 和 q 的共同祖先裡，輩份最小的稱作 r （也就是 r 的子孫裡沒有人既是 p 的祖先，又是 q 的祖先。），然後知道 p 是 r 的 m 級子孫， q 是 r 的 n 級子孫。

  • 則我們這樣定義：p 和 q 的關係有 ‘’ kth cousins ‘’，其中 k=min(n,m)（也就是 k 是 p , q 裡面較小的那一個）；而且 p 和 q 的關係還有 ‘’ cousins removed j times ‘’ ，其中 j=| n-m|（也就是 j 為 n 和 m 差的絕對值。）

兄弟姊妹類（sibling）： 0th cousins removed 0 times 就是所謂的「兄弟姊妹」。（也就是他們有同一個家長）

閱讀全文 »

Luckycat   |   來自 Lucky 貓   |   發表於   |   分類於   |   UVa

你喜歡紅綠燈嗎？如果在上班的途中一路上都剛好遇到綠燈那將是一件令人快樂的事。有一天當你在一條筆直的路上開車時，突然發現所有的紅綠燈同時由紅燈變為綠燈。 這使你不禁想到一個問題：下一次所有的燈號都是綠燈的時間要多久（從所有的燈號恰好同時由紅燈轉為綠燈那時算起）。在這裡並不要求所有的燈號同時再由紅轉綠，而是指在某一秒鐘時，所有的燈號都是綠色的就可以了。 並且「下一次」指的是至少有一個紅綠燈曾經轉為紅燈之後。

給你各紅綠燈的間隔時間，你的任務就是算出這個再一次同時為綠燈的時間是多少。

閱讀全文 »

Luckycat   |   來自 Lucky 貓   |   發表於   |   分類於   |   UVa

給你一些變數之間的條件限制（以 x < y 的樣式）。你的任務是寫一個程式輸出所有符合條件的變數排列（由小到大）。例如：

給你 3 個變數 x, y, x 和 2 個條件限制：x < y, x < z，在這 2 個條件限制之下，這 3 個變數的排列有2種：xyz, xzy

閱讀全文 »