12299 - RMQ with Shifts

許胖 | 來自 uniDog | 發表於 2015-12-29 | 分類於 Volume - 122 | UVa

在傳統的 RMQ (Range Minimum Query) 問題中，我們有靜態的陣列 $A$ ，對於每次查詢 $(L,R)$ ( $L\leq{R}$ )，我們回傳 $A[L],A[L+1],\cdots{},A[R]$ 之間的最小值。注意陣列的足標從 1 開始，例如陣列最左邊的元素就是 $A[1]$ 。

在這個問題中，陣列 $A$ 不再是靜態的，我們需要支援另一個操作如下：

$shift(i_1,i_2,i_3,\cdots{},i_k)(i_1 < i_2 < \cdots{} < i_k, k > 1)$

　
代表對 $A[i_1],A[i_2],\cdots{},A[i_k]$ 做「左環形位移」(left circular shift)。

例如，如果 $A=\{6,2,4,8,5,1,4\}$ ，則 $shift(2,4,5,7)$ 會產生 $6,8,4,5,4,1,2$ ，若繼續做 $shift(1,2)$ 則會變成 $8,6,4,5,4,1,2$ 。

Input

只有一筆測試資料，一開始有兩個整數 $n,q$ ( $1\leq{n}\leq{100,000}$ 、 $1\leq{q}\leq{250,000}$ )，分別代表陣列 $A$ 的整數數量、和操作的數量。下一行有 $n$ 個不超過 $100,000$ 的整數，代表一開始 $A$ 當中的整數。接著 $q$ 行，每行有一長度不超過 30 的字串，並且沒有空白字元。所有的操作指令保證都是合法的。

注意：測資很大，最好使用快速的 I/O 方法。

Output

對於每個查詢，印出範圍內的最小值。

Sample Input

7 5
6 2 4 8 5 1 4
query(3,7)
shift(2,4,5,7)
query(1,4)
shift(1,2)
query(2,2)

Sample Output

1
4
6

11992 - Fast Matrix Operations

許胖 | 來自 uniDog | 發表於 2015-12-29 | 分類於 Volume - 119 | UVa

一個最多不超過 $10^6$ 個元素的矩陣有 $r$ 列 (row) 和 $c$ 行 (column)，每個元素的位置為 $(x,y)$ ，其中 $1\leq{x}\leq{r}$ ， $1\leq{y}\leq{c}$ 。一開始所有元素都是 $0$ ，你必須處理以下三種操作：

指令	說明
$1$ $x_1$ $y_1$ $x_2$ $y_2$ $v$	將子矩陣 $(x_1,y_1,x_2,y_2)$ 中每個元素 $(x,y)$ 遞增 $v$ ( $v > 0$ )
$2$ $x_1$ $y_1$ $x_2$ $y_2$ $v$	將子矩陣 $(x_1,y_1,x_2,y_2)$ 中每個元素 $(x,y)$ 設為 $v$
$3$ $x_1$ $y_1$ $x_2$ $y_2$	輸出子矩陣 $(x_1,y_1,x_2,y_2)$ 的總和、最小值和最大值

在上面的描述中，子矩陣 $(x_1,y_1,x_2,y_2)$ 表示所有滿足 $x_1\leq{x}\leq{x_2}$ 和 $y_1\leq{y}\leq{y_2}$ 的元素 $(x,y)$ ，輸入中保證 $1\leq{x_1}\leq{x_2}\leq{r}$ ， $1\leq{y_1}\leq{y_2}\leq{c}$ ，而對於任意操作，矩陣內所有元素總和不會超過 $10^9$ 。

閱讀全文 »

11990 - ``Dynamic'' Inversion

許胖 | 來自 uniDog | 發表於 2015-12-29 | 分類於 Volume - 119 | UVa

給你 $\{1,2,3,\cdots{},n\}$ 的一個排序，依序移除 $m$ 個數字，然後輸出移除前逆序數對 (inversion pairs) 的數量，一個陣列 $A$ 的逆序數對總數就是對於所有有序數對 $(i, j)$ ，使得 $i < j$ 而 $A[i] > A[j]$ 的總數。

閱讀全文 »

11601 - Avoiding Overlaps

許胖 | 來自 uniDog | 發表於 2015-12-28 | 分類於 Volume - 116 | UVa

依序給你 $N$ 個正規矩形 (regular rectangle) 去畫，如果一個矩形沒有跟之前被畫出的矩形重疊，則畫出該矩形。請算出所有被畫出來的矩形的總面積。

註：一個矩形如果是正規的若且唯若他的邊都和 x 軸 y 軸平行。

閱讀全文 »

11610 - Reverse Prime

許胖 | 來自 uniDog | 發表於 2015-12-28 | 分類於 Volume - 116 | UVa

有一些七位數的正整數，其左右相反是質數，且小於 $10^6$ 。例如： $1000070$ 、 $1000090$ 、 $1000240$ 是前幾個顛倒質數 (reverse prime)，因為他們都是七位數，而且左右相反後是一個小於 $10^6$ 的質數。你必須找出所有七位數顛倒質數和他質因數的個數。一個整數的質因數是質數且剛好整除該數，例如 24 的質因數有 2、2、2 和 3。

閱讀全文 »

11423 - Cache Simulator

許胖 | 來自 uniDog | 發表於 2015-12-22 | 分類於 Volume - 114 | UVa

快取記憶體 (Cache) 是一種特別的記憶體，用來縮小讀取中的延遲時間。快取記憶體最基礎的應用就是去保留處理器最常用的的資料，因此現代的處理器使用的主記憶體都擁有一小塊快取記憶體。程式的效能取決於快取的效能，如果資料是在快取記憶體中 (稱為 Hit)，那麼就可以正常的執行；反之，如果資料不在快取記憶體中，程式就會暫停直到資料從主記憶體中讀取進來，計算機架構師總是會去參考快取的 miss 率 (每一百次有多少次資料不在快取中)。

當一次 miss 發生時，新的資料要被放進快取中，而某些舊的資料就要從快取當中移除，這裡有幾個決策法來選擇要移除的資料，一個在計算機系統中最普遍的方法叫做 LRU (最少使用替換演算法，Least Recently Used)，在這個方案裡，最不常用的資料會被移除，讓我們解釋一下這個方案是怎麼運作的。

假設有一個快取有 4 個空間，如果處理器依照 1, 2, 3, 4, 5, 2, 3, 99, 2, 5, 4 的順序拿資料，則狀況如下所述：

閱讀全文 »

11402 - Ahoy, Pirates!

許胖 | 來自 uniDog | 發表於 2015-12-21 | 分類於 Volume - 114 | UVa

在遙遠的大海賊時代，海盜大陸 (Pirate Land) 有著兩批海盜集團，稱為「西印度海盜」(Buccaneer) 和「巴巴利海盜」(Barbary)。每個海盜的身分並不是固定的，有時一個海盜被對方的海盜集團攻擊後，他的身分就會變成攻擊者的身分。突然有一天，一位魔法師出現在海盜大陸，只要他念一聲咒語，他就可以隨意地變換海盜的身分，這個過程稱為「轉移」(mutating)。

大陸上有 $N$ 個海盜，每個海盜的編號依序為 $0$ 到 $N-1$ ，大魔法師可以轉移連續編號的海盜變成某種海盜。

假設有 100 個巴巴利海盜在海盜大陸上，接著魔法師可施展一個魔法，把編號 10 到 33 的海盜變成西印度海盜，此時有 24 個西印度海盜和 76 個巴巴利海盜。

魔法師施展魔法的速度很快，這讓神開始不開心，因為神比較偏好西印度海盜，因此會問魔法師：「告訴我，在編號 2 到 30 號之間有幾個西印度海盜？」現在，魔法師陷入苦思，因為他只善於施法，而不是計數 XD。

於是聰明的魔法師去地球抓了一個聰明的人，但很不幸的就是你！因此你必須去回答神的問題。

閱讀全文 »

11297 - Census

許胖 | 來自 uniDog | 發表於 2015-12-21 | 分類於 Volume - 112 | UVa

今年，我們遇到了很多人口統計的問題，因為在有些城市中有許多移民，或者人口增長非常快。每一年，計數成員協會 (Association for Counting Members, ACM) 在每個區域實施人口普查，這個國家被切割成 $N^2$ 個區域，由 $N\times{N}$ 的網格所組成。你的任務是找出某些區域中最小與最大人口數，因為一年當中會改變的人口數並不是很巨大，因此用一個數字來表示由移民而改變的人口數。

閱讀全文 »

11054 - Wine trading in Gergovia

許胖 | 來自 uniDog | 發表於 2014-12-24 | 分類於 Volume - 110 | UVa

你可能知道在漫畫《阿斯特里克斯和首領之盾》(Asterix and the Chieftain’s Shield) 中，日爾戈維亞 (Gergovia) 有一條街，且街上的居民都是紅酒推銷員。你想知道這個城鎮的經濟是怎麼運作的？很簡單：每個人向城鎮的其他居民買紅酒就行啦。每一天，每個居民都會決定要買或賣多少紅酒，有趣的是，需求和供給量總會是一樣的，因此每位居民都會得到他想要的。

這裡有一個問題：將紅酒從一間房子送到另外一間是很費力的，因為所有的酒品質都很好，日爾戈維亞的居民並不在意跟誰交易，他們只關注買了或賣了多少酒，因此他們會用聰明的腦袋來找出花費最少力氣來運送這些紅酒的方法。

所以在這問題中，你被請求去重建日爾戈維亞一天的貿易，為了簡化問題，我們假設街上相鄰兩棟房子之間的距離是一樣的，從一棟房子運送一瓶紅酒到相鄰的房子需花費一單位的力氣。

閱讀全文 »

637 - Booklet Printing

許胖 | 來自 uniDog | 發表於 2014-12-20 | 分類於 Volume - 006 | UVa

通常印一份文件，首先會印出第一頁，接著是第二頁、第三頁，以此類推，直到最後一頁。然而，當要做出一本可摺疊的小冊子 (fold-over booklet) 時，印出的順序就要稍作改變。小冊子在每張紙上會印四頁，兩頁在紙的正面，兩頁在反面，當你將這些紙依照順序疊好，再將他們從中對折，它們就像一本正常的書一般，每頁的順序都會是正確的。

例如，一本四頁的冊子只會有一張紙，正面依序有第 4 頁和第 1 頁，反面則會有第 2 頁和第 3 頁。

Front              Back
-------------      -------------
|     |     |      |     |     |
|  4  |  1  |      |  2  |  3  |
|     |     |      |     |     |
-------------      -------------

你的任務就是寫一支程式去讀取要列印的頁數，接著輸出列印順序。

Input

輸入檔案包含一至多組測試資料，最後有一行 0 代表檔案結束。

每組測資只有一行，包含一個正整數 n，n 代表要列印的頁數且 n 不超過 100。

Output

對於每個測試資料，輸出哪一頁要印在哪一張紙上，如 Sample Output。如果要印出的頁數無法塞滿整張紙，那麼就印出 Blank 代替，如果印出的紙張正面或反面都是空白的，請不要輸出它。

輸出必須要依照紙張的順序印出，正面 (front) 先，其次是反面 (back)。

Sample Input

Sample Output

Printing order for 1 pages:
Sheet 1, front: Blank, 1
Printing order for 14 pages:
Sheet 1, front: Blank, 1
Sheet 1, back : 2, Blank
Sheet 2, front: 14, 3
Sheet 2, back : 4, 13
Sheet 3, front: 12, 5
Sheet 3, back : 6, 11
Sheet 4, front: 10, 7
Sheet 4, back : 8, 9
Printing order for 4 pages:
Sheet 1, front: 4, 1
Sheet 1, back : 2, 3