Question

Пусть задано шестнадцатеричное число. Рассмотрим все шестнадцатеричные числа, которые можно получить из заданного перестановками цифр (при этом перестановки, в которых на первом месте оказывается 0, из рассмотрения исключаются, а исходное число, наоборот, включается). Для каждого такого числа считаем остаток от его деления на 5. Требуется найти среднее арифметическое таких остатков всех рассматриваемых чисел. Формат ввода Входные данные содержат одно шестнадцатеричное число, состоящее из не более чем 20 знаков. Цифры, большие 9, обозначаются строчными латинскими буквами от ‘a’ до ‘z’. Гарантируется, что первой цифрой числа не является 0. Формат вывода Выведите среднее арифметическое остатков от деления всех корректных (то есть не имеющих ведущих нулей) чисел, образованных перестановками цифр в данном числе, от деления на 5, с точностью не хуже 10−9. Пример 1ВводВывод222 1Пример 2ВводВыводaaa 0

Answer 1

Решение задачи будет гораздо проще, если заметить, что остаток от деления шестнадцатеричного числа на 5 совпадает с остатком от деления на 5 его суммы цифр.

Действительно, доказываем по индукции:

• Для числа из одной цифры это тривиально: число из одной цифры совпадает со своей суммой цифр.
• Переход: пусть число из k цифр ...xyz дает такой же остаток при делении на 5, что и сумма цифр ... + x + y + z. Покажем, что число из (k + 1) цифры ...xyzt дает такой же остаток, что и сумма цифр ... + x + y + z + t: ...xyzt = 16 * ...xyz + t = 15 * ...xyz + (...xyz + t). Первое слагаемое делится на 5, второе по предположению дает такой же остаток, что и (... + x + y + z) + t, что и требовалось.

У любой перестановки сумма цифр такая же, так что и остатки от деления на 5 совпадают. Так что осталось найти сумму цифр исходного числа и найти остаток от деления её на 5, это и будет ответом.

Python 3:

digits = "0123456789abcdef"

n = input()

s = sum(digits.index(digit) for digit in n)

print(s % 5)

Answer 2

Для решения этой задачи, следует выполнить следующие шаги:

1. Сгенерировать все перестановки заданного шестнадцатеричного числа.
2. Исключить перестановки, в которых на первом месте оказывается 0.
3. Перевести каждое полученное число из шестнадцатеричной системы в десятичную.
4. Найти остаток от деления каждого полученного числа на 5.
5. Найти среднее арифметическое полученных остатков.

Давайте разберемся с каждым шагом по отдельности:

1. Сгенерировать все перестановки заданного шестнадцатеричного числа. Для генерации перестановок, можно использовать рекурсивную функцию, которая будет менять местами цифры на разных позициях.

2. Исключить перестановки, в которых на первом месте оказывается 0. После получения каждой перестановки, мы проверяем, что первый символ не является '0'.

3. Перевести каждое полученное число из шестнадцатеричной системы в десятичную. Для перевода из шестнадцатеричной системы в десятичную, можно воспользоваться стандартными функциями языка программирования.

4. Найти остаток от деления каждого полученного числа на 5.

5. Найти среднее арифметическое полученных остатков.

Давайте реализуем алгоритм на Python:

pythonCopy code
from itertools import permutations

def hex_to_decimal(hex_str):
    return int(hex_str, 16)

def calculate_average_remainder(hex_num):
    valid_numbers = set()
    total_remainder = 0

    # Генерируем все перестановки числа
    for perm in permutations(hex_num):
        perm_num = ''.join(perm)

        # Исключаем перестановки, в которых первый символ '0'
        if perm_num[0] != '0':
            valid_numbers.add(perm_num)
    
    if hex_num in valid_numbers:
        valid_numbers.remove(hex_num)

    # Переводим из шестнадцатеричной системы в десятичную и считаем остатки от деления на 5
    for num in valid_numbers:
        decimal_num = hex_to_decimal(num)
        total_remainder += decimal_num % 5

    # Находим среднее арифметическое
    average_remainder = total_remainder / len(valid_numbers)

    return average_remainder

# Ввод шестнадцатеричного числа
hex_num = input().strip()

# Выводим результат с точностью не хуже 10^(-9)
print("{:.9f}".format(calculate_average_remainder(hex_num)))

Примеры использования:

1. Ввод: 222, Вывод: 1
2. Ввод: aaa, Вывод: 0