Problem : 308 - p&q的邂逅

Problem Statistics

Solved Member: 55　　Submission: 108　　User Tried: 57

Statement:

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

Input:Output:

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

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

Sample Input:Sample Output:

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

2
6

Source:

101北市賽

Problem Setter

bigelephant29

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1	1000ms	65536kb	20
2	1000ms	65536kb	20
3	1000ms	65536kb	20
4	1000ms	65536kb	20
5	1000ms	65536kb	20