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

2011年12月17日 星期六

12068 - Harmonic Mean

N個數字a1, a2, a3, ..., aN-1, aN的調和數(harmonic)HN定義如下：

HN = $\displaystyle {N \over {{1 \over a_1} + {1 \over a_2} + {1 \over a_3} + \dots + {1 \over a_{N-1}} + {1 \over a_N}}}$

\epsfbox{p3288.eps}
所以四個數字a, b, c, d的調和數定義為：

H4 = $\displaystyle {4 \over {{1 \over a} + {1 \over b} + {1 \over c} + {1 \over d}}}$

給定N(0 < N < 9)個整數，請你找出它的調和數。

Input

輸入資料的第一列有一個整數S(0 < S < 501)表示測試資料的組數，接下來每組測試資料一列，每列的開頭有一個整數N(0 < N < 9)表示該組測試資料有幾個整數，接下來依序為每個整數，其值大於0小於101。

Output 

請每組測試資料輸出其資料編號，及兩個以 / 隔開的整數表示一個最簡分數，這兩個整數必須互質，且可用64-bit有號整數表示。

Sample Input 

2
4 1 2 3 4
4 2 2 3 1

Sample Output 

Case 1: 48/25
Case 2: 12/7


原文出處
沒有留言:

12041 - BFS (Binary Fibonacci String)

我們知道費氏數列(Fibonacci sequence)：1, 1, 2, 3, 5, 8, ...。我們現在用類似的概念定義一種字串，如下所示：
 
BFS(0) = 0
BFS(1) = 1 (這裡的"0"與"1"為字串，並非數字的0與1)
對於所有 n > 1，BFS(n) = BFS(n-1) + BFS(n-1)，這裡的 + 符號表示兩個字串的合併

故我們定義了一個新的字串序列：0, 1, 01, 101, 01101, ...。
請你寫一個程式找出序列中的第N個字串，並輸出該字串的第 i 個字元到第 j 個字元(N, i, j的序號皆以0開始)。

Input

輸入資料的第一列有一個整數T(T <= 100)表示測試資料的組數，每組資料有三個整數N, i, j (0 <= N, i, j < 2^31 且 i <= j 且 j - i <= 10000)，資料保證不會超出範圍(即 0 <= i, j < BFS(N)字串長度)。

Output

對於每組測試資料，請輸出BFS(N)中從 i ~ j 位置的字串。

Sample Input

3
3 1 2
1 0 0
9 5 12

Sample Output

01
1
10101101
原文出處
沒有留言:

2011年8月13日 星期六

12036 - Stable Grid


給定一個矩陣，如果我們說該矩陣是"穩定的"，表示我們可藉由將同一列元素任意作交換之後，使得每一行的元素值不會重複。
以數學形式來表達，我們定義一 n x n 矩陣G，藉由任意交換同一列 Gi 的元素使得下列敘述成立：

對於每一 j 行，Gi, j的值皆不相同，其中 1 <= i <= n。

例如下列 4 x 4 的矩陣G：

2113
3126
26103
9876
我們藉由重排每一列得到G'：

2113
1362
62310
9876
在G'中的任一行，其行內的元素皆不相同，所以我們可以說該矩陣是"穩定的"。
本題給定一個 n x n 的矩陣，請你判斷該矩陣是否是穩定的。

Input

輸入的一開始會給定一個整數T( <= 500)表示測試資料的組數。
每組測試資料的第一列有一個整數 n (0 < n < 100)表示矩陣的大小，接下來的 n 列每列有 n 個整數，其中第 i 列的第 j 個整數以Gi, j來表示。每列的整數間以一個空白字元隔開，每個元素值皆大於等於 0 且小於等於100。

Output

請輸出每組測試資料的編號，並當該矩陣是穩定的，請輸出"yes"，否則請輸出"no"。

Sample Input 

3
4
2 1 1 3
3 1 2 6
2 6 10 3
9 8 7 6
3
1 1 2
1 1 1
2 2 2
3
1 2 3
2 3 1
3 1 2

Sample Output 

Case 1: yes
Case 2: no
Case 3: yes



原文出處
沒有留言:

12028 - A Gift from the Setter

下列程式碼是計算陣列 a[] 中任兩數之差值的和：

\framebox{ \parbox{5.5in}{ \texttt{ \\ long long GetDiffSum( int a[], int n ) \... ...extit{abs means absolute value} \\ \mbox{\ \ \ \ } return sum; \\ \} \\ } } }

a[]內的元素是依下列式子所決定：
a[i] = (K*a[i - 1] + C)%1000007 for i > 0


給定K, C, a[0] 及陣列長度 n 之值，請你計算下列函式之回傳值：

long long GetDiffSum( int a[], int n )

不過上面提供的程式碼的效率實在是太慢了，直接套用的結果很可能會讓你得到"TLE"，所以你有必要對此做最佳化。

Input

輸入一開始會給定整數T( <= 100)表示測試資料的組數。每組資料有四個整數K, C, n, a[0] 其中1 <= K, C a[0] <= 10000 且 2 <= n <= 100000。

Output

請輸出測試資料編號與GetDiffSum之回傳值。

Sample Input 

2
1 1 2 1
10 10 10 5

Sample Output 

Case 1: 1
Case 2: 7136758

原文出處
沒有留言:

12027 - Very Big Perfect Squares


Background

若整數 n 為完全平方數，表示存在有另一個整數 m 使得 n = m x m。例如前幾個完全平方數為1, 4, 9, 16, 25, 36...。

The Problem

給定一個自然數A，我們想要知道由1到A之間的所有整數中，共有幾個完全平方數(包含1與A)，例如由1到1之間只有一個完全平方數1，由1到5之間共有兩個(1與4)，1到40之間共6個(1, 4, 9, 16, 25, 36)。
由於A的值可能非常非常大，所以我們並不要求精確的答案，只需要最前面的一個位數正確就即可，之後的每個位數補0就好。

Input

輸入有多筆測試資料。每組測試資料一列，僅包含一個自然數A。A的值介於1 ~ 10^1000之間。最後一列為0表示測試資料結束。

Output

請輸出1到A之間共有幾個完全平方數，但是僅需最大的位數正確就好，其餘的補0，例如若結果為59，請你輸出50，若為12345，請輸出10000。

Sample Input

1
5
40
1000
0

Sample Output

1
2
6
30
沒有留言:

2011年8月12日 星期五

12019 - Doom's Day Algorithm

請你判斷西元2011年的某月某日是星期幾。

Input

輸入的第一列有一個表示測試資料組數的整數。接著每一列分別表示一組測試資料，其格式為M D。M表示月份(1~12)，D表示日期(1~31)，所有日期皆是合法的。

Output

請你判斷2011年的該日期是星期幾。星期一到星期日分別為Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday。

Sample Input

8
1 6
2 28
4 5
5 26
8 1
11 1
12 25
12 31

Sample Output

Thursday
Monday
Tuesday
Thursday
Monday
Tuesday
Sunday
Saturday
原文出處
沒有留言:

2011年8月11日 星期四

12032 - The Monkey and the Oiled Bamboo

我拿了一個梯子往上爬，梯子每一階的距離並不相同，我的力氣只有 k，這表示我爬一階的最大高度不超過 k 英呎，而且當我往上爬一階的高度剛好等於 k 英呎時，我的力氣 k 就會減 1。若不到 k 英呎，則 k 值保持不變。
例如假設梯子每一階距離地面的高度分別為1, 6, 7, 11, 13英呎，且當 k = 5時，則：
  1. 從地面到第一階往上爬了1英呎(0到1)，1 < 5，故 k 依然等於5。
  2. 從第一階到第二階往上爬了5英呎(1到6)，5 = 5，故 k 變為4。
  3. 從第二階到第三階往上爬了1英呎(6到7)，1 < 4，故 k 依然等於4。
  4. 從第三階到第四階往上爬了4英呎(7到11)，4 = 4，故 k 變為3。
  5. 從第四階到第五階往上爬了2英呎(11到13)，2 < 3，故 k 依然等於3。
本題給定梯子每一階的高度，請你找出最小的 k 值使我可以爬到梯子的最高階。

Input

輸入的一開始有一個整數T( <= 500)表示測試資料的組數。每組測試資料有兩列，第一列為整數 n 表示梯子共有幾階，第二列有 n 個整數，由小到大分別表示每階的高度。基本上 1 <= n <= 10，但有五組測試資料 10 < n <= 100000。

Output

請輸出每組測試資料的編號與最小的 k 值。

Sample Input 

2
5
1 6 7 11 13
4
3 9 10 14

Sample Output 

Case 1: 5
Case 2: 6

原文出處
沒有留言:

2011年8月10日 星期三

12022 - Ordering T-shirts

The Problem

給定 n 項，請你計算這 n 個項共有幾種可能的大小關係，其比較符號為"<", "="。
例如有兩項，A與B，共有三種可能的大小關係：
A = B; A < B; B < A

若有三項，A, B, C，則共有13種可能的大小關係：
A = B = C; A = B < C; A < B = C; A < B < C; A < C < B; A = C < B; B < A = C; B < A < C; B < C < A; B = C < A; C < A = B; C < A < B; C < B < A

The Input

輸入的第一列有一個整數 t 表示測試資料的組數，接下來分別有 t 列，每列為一個整數 n (1 <= n <= 11)，表示共有 n 項。

The Output

請針對每組測試資料 n ，分別輸出一列整數表示當有 n 項時共有幾種可能的大小關係。

Sample Input

4
1
2
3
4

Sample Output

1
3
13
75
原文出處
沒有留言:

12034 - Race

賽馬比賽中共有 n 匹馬，請你計算共有幾種可能的排名方式。注意，可能會有多匹馬名次相同的情況，例如任兩匹馬有三種可能的相對排名方式：
  1. 並列第一。
  2. 第一匹馬在前，第二匹馬在後。
  3. 第二匹馬在前，第一匹馬在後。

Input

輸入的一開始有一個整數T( <= 1000)表示測試資料的組數，每組測試資料有一個整數 n (1 <= n <= 1000)。

Output

請針對每組測試資料，輸出資料的編號，及共有幾種排名的方式。由於數值可能非常大，故請取除10056的餘數。


Sample Input 

3
1
2
3

Sample Output 

Case 1: 1
Case 2: 3
Case 3: 13

原文出處
沒有留言:

2011年8月9日 星期二

12043 - Divisors

定義兩個函數 d(n) 與 q(n)：

d(n) = 可整除 n 的整數個數。

q(n) = 可整除 n 的整數之總和。

在此我們定義可整除 n 的整數包含 1 與 n 本身，例如當 n = 6，可整除6的整數為1, 2, 3, 6，故 d(6) = 4; q(6) = 12。

另外，我們定義兩個函數 g(a, b, k) 與 h(a, b, k) 為



其中 a <= i <= b 且 i 可被 k 整除(羅馬符號sigma(i)即為q(i)，因譯者打不出該符號，故以q(n)代替)。

例如 g(5, 12, 3) = d(6) + d(9) + d(12) = 4 + 3 + 6 = 13 且 h(5, 12, 3) = q(6) + q(9) + q(12) = 12 + 13 + 28 = 53。本題給定 a, b, k 請你計算 g(a, b, k), h(a, b, k)。

Input

輸入的第一列有一個整數T(T <= 75)表示測試資料的組數，每組資料有三個整數a, b, k，且 0 < a <= b <= 100000; 0 < k < 2000。

Output

請針對每組測試資料，輸出 g(a, b, k) 與 h(a, b, k)，並以一個空白字元隔開。

Sample Input

2 
5 12 3 
1 100 3

Sample Output

13 53 
217 3323
原文出處
沒有留言:

2011年8月7日 星期日

12015 - Google is Feeling Lucky


Google搜尋網站有一個功能按鍵：「好手氣」，按下這個按鍵可以省略搜尋結果頁面，直接連結到排名最高的網頁。問題是哪個網頁才是排名最高的網頁呢？Google自然有自已的一套排名原則，我們只需假設每個網頁都對應一個分數，分數最高的網頁皆可能被選中。本問題很簡單，給定10個網址與其排名的分數，請你輸出排名最高的網址。

Input

輸入的第一列有一個整數T，表示測試資料的組數。每組有10個網址及其分數，URL網址為一個不含空白字元的字串，其長度大於等於1，小於等於100。

Output

請針對每組測試資料輸出分數最高的網址，輸出格式請參考範例資料。



Sample Input 

2
www.youtube.com 1
www.google.com 2
www.google.com.hk 3
www.alibaba.com 10
www.taobao.com 5
www.bad.com 10
www.good.com 7
www.fudan.edu.cn 8
www.university.edu.cn 9
acm.university.edu.cn 10
www.youtube.com 1
www.google.com 2
www.google.com.hk 3
www.alibaba.com 11
www.taobao.com 5
www.bad.com 10
www.good.com 7
www.fudan.edu.cn 8
acm.university.edu.cn 9
acm.university.edu.cn 10

Sample Output 

Case #1:
www.alibaba.com
www.bad.com
acm.university.edu.cn
Case #2:
www.alibaba.com

原文出處
沒有留言:

12049 - Just Prune The List

給你兩組整數集合，你可以從這兩個集合中移走任意多個整數，你的目標是要從中移走最少數量的整數之後，使得這兩個集合內的所有元素皆相同，其排列順序並不限，例如下列兩個集合：

List #11 2 3 2 1
List #21 2 5 2 3

從第一列中移除1，並從第二列中移除5，則這兩個集合將有相同的元素，如下所示：

List #11 2 3 2
List #21 2 2 3

為了達成兩個集合元素皆相同的目的，你最少必須移除掉多少個整數呢？

Input

輸入的第一列有一個整數T(T <= 100)，表示測試資料的組數。每組測試資料的第一列包含兩個整數N, M，N(1 <= N <= 10000)表示第一組有幾個元素，M(1 <= M <= 10000)，表示第二組有幾個整數，接下來的兩列分別為這兩組資料的所有元素，每個元素皆可以32位元的有號整數來表示。

Output

請依題意輸出每組測試資料的答案。

Sample Input

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

Sample Output

2
原文出處
沒有留言:

2011年7月30日 星期六

12003 - Array Transformer

本題給定一個大小為 n 的陣列，其元素分別為A[1], A[2], ..., A[n]，將它經由 m 個指令轉換後輸出，每道指令格式為(L, R, v, p)，首先計算從A[L]到A[R](包含兩者)中，其值嚴格地小於 v 的個數，假設共 k 個，然後將A[p]的值改為 u*k/(R-L+1)只取整數的部份。

Input 

輸入的第一列有三個整數 n, m, u(1 <= n <= 300,000; 1 <= m <= 50,000; 1 <= u <= 1,000,000,000)，接下來的 n 列每列一個整數表示陣列的元素A[i](1 <= A[i] <= u)，再接下來的 m 列為轉換的指令，共有四個整數L, R, v, p(1 <= L <= R <= n; 1 <= v <= u; 1 <= p <= n)。

Output 

請輸出 n 列，依序把陣列中的每個元素印出來。

Sample Input 

10 1 11
1
2
3
4
5
6
7
8
9
10
2 8 6 10

Sample Output 

1
2
3
4
5
6
7
8
9
6

只有一道指令：L=2, R=8, v=6, p=10，共有4個數(2, 3, 4, 5)小於6，所以 k = 4，因此A[10]設為 11*4/(8-2+1) = 44/7 = 6(只取整數)。

原文出處
沒有留言:

2011年7月29日 星期五

12002 - Happy Birthday

當生日派對結束之後，大家拍拍屁股走人，留下壽星一個人整理客廰，他開始把客廳桌上的盤子拿到廚房清洗，他雖然很強壯可以一次拿得動所有盤子，但是卻害怕自已笨手笨腳打破盤子，所以希望所收捨的盤子可以穩穩地疊在一起，避免拿到廚房的途中摔破盤子而花上更多時間清理。讓盤子穩穩地疊在一起的方法是下層的盤子必須大於或等於上層盤子的大小。

一開始他兩手空空站在桌旁的一端，他沿著桌子走到另一端，沿途選擇一些盤子拿在手上，每當他發現一個盤子時，他可以：
  • 不理它。
  • 如果他手上沒有盤子，他可以拿起那個盤子。
  • 如果他手上有一疊盤子，他可以拿起桌上的盤子放到手上的那疊盤子上。
  • 如果他手上有一疊盤子，他可以把手上的盤子疊在桌上的盤子上，再把整盤拿在手上(包含最下面的那個)。
他希望儘可能地拿最多盤子到廚房，請你幫他選擇取盤子的順序。

Input 

輸入有多筆測試資料，每組資料兩列，第一列有一個整數N(1 <= N <= 500)表示桌上盤子的總數，第二列有N個整數k1, k2, ..., kn(1 <= ki <= 1000)依序表示他沿途發現的般子大小。當N=0表測試資料結束。

Output 

請每組測試資料輸出一趟最多可以收拾幾個盤子。

Sample Input 

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

Sample Output 

4
6

原文出處
沒有留言:

2011年7月28日 星期四

12005 - Find Solutions

請參考下列等式：

c = ab - $\displaystyle {\frac{{a+b}}{{2}}}$ + 1
給定 c，請你算出有幾組(a, b)使得等式成立(a, b皆必須為正整數)。

Input 

輸入資料大約有3000列，每列有一個整數 c (0 < c <10^14)，當讀到0時表示測試資料結束。

Output 

請每組資料輸出一列，每列有兩個整數，第一個整數為 c，第二個整數表示使等式成立的(a, b)共有幾組。

Sample Input 

1020
400
0

Sample Output 

1020 8
400 2


註：第一筆測試資料中，使等式成立的8對(a, b)為：(1, 2039), (2, 680), (5, 227), (14, 76), (76, 14), (227, 5), (680, 2), (2039, 1)。
原文出處
沒有留言:

2011年7月26日 星期二

12001 - UVa Panel Discussion


UVa線上解題裁判小組欲舉行一次小組研討會，打算從300位參賽者中找3~4位來加入此次研討活動。尋找參賽者的原則有一些限制條件，他們決定若最後只找3位參賽者，則希望這3位皆來自相同國家，或是皆來自不同國家。若決定找4位參賽者，則希望這4位最少來自三個不同的國家，或是其中最少有三位來自相同國家。
請你分別計算這兩種情況有幾個可能的組合可選。

Input

輸入有多組測試資料，每組資料兩列。第一列有兩個整數N與M，並一空白字元隔開，其中N(3 <= N <= 300)表示所有參賽者總數，M(1 <= M <= 50)表示共有幾個不同的國家。第二列有N個大小介於1 ~ M的整數，並以空白字元隔開，分別表示所有N位參賽者所來自的國家(所有參賽國家不見得等於M)。最後一列有兩個零，表示測試資料結束。

Output

請毎組測試資料輸出兩個整數，第一個整數表示依題意選擇3位參賽者的可能組合總數，第二個整數則是選擇4位參賽者的組合總數。

Sample Input 

3 5
5 4 2
5 3
3 1 3 2 2
10 10
1 8 9 1 6 7 3 4 10 4
0 0

Sample Output 

1 0
4 4
104 209

原文出處
沒有留言:

2011年7月3日 星期日

12004 - Bubble Sort


下列c語言程式為泡泡排序演算法(bubble sort)，注意程式碼count++;的地方，每次做資料交換，count的值即累加1。

int findSwaps( int n, int a[] )
{
    int count = 0, i, j, temp, b[100000];

    for( i = 0; i < n; i++ ) {
        b[i] = a[i];
    }
    for( i = 0; i < n; i++ ) {
        for( j = 0; j < n - 1; j++ ) {
            if( b[j] > b[j+1] ) {
                temp = b[j];
                b[j] = b[j+1];
                b[j+1] = temp;

                count++;
            }
        }
    }
    return count;
}
本題請你計算對於不同的陣列大小n，陣列元素交換次數的期望值為何(即count的期望值)？也就是說，當陣列大小為 n，且陣列元素a[]分別為1~n的值之隨機分佈時，若呼叫findSwaps()無限多次，則count的平均值應為多少？

Input 

輸入的第一個整數為T( <= 1000)表示測試資料的組數，接下來有T列，每列為一個整數 n (1 <= n <= 100000)。

Output 

請對每個 n 之值輸出count的期望值為何，若非整數請輸出最簡分數，輸出格式請參考範例資料。

Sample Input 

2
1
2

Sample Output 

Case 1: 0
Case 2: 1/2

原文出處
沒有留言:

2011年6月6日 星期一

12024 - Hats

The Problem

到戲院看戲前，有戴帽子的人會先把帽子寄放在寄物服務台，等到戲散場後他們就會回到服務台拿回自已的帽子，不過總是會有人拿錯帽子。請問每個人都拿錯的機率為何？

The Input

第一列有一個整數 t 表示測試資料的組數。每組測試資料只有一個整數 n (2 <= n <= 12)表示人(或帽子)的總數。

The Output

請以下列格式輸出每個人都拿錯帽子的機率，請不要約分。

Sample Input

3
2
3
4

Sample Output

1/2
2/6
9/24




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