codeforces-scrape

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

169B.md (1408B)


      1 Source: https://codeforces.com/problemset/problem/169/B
      2 
      3 B. Replacing Digits
      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 are given an integer *a* that consists of *n* digits. You are also given a sequence of digits *s* of length *m*. The digit in position *j* (1 ≤ *j* ≤ *m*) of sequence *s* means that you can choose an arbitrary position *i* (1 ≤ *i* ≤ *n*) in *a* and replace the digit in the chosen position *i* with *s**j*. Each element in the sequence *s* can participate in no more than one replacing operation.
     22 
     23 Your task is to perform such sequence of replacements, that the given number *a* gets maximum value. You are allowed to use not all elements from *s*.
     24 
     25 Input
     26 
     27 The first line contains positive integer *a*. Its length *n* is positive and doesn't exceed 105. The second line contains sequence of digits *s*. Its length *m* is positive and doesn't exceed 105. The digits in the sequence *s* are written consecutively without any separators.
     28 
     29 The given number *a* doesn't contain leading zeroes.
     30 
     31 Output
     32 
     33 Print the maximum value that can be obtained from *a* after a series of replacements. You are allowed to use not all elements from *s*. The printed number shouldn't contain any leading zeroes.
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 1024  
     41 010
     42 ```
     43 
     44 Output
     45 
     46 ```
     47 1124
     48 ```
     49 
     50 Input
     51 
     52 ```
     53 987  
     54 1234567
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 987
     61 ```