4586 . pD. 京都大學 (IUPAC)

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

Description

題目 PDF 檔在這裡

京都大學的國際學士課程計劃（Kyoto iUP）是專為國際學生設計的一個特別學術項目。這個計劃不要求學生在入學時具備日語能力，提供六個月的預備課程以及四年的本科學習，總共 4.5 年。

iUP 計劃的主要特色包括：

  1. 學費及入學費減免：學生可獲得學費及入學費的減免，同時還有每月的獎學金，以減輕經濟負擔。
  2. 語言支持：入學時不需要日語能力，計劃內提供密集的日語課程，幫助學生逐步適應。
  3. 多樣化的學術領域：包括綜合人類學研究、教育、法學、經濟學、科學、藥學、工程和農業等多個學科。
  4. 全面的學生支持：包括住宿安排、生活支援等。

每年該計劃約有 30 個入學名額，競爭相當激烈。例如，2024 學年有 576 名申請者中只有 31 人被錄取。

若想了解更多詳情，可以訪問 京都大學iUP計劃官網。

以建國中學數理資優班的傳奇嘴砲競賽選手出名，魔方社的 Ancuber 學長在歷史的洪流之中留下了自己的痕跡。

Ancuber 與就學期間曾多次唬爛班上同學，使同學對其刮目相看，包括透過思想實驗比較出手指的相對長度、通過臺大牙醫一階後為了魔術方塊建中賽而放棄等。

賴泓安的神通廣大不侷限於與人面對面的互動，在網路上，他也作為嘴砲競賽選手活躍。最為知名的豐功偉業便是在網路上分析中華民國升學制度時被路人當作失意的落榜生後，告訴他們自己不但拿了滿級分，還不屑在臺灣念大學，將酸民們打得心服口服、一敗塗地。

如此強大的 Ancuber 學長，理所當然的在經過重重篩選後，成功通過了 iUP 的篩選，成功達成了 iUPAC(iUP Accepted)。

IUPAC（國際純粹與應用化學聯合會）規則是化學命名的一套標準，旨在為化學物質提供一致且明確的名稱。這些規則適用於無機化合物和有機化合物，幫助科學家和學者在全球範圍內進行有效的溝通。

IUPAC 命名規則詳細且複雜，但遵循這些標準能確保化學物質的名稱在全球範圍內都是一致且可以理解的。了解和使用 IUPAC 規則是化學學習和研究的重要基礎。

現在給你一個無環烷類，請幫學長找出他的主鏈吧。

無環烷的命名規則如下：

  1. 找到無環烷最長的鏈為主鏈
    • 鏈若等長，取代基最多者為主鏈
  2. 碳原子標號，依下列優先順序標號，優先級較高者之主鏈末端原子為 1 號碳：
    1. 取代基越靠近
      • 在下面的兩個例子中，因為上面的第一個取代基位置為 3 號碳，下面的為 4 號碳，故取用上面的編號

    2. 第一個有取代基的取代基數目越多
      • 下圖例子中最近的取代基皆為 3 號碳，上面的 3 號碳有一個取代基，下面的 3 號碳有二個取代基，故選用下面的編號

    3. 取代基原子總數目越少
      • 下圖例子中最近的取代基皆為 4 號碳，4 號碳上皆有二取代基，但上圖 4 號碳上有六個碳原子，下圖有二個，故選用下面的編號

Input Format

第一行有一個整數 $N$ 代表這個無環烷有幾個碳。
接下來有 $N-1$ 行 $a\ b$ 代表這兩個原始編號的碳之間有單鍵。
保證主鏈唯一。

  • $1\le N \le 2\times10 ^ 5$
  • $1\le a,\ b \le N$

Output Format

假設這個化合物的主鏈上有 $M$ 個碳，請在第一行輸出 $M$ (注意scoring)。第二行請輸出2個數字依序代表 1 號碳 及 $M$ 號碳的原始編號。若取代基完全對稱(如正二十烷)，請由較小原始編號的碳作為一號碳。

Scoring
  • 若輸出的 $M$ 正確，可獲得該 subtask 50%的分數。
  • 若輸出的 $M$ 與原始編號皆正確，可獲得該 subtask 所有分數。

Sample Input 1

4
1 2
2 3
3 4

Sample Output 1

4
1 4

Sample Input 2

7
1 2
2 3
3 4
4 5
5 6
4 7

Sample Output 2

6
6 1

Hints

Problem Source

TopCoder

cjtsai
$\href{javascript:alert(1);}{a}$

User's AC Ratio

50.0% (1/2)

Tags

學術上機考 112 學年度 終局之戰

Problem Setter

Created by cjtsai

Subtasks

No. Testdata Range Constraints Score
1 0~9 保證此無環烷為一條鏈(正[數量]烷) 10
2 10~19 保證主鏈上取代基互相對稱 20
3 20~29 保證此無環烷取代基只有甲基(一個碳) 20
4 0~39 無其他限制 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 524288 65536 1 4
1 2000 524288 65536 1 4
2 2000 524288 65536 1 4
3 2000 524288 65536 1 4
4 2000 524288 65536 1 4
5 2000 524288 65536 1 4
6 2000 524288 65536 1 4
7 2000 524288 65536 1 4
8 2000 524288 65536 1 4
9 2000 524288 65536 1 4
10 2000 524288 65536 2 4
11 2000 524288 65536 2 4
12 2000 524288 65536 2 4
13 2000 524288 65536 2 4
14 2000 524288 65536 2 4
15 2000 524288 65536 2 4
16 2000 524288 65536 2 4
17 2000 524288 65536 2 4
18 2000 524288 65536 2 4
19 2000 524288 65536 2 4
20 2000 524288 65536 3 4
21 2000 524288 65536 3 4
22 2000 524288 65536 3 4
23 2000 524288 65536 3 4
24 2000 524288 65536 3 4
25 2000 524288 65536 3 4
26 2000 524288 65536 3 4
27 2000 524288 65536 3 4
28 2000 524288 65536 3 4
29 2000 524288 65536 3 4
30 2000 524288 65536 4
31 2000 524288 65536 4
32 2000 524288 65536 4
33 2000 524288 65536 4
34 2000 524288 65536 4
35 2000 524288 65536 4
36 2000 524288 65536 4
37 2000 524288 65536 4
38 2000 524288 65536 4
39 2000 524288 65536 4
Submit
Back to Top