CF629C Famil Door and Brackets

As Famil Door’s birthday is coming, some of his friends (like Gabi) decided to buy a present for him. His friends are going to buy a string consisted of round brackets since Famil Door loves string of brackets of length $ n $ more than any other strings! The sequence of round brackets is called valid if and only if: 1. the total number of opening brackets is equal to the total number of closing brackets; 2. for any prefix of the sequence, the number of opening brackets is greater or equal than the number of closing brackets. Gabi bought a string $ s $ of length $ m $ ( $ m

N/A

N/A

In the first sample there are four different valid pairs: 1. $ p= $ "(", $ q= $ "))" 2. $ p= $ "()", $ q= $ ")" 3. $ p= $ "", $ q= $ "())" 4. $ p= $ "", $ q= $ ")()" In the second sample the only way to obtain a desired string is choose empty $ p $ and $ q $ . In the third sample there is no way to get a valid sequence of brackets.