Предскажите номер с добавлением номеров

Question

Кто-то спросил меня об этом алгоритмическом вопросе и, как обычно, я не смог ответить на этот вопрос. :) Скажем, у вас есть один номер (назовем его)

504 

В следующий раз, вы видите его, вы удалите последнюю цифру числа. Будет (называть его b)

50 

В следующий раз, вы видите, вы удаляете последнюю цифру числа. Будет (назовем его c)

5 

Теперь добавьте все три числа (a + b + c). Это будет:

504 + 50 + 5 = 559 

Хорошо, к настоящему времени вы, возможно, хорошо поняли постановку проблемы.

Вопрос: При добавлении трех цифр a + b + c вам (в данном случае 559), как вы можете вернуться к исходному номеру (в данном случае 504)? Все решения будут оценены.

Answer 1

Предположим, номер, который вы начали, выглядит как xyz. То есть его последняя (десятичная) цифра равна z, ее предпоследней цифрой является y, а остальное x. В вашем примере, если вы начали с 504, тогда x = 5, y = 0, z = 4. Значение вашего исходного номера равно 100x + 10y + z.

Число, в котором вы закончите, представляет собой сумму (100x + 10y + z), (10x + y) и x. Это 111x + 11y + z.

Обратите внимание, что наши ограничения заключались в том, что 0≤y≤9 и 0≤z≤9. Даже с их наибольшими значениями мы имеем 11y + z ≤ 11 (9) + 9 < 111. Таким образом, мы можем инвертировать преобразование: вытащить наибольшее кратное 111, затем вытащить наибольшее кратное 11 из оставшихся, а затем то, что осталось.

def transform(n): 
    return n + (n/10) + (n/100) 

def invert(m): 
    [x, y, z] = [m/111, (m%111)/11, (m%111)%11] 
    return 100*x + 10*y + z 

assert transform(504) == 559 
assert invert(559) == 504 

(Попробуйте выше, в оболочке Python Обратите внимание, что это работает, даже если й не одноразрядный номер:.. transform(12345) дает 13702, и invert(13702) дает 12345, как и ожидался)

---

Редактировать: Альтернативное решение, основанное на идее в Paul Hankin's answer (пожалуйста, подтвердите это) с использованием m*100/111 в качестве отправной точки. Вы можете использовать (потолок) это значение как грубый ответ и попробуйте добавить 1 и 2, чтобы получить точный ответ, но вы также можете прекомпотировать «смещение», необходимое из грубого ответа.

# Precomputation, to populate the "offset" dictionary 
def sane_mod(a, m): return ((a % m) + m) % m 
offset = {} 
for y in range(10): 
    for z in range(10): 
     add = 10*y + 11*z 
     offset[sane_mod(-add, 111)] = add 

# Actual function 
def invert2(m): 
    rough = m * 100 
    return (rough + offset[rough % 111])/111 
assert invert2(559) == 504 

Answer 2

a + b + c является a + a // 10 + a // 100 (где // обозначает округление). Это где-то между * 111/100 - 1.89 и * 111/100. (1,89, потому что максимальная доля, отбрасываемая из // 10, равна 0,9, а максимальная доля, отбрасываемая из // 100, равна 0,99 и 1,89 = 0,9 + 0,99).

Таким образом, учитывая а + Ь + с, мы ищем целое такое, что:

a * 111/100 - 1.89 <= a + b + c <= a * 111/100 
a - 2.0979 <= (a + b + c) * 100/111 <= a 

Итак, пусть х = CEIL ((A + B + C) * 100/111), и одним из х, х + 1 или х + 2 должно быть решение.