1245 . 烷類命名

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

87.5% (7/8)

Submission's AC Ratio

38.1% (8/21)

Tags

CKinfor XXI-CKinfor

Description

最近化學課在上IUPAC烷類命名方法，但是lachu學的不太好，常常會算錯，可是lachu又是化學小老師，這樣太丟臉了，所以請聰明的你幫他寫一個程式，幫助他把烷類命名。

命名方法如下：
一堆碳的結構中，要找出最長的一條碳鏈，作為主鍊。例（氫就省略了）：

這樣最長的一條碳鏈長度是8。有兩條支鏈，有一個碳，稱做C1。如果支鏈上有兩個碳就叫做C2，以此類推，十個碳叫做C10。

我們要做的就是幫lachu找出主鏈長度還有每種官能基的個數。

Input Format

輸入可能包含多筆測試資料。
每筆測試資料的第一行有一個正整數N，表示碳的個數（1 ≦ N ≦ 62）。
接下來的N-1行，每行有兩個編號，代表哪個碳和哪個碳之間有單鍵。（每個碳可以連接不限個數個碳）（編號依序為A、B、C......Z、a、b、c......z、0、1、2、3......9，並且一定是由A開始編號）。
當N = 0時，代表輸入結束，聰明的你當然不會對它輸出任何資料。

Output Format

第一行輸出主鏈的長度。
接下來的幾行輸出各種官能基的名稱及個數，由碳數從小到大排序。如果該種官能基的數量為0，就不用輸出。如果沒有任何的官能基，請輸出"No functional group"。
你可以假設最長碳鏈是唯一的，整個碳鏈是連通的並且沒有迴圈。
輸出格式請參考範例測資

Sample Input 1

6
A C
C E
D B
B C
F E
0

Sample Output 1

5
C1:1

Hints

（為了版面美觀，這裏使用全形的英文字母，但輸入一律為半形英文字母）

Problem Source

原TIOJ1245 / INFOR 21st幹部考(prob A)。Problem Setter：peter50216。

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6
6 1000 65536 262144 7
7 1000 65536 262144 8
8 1000 65536 262144 9
9 1000 65536 262144 10
Submit
Back to Top