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 對應到上列的範例測資

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

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

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