0

Задача "Инопланетянин"

Во время эксперимента Накодиллы было случайно получено сообщение инопланетян , содержащее формулу вида A + B = C. Общественности стало интересно , какую же систему счисления использую инопланетяне. Так как внеземная цивилизация была достаточно развита, чтобы отправить межпланетное сообщение , Накодилла предположил, что основание системы счисления довольно мало. Требуется написать программу, которая находит минимальное основание системы счисления, при котором данное равенство выполняется.

ФОРМАТ ВВОДА : В единственной строке входных данных содержится три числа A , B и C. Числа состоят из цифр от 0 до 9 и заглавных латинских букв от A до Z.

ФОРМАТ ВЫВОДА : Требуется вывести единственное число - искомое основание системы счисления. Если такой системы счисления не существует , то вывести -1. Гарантируется, что ответ не превышает 36.

Пример ввода : 2 2 4 Пример вывода : 5

Пример ввода : 1A 2 20 Пример вывода : 12

2 ответа 2

2

Простейший вариант:

1) Пишем функцию преобразования системы счисления (см. учебник по математике или информатике) Формат:

int: changeBaseToDec(str: count,int: base_in){
//преобразование В десятичную
}

2) минимальное основание системы счисления (MIN_BASE) гарантированно больше, чем самая большая цифра, соответственно, пробегаемся циклом по примеру, выискивая максимальную "цифру".

3)

for(i=MIN_BASE; i<=36; i++){
if((changeBaseToDec(A,i)+changeBaseToDec(B,i))==changeBaseToDec(C,i)){
return i;
}
}
return -1;//Сюда мы придем, если не найдем ответа.

Собственно, все. Не уверен, правда, что самый оптимальный.

P.S. кто сказал, что у инопланетян цифры и буквы расположены в том же порядке, что и у нас? В этом случае придется заняться гораздо более масштабным перебором: вам придется перебрать все последовательности всех букв. Это, в нашем случае, 36! возможных вариантов = 3.72 × 10^41 Компу такое быстро перебрать слабо. По крайней мере, за время олимпиады.(на хорошем десктопном проце это будет 10^16 миллиардов лет) Так что вероятность контакта 1/36! =)

0
2

Переведём все строки-числа в массивы со значениями их цифр. Запишем их задом-наперед. Более короткие дополним нулями:

A: 1A -> [10, 1]
B: 2  -> [ 2, 0]
C: 20 -> [ 0, 2]

Пройдемся слева направо имитируя сложение в столбик. Рассмотрим сумму младших разрядов: если бы переноса не возникло, то A[0] + B[0] == C[0]. Это не так (10 + 2 != 0). Значит есть перенос и A[0] + B[0] == base + C[0]. Можно вычислить основание системы счисления.

В следующем разряде нужно учесть пришедший перенос: A[1] + B[1] + carry == C[1]. Равенство выполнено, проверять основание не надо.

Продвигаясь по разрядам выполняем сложение в столбик. При каждом переносе проверяем основание - все переносы должны дать один результат. Кроме этого основание должно быть больше всех цифр в во всех трёх числах.

def read_number(s):
    alphabet = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    return list(map(alphabet.index, reversed(s)))


def align(lists):
    max_length = max(map(len, lists))
    for l in lists:
        l.extend([0] * (max_length - len(l)))


def determine_base(a, b, c):
    align((a, b, c))
    max_digit = max(a + b + c)
    base = None
    carry = 0
    for ai, bi, ci in zip(a, b, c):
        s = ai + bi + carry
        if s < ci:
            return -1
        if s > ci:
            if base is None:
                base = s - ci
                if base <= max_digit:
                    return -1
            if s - ci != base:
                return -1
            carry = 1
        else:
            carry = 0
    if carry != 0:
        return -1
    if base is None:
        return max_digit + 1
    return base

    
def main():
    a, b, c = tuple(map(read_number, input().split()))
    print(determine_base(a, b, c))


main()

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.