eolymp
bolt
Try our new interface for solving problems
Məsələlər

Автомобiльнi номери

Автомобiльнi номери

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Козак Вус та Ледi, їдучи автомобiлем, обожнюють грати в одну гру. Вони дивляться на число, записане на номерi автомобiля, та хочуть зробити, щоб воно дiлилося нацiло на 9 за мiнiмальну кiлькiсть операцiй.

Операцiя — це додати або вiдняти одиницю до будь-якої цифри. Звичайно цифри завжди мають бути вiд 0 до 9. Тобто, не можна вiднiмати вiд 0 та додати до 9.

Друзям ця гра швидко набридла, тому вони вирiшили ускладнити її, доповнивши її ще одним правилом — серед усiх можливих рiшень, потрiбно знайти лексикографiчно мiнiмальний.

В Потоколяндiї автомобiльнi номери досить великi, тому грати в цю гру складно, тому компанiяпросить вас написати програму, яка буде грати за них.

Giriş verilənləri

Єдиний рядок мiстить цифровий рядок s (1 ≤ |s| ≤ 1 000 000), де |s| — довжина рядка. Звернiть увагу, що рядок може починатись з «0».

Çıxış verilənləri

В єдиному рядку виведiть вiдповiдь на задачу.

####Примiтка

У першому прикладi з 23 можна зробити 00 за 5 операцiй, або 27 за 4 операцiї, що є вигiднiшим.

У другому прикладi з 228 можна зробити 279 за 6 операцiй, або 018 за 3 операцiї, що є вигiднiшим.

У третьому прикладi 0234 одразу нацiло дiлиться на 9, тому i є вiдповiддю.

Nümunə

Giriş verilənləri #1
23
Çıxış verilənləri #1
27
Giriş verilənləri #2
228
Çıxış verilənləri #2
018
Giriş verilənləri #3
0234
Çıxış verilənləri #3
0234
Mənbə 2019-2020 ACM-ICPC, SEERC, 1/4 фiналу, Днiпро, Київ, Львiв, Миколаїв, Тернопiль, Харкiв, 14 вересня 2019