e796: p3. 站牌廣告
Tags :
Accepted rate : 27人/27人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-01-01 14:00

Content

2019TOI1214 新手同好會 3. 站牌廣告 (BusStop)  {試題連結}

 問題敘述

為因應全球暖化,政府近年來提倡大眾運輸以減少交通工具所產生的碳排放量,而公車站牌所帶來的人流也可以為廣告看板增加曝光度!各廠商都想在最多人經過的站牌擺放自家的廣告,政府看準了這項商機,為了增加國庫收入以替人民謀福祉,決定依據站牌人流的多寡來制定廣告價格的高低以獲取最大的效益。 假設公車路線只有一條,公車會來回行駛。去程從站牌 1 經過站牌 2,依續到最後一站 B; 回程從站牌 B 經過站牌 (B-1),依續到站牌 1。目前已統計出乘客之上下車站牌,請你幫忙統計經過各站牌之人流數量,找出最多與最少人經過之站牌。

範例 1 圖示如下 (輸入、輸出格式請見下頁範例 1):

最少人流車站為(1) 號站牌 ( 0 人經過 ),最多為(5) 號站牌 ( 3 人經過 )。

 

 評分說明 此題目測資分成三組,每組測資有多筆測試資料,需答對該組所有測試資料才能獲得該 組分數,各組詳細限制如下。

子任務1 分數 50額外輸入限制乘客路線為單一方向 (Y > X),且最多與最少人流之站牌皆僅有一個。
子任務2 分數 30 乘客路線可能為雙向,且最多與最少人流之站牌皆僅有一個。
子任務3 分數 20 無特別限制。

Input

第一行輸入兩個正整數,第一個數 B (2 ≤ B ≤ 1000) 代表公車共經過幾個公車站牌(站牌 編號為 1, 2, 3, …, B);第二個數 P (1 ≤ P ≤ 1000) 則表示共有多少人要搭乘此公車。接下來共 輸入 P 行,每行輸入兩個正整數,以空白隔開,表示該位乘客的上車站牌 X 與下車站牌 Y ( 1 ≤ X,Y ≤ B,X<>Y)。

 

Output

共輸出兩個正整數,以一個空白區隔,第一個正整數 N (1 ≤ N ≤ B) 代表最少人流之公車 站牌(若有多個則輸出編號最小者),第二個正整數 M (1 ≤ M ≤ B)則代表最多人流之公車站牌 (若有多個則輸出編號最大者)。

 

Sample Input #1
8 3
2 7
5 3
5 8
Sample Output #1
1 5
Sample Input #2
10 9
1 5
10 5
4 2
8 10
4 5
7 10
2 4
10 8
8 9
Sample Output #2
1 9
Sample Input #3
1000 2
1 1000
1 1000
Sample Output #3
1 1000
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (5%): 1.0s , <1M
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1M
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1K
公開 測資點#5 (5%): 1.0s , <1M
公開 測資點#6 (5%): 1.0s , <1M
公開 測資點#7 (5%): 1.0s , <1M
公開 測資點#8 (5%): 1.0s , <1M
公開 測資點#9 (5%): 1.0s , <1M
公開 測資點#10 (5%): 1.0s , <1M
公開 測資點#11 (5%): 1.0s , <1M
公開 測資點#12 (5%): 1.0s , <1M
公開 測資點#13 (5%): 1.0s , <1M
公開 測資點#14 (5%): 1.0s , <1M
公開 測資點#15 (5%): 1.0s , <1M
公開 測資點#16 (5%): 1.0s , <1M
公開 測資點#17 (5%): 1.0s , <1M
公開 測資點#18 (5%): 1.0s , <1M
公開 測資點#19 (5%): 1.0s , <1M
Hint :
Tags:
出處:
2019年12月TOI新手同好會 [管理者:
p3a_owhj (阿普二信)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」