Блокчейн (blockchain) переводится как «цепочка блоков». Это способ хранения данных, защищённый от подделки, используемый, в частности, криптовалютой биткоин.

Блокчейн действительно представляет собой последовательность блоков. Каждый блок представляет собой некоторую полезную информацию (в частности, в случае биткоина это список транзакций за определённый период времени — кто кому когда сколько денег передал), снабжённую случайным числом и некоторыми служебными данными, в том числе хэшем — числом, которое по определённой формуле зависит от остальной части блока и хэша предыдущего блока.

Хэш должен быть меньше определённого числа. При этом формула, по которой вычисляется хэш, устроена так, что невозможно получить достаточно маленький хэш иначе, чем перебирая различные значения случайного числа. Поэтому если злоумышленник решит подделать блокчейн (и, допустим, вставить в его середину блок с записью о том, что все люди передают ему все свои деньги), то ему придётся подобрать новое случайное число в новое поддельном блоке и всех последующих (ведь хэш каждого следующего блока зависит от хэша предыдущего), что потребует невозможно больших вычислительных мощностей.

Поэтому блокчейн в целом защищён от подобных атак.

Напишите программу, которая проводит проверку правильности хэшей в модельном блокчейне с простой хэш-функцией.

Блок bn с номером n включает полезную информацию mn, представленную натуральным числом, rn — случайное число от 0 до 255 и hn — хеш (целое число от 0 до 255). У каждого блока хэш вычисляется по формуле hn = 37×(mn+rn+hn-1) (по модулю 256), при вычислении хэша начального блока h0 вместо хэша предыдущего блока берётся ноль.

При этом каждый блок представлен одним числом bn = hn + rn×256 + mn×2562. При этом требуется, чтобы хэш hn был меньше 100.

Формат ввода
На первой строке вводится натуральное число N — количество блоков.
Далее следуют N чисел bn, каждое на отдельной строке.

Формат вывода
Следует вывести номер первого блока, у которого неправильный хэш (не меньше 100 или не совпадает с вычисленным по указанной в условии формуле), или -1, если все хэши в блокчейне правильные. Нумерация блоков идёт с нуля, т. е. они имеют номера от 0 до N-1.

напиши код на python

Информатика 10 класс Алгоритмы и структуры данных ключевые слова: блокчейн хэш проверка хэша криптовалюта биткоин Новый

Давайте разберем, как можно решить эту задачу шаг за шагом.

Для начала, нам нужно понять, как извлечь из числа bn все необходимые компоненты: mn, rn и hn.

1. mn можно получить, разделив число bn на 256² и взяв целую часть от деления:
• mn = bn // 256²
2. rn можно получить, разделив число bn на 256, взяв остаток от деления на 256 и целую часть:
• rn = (bn // 256) % 256
3. hn можно получить, взяв остаток от деления числа bn на 256:
• hn = bn % 256

Теперь, когда мы знаем, как извлечь все компоненты, давайте перейдем к проверке корректности хэшей.

1. Заведем переменную previous_hash, которая будет хранить хэш предыдущего блока. Для начального блока она равна 0.
2. Заведем цикл, который будет проходить по всем блокам:
• Для каждого блока извлекаем mn, rn и hn.
• Вычисляем ожидаемый хэш expected_hash по формуле: expected_hash = (37 * (mn + rn + previous_hash)) % 256.
• Проверяем два условия:
  • Если hn не совпадает с expected_hash, значит, хэш блока неверен.
  • Если hn не меньше 100, значит, хэш блока неверен.
• Если одно из условий выполняется, выводим номер блока и завершаем выполнение.
• Если оба условия не выполняются, обновляем previous_hash значением hn и продолжаем проверку следующего блока.
3. Если цикл завершился и не было найдено ни одного блока с неверным хэшем, выводим -1.

Теперь давайте напишем код, который реализует описанный алгоритм:

def check_blockchain(N, blocks):
    previous_hash = 0

    for i in range(N):
        bn = blocks[i]
        mn = bn // (256 ** 2)
        rn = (bn // 256) % 256
        hn = bn % 256

        expected_hash = (37 * (mn + rn + previous_hash)) % 256

        if hn != expected_hash or hn >= 100:
            return i

        previous_hash = hn

    return -1

# Пример использования:
N = int(input())
blocks = [int(input()) for _ in range(N)]
result = check_blockchain(N, blocks)
print(result)

Этот код читает количество блоков и сами блоки, затем проверяет каждый блок на корректность хэша и выводит номер первого блока с ошибкой или -1, если все блоки корректны.