c654: 秒速五公分
標籤 :
通過比率 : 79% (11 人 / 14 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2018-09-16 23:02

內容

在一個月黑風高的夜晚,名為「粄條高級中學監獄」的囚犯們正為了隔天的重要日子做準備

他們正在做的事情並不是利用回溯取模計算如何搶到一個好位子以避免槍決,而是為了一個名為「段考」的事情認真念書,以躲避暑假被暑修的命運

只不過讀書過程實在是太無聊了,因此某個監獄裡面的人決定來玩一個遊戲...

 

所有犯人圍成一個圓環,環長X,圓環位置編號從0到N-1

決定編號之後,就是決定方向跟速度的時間了,這時候每個人都要用一袋僅有編號0和1的球來決定自己要逆時針跑還是順時針跑,然後所有人再討論出一個速度每秒V單位好讓大家遵守

接著他們邀請你這個典獄長玩遊戲,你的任務就是計算他們一秒後任意相鄰兩人相距的最大值

 

阿阿對了,為了增加遊戲難度,行進中任兩位犯人相遇後,彼此都必須要轉向

 

 

 

 

輸入說明

第一行數字T代表有T筆測資

接下來T筆測資第一行輸入N,X,V,分別代表N個人 , 環長X , 速度V

測資第2行到第N+1行,第i行輸入兩個數字C_i 跟 D,分別代表這些犯人所在的位置跟移動方向

D=0代表順時針,D=1代表逆時針

測資範圍:

第00筆測資:T=102,1≤X,V≤103

第01筆測資:T=5,1≤X,V≤105

第02筆測資:T=3,1≤X,V≤106

第03測資:T=3*104,1≤X≤100,V=106

第04測資:T=102,1≤X≤106,V=102

 

對於所有測資 :1≤N≤min(106,X)

輸出說明

求一秒後任意相鄰兩人相距的最大值

範例輸入
1
3 15 5
0 0
5 0
14 1
範例輸出
10
測資資訊:
記憶體限制: 64 MB
不公開 測資點#0 (20%): 0.2s , <1M
不公開 測資點#1 (20%): 0.2s , <1M
不公開 測資點#2 (20%): 0.2s , <10M
不公開 測資點#3 (20%): 0.2s , <10M
不公開 測資點#4 (20%): 0.2s , <10M
提示 :

第一筆測資:

 

 

位置 方向
0 0
5 0
14 1

 

一秒後

第二和第三人會在9.5的位置碰面 然後雙方調頭 最後的位置如下

 

位置 方向
5 0
9 1
10 0

 

最大相差=10 第一人和第三人的差距

標籤:
出處:
107學年度板橋高中校內資訊學科能力競賽310573sao [編輯:
snail (蝸牛)
]


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