Phép cuốn số

Submit solution
Points: 3 (partial)
Time limit: 1.0s
Memory limit: 98M
Author:
TICHPX
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Cho một số tự nhiên n nếu n có nhiều hơn 1 chữ số mà thỏa mãn chữ số đầu tiên và chữ số cuối cùng có tổng không vượt quá 9 thì có thể rút gọn lại bằng cách bỏ đi chữ số đầu và cộng nó vào chữ số cuối hoặc bỏ đi chữ số cuối rồi cộng vào chữ số đầu

Chẳng hạn 31425 thì có thể rút thành 8142 hoặc 1428

Nhiệm vụ của bạn là cho một số tự nhiên n không quá 1018 hãy tìm cách rút gọn tối đa số này thế nào để thu được số bé nhất

Input

Một số tự nhiên n không quá 1018

Output

Giá trị nhỏ nhất của n sau khi thực hiện các phép rút gọn

Ví dụ

Input

Copy
123456

Output

Copy
3459

Giải thích Xét số 123456, nếu lấy chữ số đầu cộng chữ số cuối là 1+6≤9 có thể rút gọn thành 72345 hoặc 23457 chúng ta chọn cách rút gọn thứ 2 và tiếp tục như sau

123456−>23457−>3459

tichpx

Comments