顯示具有 Volume 100XX 標籤的文章。 顯示所有文章
顯示具有 Volume 100XX 標籤的文章。 顯示所有文章

2011年6月3日 星期五

10069 - Distinct Subsequences


本題要計算一個字串內選擇一組特定子字串的所有組合方式之總數。定義兩個字串X = x1x2...xm, Z = z1z2...zk，如果我們說Z是X的子字串，則可以找到一個嚴格遞增子序列表示X內字元的索引，使得對所有i1...ij...ik(j=1~k)使得xij = zj。例如Z=bcdb為X=abcbdab的子字串，其索引序列為< 2, 3, 5, 7>。
本題給你一個字串X與子字串Z，請你找出所有可能的索引序列總數。

Input
輸入的第一列有一個整數N表示測試資料的總數。每組測試資料的第一列為字串X，為全小寫的字串，其長度不超過10000個字元，第二列為字串Z，為全小寫的字串，其長度不超過100個字元。注意所有子字串的組合不超過10^100個。


Output
請每組測試資料輸出一列表示所有子字串組合的總數。

Sample Input
2
babgbag
bag
rabbbit
rabbit

Sample Output
5
3
____________________________________________________________________________________
原文出處
沒有留言:

2011年5月21日 星期六

10077 - The Stern-Brocot Number System

"Stern-Brocot tree"是用來產生一組分數 m/n 集合的一種漂亮的型式(其中m, n互質)，首先由兩個分數開始：，並依下列原則重複計算而得：

在相鄰的兩分數 與 之中插入一分數

例如，一開始我們在 與 之中插入一數，得到一組分數集合,

這三個數中間又可以另外插入兩個分數:

以此類推，得出另一組分數 ,

整個分數集合可以用二元樹(binary tree)來表示：

此結構是有序的，不同位置上的分數皆不會相同。


事實上，我們可以把Stern-Brocot tree當作是一種數值系統，用此系統來表示有理數，因為每一個正的、最簡的分數剛好只出現一次，若我們以字母L與R來表示對右子樹與左子樹的尋訪，則此二元數上的每一個分數都可以用唯一的一組字串來表示。例如，LRRL是指由 開始拜訪右子節點 , 再拜訪左子節點 , 再到左子節點 , 最後到右子節點 ，所以我們可以用LRRL來表示。用這種方式每個分數都可以用一組只包含L, R的字串來表示。


本問題會給你一個正的有理分數，你必須以Stern-Brocot數值系統來表示它。


Input

輸入包含多值測試資料，每組資料一行，共有兩個正整數 m 與 n，且m, n互質，當m=1, n=1時表示輸入結束。


Output

請以Stern-Brocot數值系統來表示每組輸入。


Sample Input

5 7
878 323
1 1

Sample Output

LRRL
RRLRRLRLLLLRLRRR
______________________________________________________________________________________
沒有留言:

2010年9月9日 星期四

10070 - Leap Year or Not Leap Year and ...

古老的民族Gulamatu非常專精於閏年的計算(閏年是可被4整數但不能被100整除的年份，但例外是能被400整除的年份也是閏年)，另外他們每幾年都會有嘉年華會，其中一個嘉年華會稱為Huluculu嘉年華(舉行於可被15整除的年份)，另一個稱為Bulukulu嘉年華(舉行於可被55整除的年份且同時該年度為閏年)。給你一個年份，你必須判斷該年度是否是閏年或有嘉年華會，若皆不是則你的程式必須印出"This is an ordinary year."，列印的順序為：閏年 --> huluculu嘉年華 --> bulukulu嘉年華。

Input
輸入的每一列都有一個表示年份的整數，並以EOF代表檔案結束，每一年都不會小於2000(為了避免與舊曆制相衝突)。請不要對輸入作多餘的假設。

Output
請依序輸出該年度的特性，並在每一組輸出之後多加一列空行。共有四種情況：
This is leap year.
This is huluculu festival year.
This is bulukulu festival year.
This is an ordinary year.

Sample Input
2000
3600
4515
2001

Sample Output
This is leap year.

This is leap year.
This is huluculu festival year.

This is huluculu festival year.

This is an ordinary year.

原文出處
沒有留言:

2010年8月23日 星期一

10033 - Interpreter

某一個指令集架構有10個暫存器，記憶體大小有1000個字組，每一個暫存器的寬度及每一個記憶體位址都佔有3個十進位數字寬，足以表示0~999。每一個指令被編成3位數字的機器語言儲存在記憶體中，機器語言的編碼如下：
  • 100 中止程式。
  • 2dn 設定暫存器 d 的值為常數 n (n=0~9)。(d代表destination，表示最終運算的結果會回存到 d 上，以下的d都具有相同的意思)
  • 3dn 暫存器 d 的值被加上常數 n。
  • 4dn 暫存器 d 的值被乘上常數 n 。
  • 5ds 設定暫存器 d 的值為暫存器 s 的值。
  • 6ds 暫存器 d 的值被加上暫存器 s 的值。
  • 7ds 暫存器 d 的值被乘上暫存器 s 的值。
  • 8da 從記憶體位址取值儲存到暫存器 d ，該記憶體位置被儲存在暫存器 a 內。
  • 9sa 把暫存器 s 的值存回記憶體，記憶體位置被儲存在暫存器 a 中。
  • 0ds 分支運算，若暫存器 s 的值不為 0 則做分支跳躍(jump)，跳躍的位址由暫存器 d 所指定。

所有暫存器的初始值為000，而記憶體的初始值則從輸入中讀取，程式從位置0開始被執行，所有運算結果若發生溢位則取餘數。

Input

輸入的第一列為一個整數，表示有幾組測試資料，每組測試資料請見下一段說明。每組測試資料之前都用一個空行隔開。

每組測試資料最多會有1000個以3位數字表示的機器語言指令，所有指令會從0開始儲存在記憶體中，未指定內容的記憶體空間則初始化為000。

Output

每組測試資料的輸出請參考下一段的說明。每組輸出請用一個空行隔開。

每一組測試資料請輸出一個整數，表示總有多少指令被執行(包含最後的中止指令)，你可以假定程式最後會中止。

Sample Input

1

299
492
495
399
492
495
399
283
279
689
078
100
000
000
000

Sample Output

16
原文出處
感謝David Kuo堪誤
1 則留言:

2010年7月30日 星期五

10050 - Hartals

社會研究組識決定採用一組簡單的參數，用來模擬我國政黨運作的行為，其中一個參數為正整數h(稱為“罷會參數(hartal parameter)”)用來表示同一個政黨連續兩次罷會的間隔時間，雖然這個參數太過簡略了，但還是可以用來預測政黨罷會所帶來的負面影響。接下來的例子會有清楚的說明：

考慮有三個政黨的情況，假設 h1 = 3, h2 = 4, h3 = 8，其中 hi 為政黨 i(i=1, 2, 3)的“罷會參數”，接下來我們摸擬這三個政黨在N=14天內的罷會行為，模擬的情況總是設定第一天為星期日，並且每週的例假日(星期五與星期六)不會有罷會的情況。

1234567891011121314
Days
SuMoTuWeThFrSaSuMoTuWeThFrSa
Party 1 x x x x
Party 2 x x x
Party 3 x
Hartals 12 34 5


上述的模擬結果顯示14天內將罷會5天(第3, 4, 8, 9, 12日)，而第6天沒有罷會是因為該天是例假日星期五，因此可看出兩週的議程已去掉了5天。

本問題會給定各個黨政的“罷會參數”與總議程的天數N，你的任務是算出在N天內共有多少個工作天因為各政黨的罷會而導致議程延岩。

Input

輸入的第一列為一個用來表示有幾組測試資料的整數T。

每組測試資料的第一列為整數N ( $7 \le N \le 3650$) ，用來表示所模擬議程的天數。下一列為另一個整數P ( $1 \le P \le 100$)表示共有P個政黨，接下來的P列分別為各政黨的“罷會參數”(絕不會為7的倍數)。

Output

輸出的每一列表示每一組測試資料所模擬出來的罷會天數(損失多少個工作天)。

Sample Input 

2
14
3
3
4
8
100
4
12
15
25
40

Sample Output 

5
15
沒有留言:

2010年7月29日 星期四

10019 - Funny Encryption Method

一位來自墨西哥蒙特瑞技術研究學院(ITESM Campus Monterrey)的學生發表他新發明的數值加密演算法，這個方法的步驟如下：

Steps : Example

1) 假設令N = M = 265為欲加密的數字

2) 把N視為十進位數值，令X1=265(十進制)

3) 把X1由十進制轉為二進制，故X1=100001001(二進制)

4) 針對以二進制表示的X1計算共有幾個1，X1=100001001共有3個1，即令B1=3

5) 把N視為十六進位數值，令X2=265(十六進制)

6) 把X2由十六進制轉為二進制，故X2=1001100101(二進制)

7) 針對以二進制表示的X2計算共有幾個1，X2=1001100101共有5個1，即令B2=5

8) 最後的編碼為 M xor (b1*b2) M xor (3*5) = 262

這位學生在計算組識(Computational Organization)這門課被當掉了，所以他請求校方在ACM的試題上出一題計算共有幾個位元1的題目，好讓他能順利發表他的加密演算法。

Task :
你必須寫一個程式能讀入一個整數，然後輸出該整數的b1, b2值

The Input

第一列為一數值N，表示共有幾組測試資料，接下來的N列(0<N<=1000)分別為一數值M(0<M<=9999, 十進制)，該數即為欲加密的數值。

The Output

你必須輸出N列，每一列依序輸出b1與b2，以空白字元隔開。

Sample Input

3
265
111
1234

Sample Output

3 5
6 3
5 5

沒有留言:
訂閱： 文章 (Atom)