codeforces-scrape

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

1146B.md (1441B)


      1 Source: https://codeforces.com/problemset/problem/1146/B
      2 
      3 B. Hate "A"
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Bob has a string $s$ consisting of lowercase English letters. He defines $s'$ to be the string after removing all "a" characters from $s$ (keeping all other characters in the same order). He then generates a new string $t$ by concatenating $s$ and $s'$. In other words, $t=s+s'$ (look at notes for an example).
     22 
     23 You are given a string $t$. Your task is to find some $s$ that Bob could have used to generate $t$. It can be shown that if an answer exists, it will be unique.
     24 
     25 Input
     26 
     27 The first line of input contains a string $t$ ($1 \leq |t| \leq 10^5$) consisting of lowercase English letters.
     28 
     29 Output
     30 
     31 Print a string $s$ that could have generated $t$. It can be shown if an answer exists, it is unique. If no string exists, print ":(" (without double quotes, there is no space between the characters).
     32 
     33 Examples
     34 
     35 Input
     36 
     37 ```
     38 aaaaa
     39 ```
     40 
     41 Output
     42 
     43 ```
     44 aaaaa
     45 ```
     46 
     47 Input
     48 
     49 ```
     50 aacaababc
     51 ```
     52 
     53 Output
     54 
     55 ```
     56 :(
     57 ```
     58 
     59 Input
     60 
     61 ```
     62 ababacacbbcc
     63 ```
     64 
     65 Output
     66 
     67 ```
     68 ababacac
     69 ```
     70 
     71 Input
     72 
     73 ```
     74 baba
     75 ```
     76 
     77 Output
     78 
     79 ```
     80 :(
     81 ```
     82 
     83 Note
     84 
     85 In the first example, we have $s = $ "aaaaa", and $s' = $ "".
     86 
     87 In the second example, no such $s$ can work that will generate the given $t$.
     88 
     89 In the third example, we have $s = $ "ababacac", and $s' = $ "bbcc", and $t = s + s' = $ "ababacacbbcc".