Christmas digits
Tag(s):

## Algorithms, Dynamic Programming, Medium

Problem
Editorial
Analytics

Little Santa made a list of all the naughty children. He created a programming problem and he will give gift to only those naughty children who will solve that problem. The problem is:

Given three integers, $n, k, x$ (without leading zeros), you can insert at most k digits at any positions in n. You have to create the maximum number (without leading zeros) from n which is not greater than x.

All the children want gifts so they asked you to solve the problem for them.

Input format:
First line of input contains three integers, $n, k, x$ $(1 <= n <= x <= 10^{100000})$, $(0 <= k <= 100000)$.

Output format:
Print one integer, denoting the maximum number (without leading zeros) that can be created from n which is not greater than x after inserting at most k digits at any position in n.

SAMPLE INPUT
10 2 109

SAMPLE OUTPUT
109

Explanation

You have to insert at most 2 digits in number 10 to make it no larger than 109. Inserting 9 at the end is the way to get the best result. There are also other valid strategies, like not inserting digits at all or inserting 0 at second position, but they give smaller numbers.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

Christmas Circuits '16

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Graphs
• Algorithms > String Algorithms