a565: 2.p&q的邂逅
Tags : stack
Accepted rate : 477人/624人 ( 76% ) [非即時]
評分方式:
Tolerant

最近更新 : 2012-11-12 22:48

Content

 「眾裡尋他(她)千百度,驀然回首,那人卻在燈火闌珊處。」如果讓你當月下老人,你能夠把看對眼的兩個有緣人盡量湊成一對,不要讓遺憾發生嗎?我們將給你一份等待配對的名單,其中「p」代表男生,「q」代表女生,配對的條件很簡單,只要p跟q的位置是「面對面」(亦即「pq」),就代表彼此相看兩不厭,可被視為一對,其他的狀態,如背對背(亦即「qp」、「pp」或「qq」),則不能配對成功。成功配對後,該pq對就被移出等候配對名單,讓其他的p與q可以有機會繼續配對。你的目標就是盡量找出所有可以配成對的p與q。能否圓滿達成任務,就靠你智慧的安排!願天下有情人終成眷屬!

Input

 第一行是一個整數n,代表有n組(行)的等候配對名單。每一組名單中,p與q之間可能相鄰或者以「.」分隔,「.」的數量多寡不定,但不影響p與q的配對(距離不是問題!),亦即除了pq以外,p.q、p....q等都可以配成對。

Output

輸出能成功配成對的最大總數,輸出的每一行對應一組等候名單。

Sample Input
2
..p..p.p...q.q.
.p...qq..p.pq.p..q.qpp..qpq
Sample Output
2
6
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 1.0s , <50M
Hint :

說明

ABCDEFGHIJKLMNO
..p..p.p...q.q.  //為標示方便,故以全形表示
H位置的p與在L位置的q可以配對成功,當他們被移開後,在F位置的p又可以跟在N位置的q配對成功,最後剩下載C位置的p無法找到可配對的q。依此類推,第二組配對名單中,用底線標記起來的部分,就是最後仍無法配對成功的pq

 .p...qq..p.pq.p..q.qpp..qpq

原題並無長度限制,此處約定長度小於等於107
測資自己出的,有錯請提出。

Tags:
stack
出處:
101學年度台北市資訊學科能力競賽 [管理者:
eddy841021 (C++?)
]


ID User Problem Subject Hit Post Date
16570
freedom501999@g... (帥氣魔方生)
a565
C的
161 2019-01-15 15:11
16537 a565
想法
118 2019-01-11 23:37
16357
inthewing (Hsu)
a565
Avoid TLE in Python
130 2018-12-23 01:34
13619
a0970580085@gma... (不會寫程式)
a565
241 2018-03-29 21:20