b316. 紅圓茵可的消失
Tags :
Accepted rate : 19人/29人 ( 66% ) [非即時]
評分方式:
Tolerant

最近更新 : 2014-09-27 02:11

Content
「哇!我終於解出來啦!咦?茵可呢?」剛解完K大數字差的你,在茵可家到處尋找,卻始終不見紅圓茵可的身影。
四處打聽之下,得知茵可前往神秘之山-「板擦山」修練神秘的魔法去了。板擦山本身有天然的結界,只有法力高強的魔法師才有辦法進入山中。「這下子我該怎麼找到茵可呢?」你苦思著,「想找茵可嗎?我可以告訴你怎麼找到茵可!」似乎是剛好路過的長頸鹿這麼說道。
板擦山的山腳下有好幾間便利商店,這些便利商店剛好開在結界外,茵可每天都會到山下的其中一間購買民生用品,而且到哪家便利商店是可以預測的。板擦山上有N個點,每個點有各自的編號,越高的點編號越小,點跟點之間有道路連接,茵可所在的山頂為編號0的點,便利商店也是其中的一個點。茵可每天會由山頂出發,經過一些點後到山下的便利商店買東西。當茵可走到一個點x後,他會先走跟x有連接的點中,編號比x大(當然要往山下走阿)的點中,編號最小的那一個。而下一次又到x時就走第二小的,直到編號比x大的點都走過一次,就會回到最小的點繼續走。(假設 3號點連到 1,4,5,第一次到3時,茵可會走向4。下一次到3時,茵可會走向5。再下一次到3時,茵可會走向4。)若一個點沒有連到編號比它大的點,則該點為便利商店。
你從長頸鹿手中的到了板擦山的地圖,你就可以預測茵可在第K天時會走到哪一家便利商店了!

Input
第一行有兩個正整數N,M,K,表示有N個點(編號0~N-1)、M條邊(M<=N*(N-1)/2)及詢問第K天茵可會到哪個點。
接下來M行每行有兩個整數a,b表示a跟b間有一條邊(保證同樣兩個點間只會有一條邊)。

測資
1. N<=10,K<=100
2. N<=10,K<=100
3. N<=1000,K<=1000
4. N<=1000,K<=1000000000,整張圖為一棵樹
5. N<=1000,K<=1000000000

Output
輸出第K天時茵可會走到哪個點。

Sample Input #1
5 6 4
0 1
0 2
1 2
2 3
0 4
1 4
Sample Output #1
4
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 1.0s , <1M
Hint :
範例測資
第一天 0→1→2→3
第二天 0→2→3
第三天 0→4
第四天 0→1→4
 
 
2014/9/27 測資加強OAO 
Tags:
出處:
103學年度板橋高中校內資訊學科能力競賽(五) [管理者: snail (蝸牛) ]

Status Forum 排行

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