codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

494A.md (1797B)


      1 Source: https://codeforces.com/problemset/problem/494/A
      2 
      3 A. Treasure
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Malek has recently found a treasure map. While he was looking for a treasure he found a locked door. There was a string *s* written on the door consisting of characters '(', ')' and '#'. Below there was a manual on how to open the door. After spending a long time Malek managed to decode the manual and found out that the goal is to replace each '#' with one or more ')' characters so that the final string becomes beautiful.
     22 
     23 Below there was also written that a string is called beautiful if for each *i* (1 ≤ *i* ≤ |*s*|) there are no more ')' characters than '(' characters among the first *i* characters of *s* and also the total number of '(' characters is equal to the total number of ')' characters.
     24 
     25 Help Malek open the door by telling him for each '#' character how many ')' characters he must replace it with.
     26 
     27 Input
     28 
     29 The first line of the input contains a string *s* (1 ≤ |*s*| ≤ 105). Each character of this string is one of the characters '(', ')' or '#'. It is guaranteed that *s* contains at least one '#' character.
     30 
     31 Output
     32 
     33 If there is no way of replacing '#' characters which leads to a beautiful string print  - 1. Otherwise for each character '#' print a separate line containing a positive integer, the number of ')' characters this character must be replaced with.
     34 
     35 If there are several possible answers, you may output any of them.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 (((#)((#)
     43 ```
     44 
     45 Output
     46 
     47 ```
     48 1  
     49 2
     50 ```
     51 
     52 Input
     53 
     54 ```
     55 ()((#((#(#()
     56 ```
     57 
     58 Output
     59 
     60 ```
     61 2  
     62 2  
     63 1
     64 ```
     65 
     66 Input
     67 
     68 ```
     69 #
     70 ```
     71 
     72 Output
     73 
     74 ```
     75 -1
     76 ```
     77 
     78 Input
     79 
     80 ```
     81 (#)
     82 ```
     83 
     84 Output
     85 
     86 ```
     87 -1
     88 ```
     89 
     90 Note
     91 
     92 |*s*| denotes the length of the string *s*.