Problem H. Honest mileage

Author:I. Oleynikov   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

Serge is an auto dealer. He brings cars from Japan and sells them in Russia. In contrast to a widespread practice of "rolling back" mileage to make a car look less used, Serge prefers a honest approach. He even drives his cars a little to get a "nice-looking" mileage numbers.

Serge says that mileage is "nice-looking" if digits located at corresponding positions on main and auxiliary car odometers are equal. The numbers on the main and auxiliary odometer written one below another look like this:

00015153 0
XXXX5121.0

Dot is the decimal separator on auxiliary odometer and does not take a place of a digit. "X" is a space filler, designating that there is no digit on this place.

Main odometer is incremented by one after each full kilometer since the moment when Serge starts driving. Serge may reset auxiliary odometer to zero at any time. Auxiliary odometer is incremented by 0.1 after each full hundred of meters since either the moment when Serge starts driving or last reset, whichever is later. Whenever any odometer reaches maximum value, it resets to zero upon next increment.

Your program must calculate a minimum distance that Serge needs to drive on his car to set car odometers to a nice-looking mileage. In the example above Serge needs to drive 35.5 km.

Input file format

The input file contains two strings, one per line. The first string contains nine digits and determines initial state of main odometer.

The second string contains four 'X' characters followed be four decimal digits, dot and another digit — the state of auxiliary odometer.

Output file format

Output file must contain a single exact floating point number — the distance that Serge must drive, measured in kilometers.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
000151530
XXXX5121.0
35.5

Explanation

Лемма 1: Для любого значения au на дополнительном одометре существует значение k1, такое что после проезда k1 км. значение на дополнительном одометре станет равно au вне зависимости от того значение, которое было на дополнительном одометре изначально.

Доказательство: сбросим дополнительный одометр в 0 и проедем au км. Значение на дополнительном одометре станет равно au, следовательно в данной постановке k1 = au

Следствие 1 первой леммы: Если требуется получить значение au на дополнительном одометре, проехав kp > k1 км, то первые kp − k1 км. следует сбрасывать одометр в 0, каждый 100 метров.

Следствие 2 первой леммы: Из начального значения 0 на дополнительном одометре получить значение au можно не ранее чем проехав k1 км. Это очевидно, так как если существует некое k3 < k1 км, то по предположению k1 − k3 > 0, а по первой лемме k1 = au, тогда получим au − k3 > 0, что возможно только если k3 число отрицательное.

Лемма 2: Для любого au ≥ init существует k2, что после k2 км от начального значения одометр получит значение au. Доказательство очевидно k2 = au − init

Лемма 3: Если au ≥ init, то k2 ≤ k1, иначе k2 > k1. Доказательство осуществляется простой подстановкой в формулы значений из леммы 1 и ее свойств, учитывая что все значения по условию больше, либо равны нулю.

Лемма 4: Дополнительный одометр не может достичь значения au за k3 км, такое что k2 < k3 < k1, если au ≥ init. Доказательство методом отпротивного, по аналогии с следствием 2 леммы 1. После подстановки получаем k3 = k2

Лемма 5: На последних пяти цифрах основного одометра получить значение am можно за am − initm км, если am ≥ initm. Или за 100000 − initm + am км. Если am ≤ initm. Доказательство очевидно. Следствие леммы 5: Каждое значение на последних пяти цифрах основного одометра можно повторять ровно через 100000 км.

Теорема 1: Значение am на последних пяти цифрах основного одометра и значение au = am10 на дополнительном при начальных значениях initm и init соответственно можно получить либо за max(k1,100000 − initm + am) км, либо за au − init км. Доказательство: очевидно следует из вышеперечисленных лемм.

Решение задачи: перебрать все возможные am на основном одометре, для каждого из них расчитать 2 варианта из Теоремы 1. Если k2 совпадет с am − initm10 то выбрать из этих вариантов минимум, иначе выбрать первый вариант Теоремы 1. Из всех подходящих вариантов для каждого am выбрать наименьший и вывести его.


0.079s 0.017s 13