a565. 2.p&q的邂逅
標籤 : stack
通過比率 : 1967人/2438人 ( 81% ) [非即時]
評分方式:
Tolerant

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

內容

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

輸入說明

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

輸出說明

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

範例輸入 #1
2
..p..p.p...q.q.
.p...qq..p.pq.p..q.qpp..qpq
範例輸出 #1
2
6
測資資訊:
記憶體限制: 512 MB
提示 :

說明

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

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

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

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

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
23687 fire5386 (becaidorz) a565
2304 2020-12-08 22:25
16570 freedom50199 ... (帥氣魔方生) a565
2390 2019-01-15 15:11
42805 asnewchien@g ... (david) a565
41 2024-10-04 14:11
41566 toseanlin@gm ... (Dr. SeanXD) a565
C++詳解
180 2024-08-07 20:31
39478 Chaoray (巧克力內餡貢丸) a565
記得優化IO
251 2024-02-26 14:55