codeforces-scrape

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

196A.md (1489B)


      1 Source: https://codeforces.com/problemset/problem/196/A
      2 
      3 A. Lexicographically Maximum Subsequence
      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 You've got string *s*, consisting of only lowercase English letters. Find its lexicographically maximum subsequence.
     22 
     23 We'll call a non-empty string *s*[*p*1*p*2... *p**k*] = *s**p*1*s**p*2... *s**p**k*(1 ≤ *p*1 < *p*2 < ... < *p**k* ≤ |*s*|) a subsequence of string *s* = *s*1*s*2... *s*|*s*|.
     24 
     25 String *x* = *x*1*x*2... *x*|*x*| is lexicographically larger than string *y* = *y*1*y*2... *y*|*y*|, if either |*x*| > |*y*| and *x*1 = *y*1, *x*2 = *y*2, ... , *x*|*y*| = *y*|*y*|, or exists such number *r* (*r* < |*x*|, *r* < |*y*|), that *x*1 = *y*1, *x*2 = *y*2, ... , *x**r* = *y**r* and *x**r* + 1 > *y**r* + 1. Characters in lines are compared like their ASCII codes.
     26 
     27 Input
     28 
     29 The single line contains a non-empty string *s*, consisting only of lowercase English letters. The string's length doesn't exceed 105.
     30 
     31 Output
     32 
     33 Print the lexicographically maximum subsequence of string *s*.
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 ababba
     41 ```
     42 
     43 Output
     44 
     45 ```
     46 bbba
     47 ```
     48 
     49 Input
     50 
     51 ```
     52 abbcbccacbbcbaaba
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 cccccbba
     59 ```
     60 
     61 Note
     62 
     63 Let's look at samples and see what the sought subsequences look like (they are marked with uppercase bold letters).
     64 
     65 The first sample: aBaBBA
     66 
     67 The second sample: abbCbCCaCbbCBaaBA