2012年12月28日 星期五

866 - Intersecting line segments


在二維座標平面上,一條線段 A 由兩個端點 $A_0=(x_0,y_0)$、$A_1=(x_1,y_1)$ 所構成,而兩條線段 A、B 的交點 (如果有的話),和原本 A、B 的四個點,可以組成四條新的線段。

在圖 1.1 中,交點 P 和線段 B、C 的四個端點一共組成了四條新線段。經過計算所有的交點後,結果總共有五條線段。

圖 1.1 - 線段相交

現在給你一些線段,當你計算出所有可能的交點後,總共會有多少條新線段。

為了簡化這個問題,假設任兩條線段兩端和交點不會出現在端點上。

輸入

輸入一開始有一個正整數,代表接下來測試資料組數,接著會有一行空白行,每組測資間也會有空白行。下面描述了這些測資的格式。

測資第一行包含一個線段的數量 N,接著有 N 行,每行有四個以空白分隔的整數 $x_0$、$y_0$、$x_1$、$y_1$,代表一條線段。

輸出

對於每組測資,每組測資間的輸出以一空白行分隔,輸出格式如下所述。

輸出一個整數,代表計算出所有交點過後線段的數量。

範例輸入

1

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

範例輸出

11

備註:圖 1.2 對應到上列的範例測資

2012年12月23日 星期日

11032 - Function Overloading


多載(Overloading)代表同樣的事物被運用在不同的用途上。在 C++ 裡允許函式多載,這意味著我們函數可以使用相同的名稱但做很不一樣的工作。

考慮兩個相同名字的函數,但有不同的參數如下:

int fun(int a, int b) {
  int ans = 0;
  int i, j, cnt;
  for(i=a; i<=b; i++) {
    cnt = 0;
    for(j=1; j<=i; j++) {
     if( j + sod(j) == i ) cnt++;
    }
    if( cnt == 0 ) ans++;
  }
  return ans;
}

int fun(int a) {
  int i;
  for(i=1; i<=a; i++){
    if( i + sod(i) == a ){
      return i;
    }
  }
  return -1;
}

其中,sod(n) = 數字 n 每個位數之和
因此,
sod(13) = 1 + 3 = 4
sod(204) = 2 + 0 + 4 = 6

輸入

輸入的第一行有一整數,代表接下來的測試資料組數。每組測資都會在一行內,這一行可能有一個整數或是兩個整數,所有的整數都會在 [1, 10000000] 的範圍內。

測試資料組數不會超過 1000。

如果輸入有兩個整數,就會呼叫第一個函式;如果只有一個整數,就會呼叫第二個函式,對應的整數將會傳到對應的參數上。

輸出

對於每組測資,首先輸出測資的編號,接著輸出對應函式的回傳值。

範例輸入

3
101
1 9
20

範例輸出

Case 1: 91
Case 2: 5
Case 3: -1


ProblemSetter: Sohel Hafiz
Special Thanks: Jane Alam Jan

11876 - N + NOD (N)


考慮一正整數的數列 N,其中:

$N_0=1$
$N_i=N_{i-1}+NOD(N_{i-1}), \text{ for } i>0$

在這裡,NOD(x) = x 因數的個數。

因此,這個數列的前幾項為:1, 2, 4, 7, 9, 12, 18, …

給兩個正整數 A 和 B,請找出數列中範圍介於 [A, B] 中整數的個數。

輸入

輸入的第一行有一正整數 T($T<100000$),代表測試資料的組數。每組測資包含兩個整數 A 和 B($1{\leq}A{\leq}B{\leq}1000000$)。

輸出

對於每組測資,輸出是第幾組測資和要求的答案。

範例輸入

3
1 18
1 100
3000 4000

範例輸出

Case 1: 7
Case 2: 20
Case 3: 87


Problemsetter: Sohel Hafiz, Special Thanks: Shamim Hafiz

2012年12月16日 星期日

11709 - Trust groups


曲奇士怪獸協會(Association of Cookie Monsters,簡稱 ACM)的人事部門注意到了,公司內許多工作團隊的生產力並不如預期,他們深入訪問受影響團隊的員工,並且找到問題的根源:信任(更確切地說,缺乏信任)。有些員工並不信任團隊中其他人,這將讓他們變得沒有幹勁且不高興。因此人事部門想要解決這個問題,他們決定重新組織所有團隊,使得這些團隊可以變得更安定,換句話說,讓他們互相信任的人組織在一起。人事部門將會詢問每個員工並且知道每個人信任誰。此外,如果員工 A 信任員工 B 且員工 B 信任員工 C,那麼員工 A 也將信任員工 C。另外顯然地,每個員工也相信他自己。人事部門想要創造出盡可能少的工作團隊來減少管理上的麻煩(他們也不想工作太辛苦)。

有了這些資訊後,他們連絡了你並且要你寫出一支程式去找出最少安定團隊的數量。

輸入

輸入包含數筆測試資料。每筆測資一開始有一行以空白分隔的兩個整數 P 和 T ($1{\leq}P{\leq}1000$,$0{\leq}T{\leq}999000$)。接著有 P 行,每行有一個人的名字,名字的格式為:姓氏、一個逗號、一個空白和人名(舉例來說,McBride, John 或者 Smith, Peter 之類)。姓氏和名字都是由大小寫英文字所組成長度不超過 10 的字串(沒有任何標點符號和空白),每個完整的人名將不會有重複的。在人名之後有 T 組輸入,代表人和人之間的信賴關係。每組輸入的 2 行各有一個人名,格式如上所述,代表第一行的人信任第二行這個人,所有出現在這兩行的人名也會在那 P 人之中。

輸入將由「0 0」做為結束,這筆不必被處理。

輸出

對於每筆輸入,輸出僅有一個整數的一行,代表可組成安定團隊的最少數目。

範例輸入

3 2
McBride, John
Smith, Peter
Brown, Anna
Brown, Anna
Smith, Peter
Smith, Peter
Brown, Anna
3 2
McBride, John
Smith, Peter
Brown, Anna
Brown, Anna
Smith, Peter
McBride, John
Smith, Peter
0 0

範例輸出

2
3

2012年12月15日 星期六

11770 - Lighting Away


Ronju 是「Lavish 辦公大樓」總部的夜間守衛,辦公大樓前有一大片草地,因此每天傍晚 Ronju 來值班時,他個工作就是把草地上的燈打開。然而,對於那麼大片的草地以及為數眾多的燈,這件工作就會相當地累人。

因此他設計了一個巧妙的解決方案--他將手動開關換成光敏觸發開關(light-sensitive trigger)。當地附近的商店以非常便宜的價格來賣這些光敏觸發開關,一旦這些開關照到光,他將自動打開燈光,即使附近某些燈被點亮,他也會感應到。自此之後,Ronju 只要手動打開一些燈,這些燈的燈光就會觸發鄰近的感應器,使得更多的燈被點亮,最終整個草地將會被點亮。

現在 Ronju 想知道:他需要手動打開多少個開關呢?

輸入

輸入一開始有一整數 T,代表接下來的測試組數。每組測資一開始有兩個整數 N ($1{\leq}N{\leq}10000$) 和 M ($1{\leq}M{\leq}100000$),N 代表草地上燈的數量。接下來會有 M 行輸入,每行有兩個以空白隔開的正整數 a、b,$1{\leq}a, b{\leq}N$,代表如果燈泡 a 亮了,就會觸發燈泡 b 也讓 b 一起亮 (依據兩燈間的距離、亮度、感應器靈敏度、方向和其他複雜的因素)。最後,每個測試資料後都有一個空白隔開。

輸出

對於每筆輸入測資,輸出一行格式如「Case k: c」,k 代表測試資料的編號,從 1 開始編號;c 代表最小 Ronju 必須手動打開燈光的數量。

範例輸入

2
5 4
1 2
1 3
3 4
5 3

4 4
1 2
1 3
4 2
4 3


範例輸出

Case 1: 2
Case 2: 2


Problemsetter: Samee Zahur
Special Thanks:  Jane Alam Jan