d049: 6.排隊
標籤 : 鏈結串列 陣列
通過比率 : 3人/4人 ( 75% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-03-10 15:03

內容

原本有 N 個編號為 1 到 N 號的人排成一列,因為一場大地震大家四處去避難,地震結束之後又重新回來排隊,這時候排隊的順序已經不是原本從 1 到 N 的順序,而是依照回來之後的順序來排隊。

為了怕再次地震導致隊伍又重新排過,所以主辦單位請每個人記下自己前、後一位的編號,並將這個資料傳給附近的工作人員。由於每個人都不知道自己是第幾位,身為主辦單位的你,可否依照每個人前後一位的編號而還原出整個隊伍的排列。

輸入說明

輸入資料第一行有一個正整數 N (1<=N<=200000),代表這個隊伍總共有多少人(編號從 1 到 N)。

接下來有 N-1 行資料,每行有兩個正整數 A、B,代表A號排在B號的前面。

輸出說明

由於隊伍非常的長,所以要全部印完資料也會非常的長,因此只要輸出最後一位的H值即可。這邊H值的計算方式如下:

  1. 第一位的H值為他自己的編號除以997的餘數,即 H1=K1%997,其中 K1 是第一位的編號。
  2. 第二位以後的H值為前一位的H值乘上7倍加上自己的編號,最後再取除以997的餘數,即 Hi=(Hi-1*7+Ki)%997

以下面的範例1來說,隊伍的順序是1 2,H1=1%997=1,H2=(1*7+2)%997=9,故答案為9。
而下面的範例2,隊伍的順序是3 2 1,H1=3%997=3,H2=(3*7+2)%997=23,H3=(23*7+1)%997=162,故答案為162。

範例輸入 #1
2
1 2
範例輸出 #1
9
範例輸入 #2
3
3 2
2 1
範例輸出 #2
162
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1K
公開 測資點#3 (10%): 1.0s , <1K
公開 測資點#4 (10%): 1.0s , <1K
公開 測資點#5 (10%): 1.0s , <1K
公開 測資點#6 (10%): 1.0s , <1M
公開 測資點#7 (10%): 1.0s , <1M
公開 測資點#8 (10%): 1.0s , <10M
公開 測資點#9 (10%): 1.0s , <10M
提示 :
標籤:
鏈結串列 陣列
出處:
中女108 [管理者:
sagit (sagit)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」