CW_2 - COMPRESSED WORDS-2
Helen has come up with a way to shorten the length of the messages send to their counterparts in the past. Helen considers only individual words, and uses the following rules to define a "shortened word":
- a single, lower-case letter is a compressed word
- (e1 e2 ... et n) where t and n are non-negative integers and ei is a compressed word.
You should observe that a compressed word of one character is the same as an uncompressed word. To uncompress the compressed word (e1 e2 ... et n) we uncompress each ei, concatenate those uncompressed words into a new word, and repeatedly concatenate that word n times. For example:
- a would be uncompressed as a,
- (a 3) would be uncompressed as aaa,
- (a (b c d 2) 3) would be uncompressed as abcdbcdabcdbcdabcdbcd.
Write a program to uncompress a compressed word.
Input
First line T, the number of test cases (=12). Next T lines contain correctly formed compressed words.
Output
For each case print in a new line the uncompressed word without spaces.
Constraints
0 < n <= 10000, 1 <= t <= 26
length of expressions will be less than 100, and the compressed worf will consist of latters (a-z), numbers and brackets.
Note: There may or may not be more than one space between brackets and letters or number. For example ( a ), (a3), ( a 3 ) are all correct expressions.
Example
Input: 3 a ( a 3 ) ( a ( b c d 2 ) 3 ) Output: a aaa abcdbcdabcdbcdabcdbcd
hide comments
Bhavik:
2014-04-08 20:42:44
@mitch: thank you for understanding my concerns. ok i got your point,i will certainly look into improving constraints for this problem with right problem statement also:)
|
|
Mitch Schwartz:
2014-04-08 20:31:25
@Bhavik: Ok, I understand that your somewhat harsh assessment of CW problem setter is more because of his unresponsiveness than because of the issues with the problem itself. I do thank you for being very responsive and understanding. It can be moved back to classical, but I would like to see it improved first, and we can discuss.
|
|
Bhavik:
2014-04-08 20:16:10
and for time limit i am not in the favour of building huge datasets just for not allowing 0.00s solution to exist.
|
|
Bhavik:
2014-04-08 20:11:32
@Mitch: i agree that i am wrong on that part since i just copied the wordings from CW...so i should have been careful with that...but as i said i am ready to accept my mistakes and rectify it for both as psetter and for users and as you mentioned my mistakes earlier i tried to
|
|
Mitch Schwartz:
2014-04-08 20:10:20
Regarding 0.00s: It is possible to e.g. increase size of test data and also increase time limit (so that slower solutions can still pass). I'm not sure how slow the solutions are that you wanted to allow, but a difference in >= 200x (the 1s time limit vs my 0.00s, should be at most 0.005s in order to get rounded that way) seems a lot to me. |
|
Mitch Schwartz:
2014-04-08 20:02:03
If you can't see that "(a)" is not a valid compressed word according to the definition, I think you should be most concerned about that.
|
|
Bhavik:
2014-04-08 19:43:04
@MITCH: i dont where i am wrong...i am giving attention to the problems that users are having with this question by clearing their doubts or vive-versa
|
|
Mitch Schwartz:
2014-04-08 19:37:12
From CW: "though it truly deserves to be in classical,but due to the ignorance of psetter all the efforts of users trying to do this is wasted:( i think spoj administrators should take away problem making rights from such people who don't care to make right problems or if psetter have some time issues they should atleast say so that we can look for problem after some time again.. "
|
|
Mitch Schwartz:
2014-04-08 19:28:58
Moved to tutorial. |
|
Mitch Schwartz:
2014-04-08 19:19:37
There is a definition of shortened/compressed word at the beginning of problem description. "(a)" is not in the language defined there. Adding mention of "regular expressions" does not fix this error. I got AC with a workaround, but this should be fixed.
|
Added by: | Bhavik |
Date: | 2014-04-08 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | CW |