#UVa中文翻譯:10020-Minimal coverage(最小覆蓋區間)

問題

給予許多利用[Li,Ri]所表示的小線段(在X坐標軸的整數點上),你必須選擇最少的線段讓它們能夠完整地覆蓋起[0,M]區間。

輸入

第一行有一個數字,表示的是會有幾筆測試資料,後面會跟著一行空白行。

輸入中每一筆測試資料會包含一格數字M(1<=M<=5000),後面跟著一對一對的”Li Ri“(|Li|, |Ri|<=50000, i<=100000),每一對會在不同行。每一筆測試資料最後會以”0 0″作為完結。

每一筆測試資料之間會用一行隔開。

輸出

對於每筆測試資料,你的程式要在第一行輸出能覆蓋[0,M]區間最少要用到的線段數量是多少。接著數行是每一段線段的座標,依據它們的最左邊來排序(Li),並且線段的表示方式要與他們在輸入中的是相同的格式。至於”0 0″這一對則不能被輸出出來。如果[0,M]區間不能被給予的線段給覆蓋,你的程式必須要輸出”0″(不用雙引號)。

在兩個測試資料的輸出的中間印出一行空白行隔開。

範例輸入

2

1
-1 0
-5 -3
2 5
0 0

1
-1 0
0 1
0 0

範例輸出

0

1
0 1

翻譯:灆洢。若翻譯有任何錯誤,歡迎底下留言告知,感謝!

#UVa中文翻譯:10013-Super long sums(超級大的總和)

問題

開發D++這個新的程式語言的創作者發現不論SuperLongInt(超級長整數)這個型態的上限能夠用到多大,有時候程式設計師就是會有機會去運算到比上限更大的數字。1000位數的限制有點太小了,你必須找到最大位數會到1,000,000位的兩個數字的加總。

輸入

輸入的第一行有個整數N,接著一行空白行後有N個輸入區塊。每個區塊的第一行包含了一個數字M(1 <= M <= 1000000),M表示的是要做相加的兩個整數的長度(為了讓兩個整數的長度相同,前面可能會補些零)。接著是要被相加的兩個數字,以直行方式撰寫;意思就是,在接下來M行中每一行包含兩個被空白隔開的單位數的數字。兩個要被相加的整數不會小於1,而且總和之長度不會超過M位數。每個輸入區塊之間會用空白行隔開。

輸出

每個輸出區塊應該包含了在輸入中提供的兩個整數的總和,並且每個區塊應只佔一行,且此數字應該剛好M位數。在每個輸出區塊之間應該用一行空白行隔開。

範例輸入

2

4
0 4
4 2
6 8
3 7

3
3 0
7 9
2 8

範例輸出

4750

470

翻譯:灆洢。若翻譯有任何錯誤,歡迎底下留言告知,感謝!

#UVa中文翻譯:620-Cellular Structure(細胞結構)

有一些APUDOTDLS種的微生物的細胞結構是由A與B兩種不同型態的細胞所串連而成的。

如果這種生物在成長時沒有發生任何突變的話,它的細胞鏈會是底下三種型式的其中一種:

  • 單純階段(simple stage)          O = A
  • 完全成長階段(fully-grown stage)     O = OAB
  • 致突變階段(mutagenic stage)       O = BOA

範例表示中,若出現O=OA代表我們在一個正常生物的細胞鏈的右方加上了一個A細胞,然後又讓包含A的整條鏈又形成了一條正常生物的細胞鏈。換句話說,意思就是從原本的生物鏈又多成長了一個A細胞。

有個研究室研究了一群這種生物。你的任務就是去寫一支程式,這程式可以從某隻生物的細胞鏈序列得知此生物目前的成長階段以及其健康程度。

輸入

一個整數n代表有幾條細胞鏈要被檢驗,接下來n行分別是每條被檢驗的細胞鏈的資訊。

輸出

對於每條要被檢驗的細胞鏈(分在不同行)給予一個適當的答案:
    SIMPLE       若為單純階段
    FULLY-GROWN   若為完全成長階段
    MUTAGENIC    若為致突變階段
    MUTANT      若為其他(對於那些已經突變過的生物)

如果某隻生物同時符合上面兩種階段的話,請以在上面的列表中比較前面的選項作為答案。

範例輸入

4
A
AAB
BAAB
BAABA

範例輸出

SIMPLE
FULLY-GROWN
MUTANT
MUTAGENIC

翻譯:灆洢。若翻譯有任何錯誤,歡迎底下留言告知,感謝!

#UVa中文翻譯:100-The 3n + 1 problem (3n+1問題)

背景

在電腦科學中,我們常將問題分類到各種不同的類別裡(例如:NP問題、無法解決(Unsolvable)的問題、遞迴(Recursive)的問題)。在這個問題裡,你將分析一個演算法的特性,而這個演算法對於所有可能的輸入來說,並不知道其分類為何。

問題

考慮到下面的演算法:

  1. 輸入n
  2. 印出n
  3. 當n等於1時停止
  4.   如果n是奇數,則100img1
  5.   其餘的狀況,則100img2
  6. 回到第二步驟

給予一個輸入22,則會印出下列的數列: 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

上面這個演算法目前被推測認為在給予任何整數輸入值時皆可以停下來(也就是說最後都能夠輸出1)。儘管這個演算法還蠻簡單的,但卻無法確定這個推測是否是正確的;然而可以確定的是,在輸入值n介於0到1,000,000之間時,這個推測是正確的(實際上,還有比0到1,000,000更多的輸入值也是可以讓演算法停下來)。

給予一個輸入n,我們可以去算出總共會有幾個數字會被印出(包含1),而這個總數就被稱作n的循環長度(cycle-length of n)。在上面的範例中,22的循環長度為16。

輸入

輸入會有一系列好幾對的整數i和j,每一對整數i和j會佔一行。所有整數會小於1,000,000並且大於0。

你應該運算每一個包含整數i和j與介於其之間的任意整數中可以造成的最大的循環長度是多少。

你可以假設沒有任何運算超過32位元整數。

輸出

對於每一對的整數i和j,你應該輸出i和j以及包含整數i和j與介於其之間的任意整數中最大的循環長度的值。對於每行輸入所要輸出的這三個數字應該放在同一行,並在數字中間至少用一個空白隔開。整數i和j必須依照在輸入之中的順序輸出,並且後面還要跟著最大的循環長度(在同一行)。

範例輸入

1 10
100 200
201 210
900 1000

範例輸出

1 10 20
100 200 125
201 210 89
900 1000 174

翻譯:灆洢。若翻譯有任何錯誤,歡迎底下留言告知,感謝!

#UVa中文翻譯:114-Simulation Wizardry(模擬巫術)

背景

模擬(Simulation)是個在電腦科學中重要的應用領域,其可被用來開發觀察真實世界中所發生之事件的虛擬模型。模擬有很多不同種的型式,包含有離散事件的模擬型式以及時間驅動的模擬型式。當要設計一個實際可行的方法去近似觀察到的行為,通常可以利用模擬來設計。

這題包含了一個簡單的彈珠台的模擬。在一個彈珠台中,一個鋼球在平面上滾著並且撞到非常多的物體(緩衝器(bumpers)),然後不斷累積分數直到球從平面上”消失”。

問題

你要做的是去寫一支程式模擬一個理想的彈珠台。這個彈珠台有一個上面佈滿著障礙物(緩衝器以及牆壁)的平面,而這個平面可以用一個原點位於左下方的114img1棋盤格來表示,平面上的每個緩衝器皆位於此棋盤格的格點上,而棋盤格中位於平面的邊界上的位置所表示的則是牆壁。鋼球在某個時間點上只會被射出(出現)在棋盤格上一顆,並且會有此顆球所在的初始位置、發射方向以及存活時間的資訊可以取得。在這個模擬中,所有的位置皆用整數表示,而鋼球的方向會是上、下、左、右四個當中的其中一個。鋼球會因為撞上緩衝器(增加分數)或是牆壁(不會增加分數)而反彈來反彈去的,而撞到的緩衝器所得到的分數是由鋼球所撞到的那個緩衝器被定義的分數來決定,並且鋼球的速度為每一個時間區間移動一個格子。當在一個時間區間內鋼球要嘛是移動到緩衝器的上面不然就是牆壁的格點上時,我們就稱作鋼球”撞到了”障礙物;而每次的撞到會造成鋼球往右(順時針)轉90度的”反彈”,並且不會讓鋼球移動到障礙物的上面或是改變其位置(僅會改變鋼球的方向)。注意一點,這樣的定義並不會讓鋼球沿著牆壁滑行的行為構成”撞到”牆壁的這件事件發生。

一個鋼球的生存時間表示的是多少時間單位可以讓鋼球存在於平面上,當超過該時間單位後,鋼球就會從平面上消失。每當鋼球移動一步就會用掉生存時間的一個單位,並且當下一步會撞到緩衝器或是牆壁時會再多用掉一些鋼球的生存時間,而這個被多用掉的一些生存時間就被稱作是這個緩衝器或是牆壁的生存時間消耗量。當球撞到緩衝器前,若其生存時間尚未被消耗殆盡,不管扣掉緩衝器之生存時間消耗量後可生存之時間是否為非正整數,依然可以得到該緩衝器能給予的分數。要注意的一點是,當鋼球只剩下一個單位的生存時間,也就是說再走下一步時鋼球就會”死掉”的時候,若這最後的一次移動會撞到緩衝器的話並不會讓你得到任何的分數。當鋼球的生存時間為非正數時(小於或等於零),則該鋼球就會消失,輪到下一顆鋼球登場並繼續遊戲。

輸入

你的程式應該要模擬一場彈珠台遊戲。輸入會有很多行以用來描述這場遊戲。第一行會有以空白隔開的兩個整數m與n,這兩個數字描述著一個用來表示遊戲中被”玩著”的直角座標系棋盤格,其x介於1到m之間並且其y介於1到n之間(114img2114img3),而m與n的範圍分別是2 < m < 51且2 < n < 51。下一行則給予撞擊牆壁的生存時間消耗量。再下一行給予緩衝器的數量整數p,且114img4。接下來的p行,每一行給予各個緩衝器所在的x座標和y座標,以及撞擊其可得到的分數和其生存時間消耗量,這四個數值在每一行中用空白隔開。緩衝器之x座標與y座標會在此棋盤格的範圍內,可得之分數與生存時間消耗量可以是任意整數(例如:它們有可能是負數;負數的生存時間消耗量反而在鋼球撞擊時可以增加其生存時間)。剩下的行數是用來描述鋼球的部分,每一行用四個被空格隔開的整數去描述一顆鋼球,四個整數分別是:鋼球初始的x與y座標、鋼球行走之方向以及其可生存之時間。鋼球的位置會在棋盤格的範圍內(而且不會位在任何的緩衝器與牆壁上面),而其行走方向會是下面四個值的其中一個:0代表往正x方向行走(右)、1代表往正y方向行走(上)、2代表往負x方向行走(左)、3代表往負y方向行走(下)。最後,鋼球的生存時間則是一個正整數。

輸出

照著每一顆球在輸入被定義的順序,一行一行的輸出各個球個別的得分,並在最後輸出總共的成績。

範例輸入

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

範例輸出

0
0
1
2
2
5

翻譯:灆洢。若翻譯有任何錯誤,歡迎底下留言告知,感謝!