Проверка блокчейна

Ограничение времени 1 секунда
Ограничение памяти 64Mb
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt

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

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

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

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

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

Миниатюры

 

1

Блин ребята помогите плиз, срочно надо. Спасибо заранее

0

mimimimimimimim,
It's easy
If i help you, not forget press but 'Thanks'.

17

Thank!!!

1

Сообщение от CyberGame mimimimimimimim, It's easy Python 1 2 3 4 5 6 7 8 9 10 11 12 n = int(input()) p = 0 bad = - 1 for i in range(n):     b = int(input())     h, r, m = b % 256, (b // 256) % 256, b // 256 ** 2     t = ((m + r + p) * 37) % 256     if t != h or h >= 100:         bad = i         break     p = h print(bad) If i help you, not forget press but 'Thanks'.

Привет.
А не мог бы пояснить как ты из условия это взял?

3

Смотри, делишь всю первую формулу на 256. Тогда слева будет b % 256, а справа выражение r * 256 + m * 256 ** 2 делится на 256, но также справа имеется член h, значит остаток от деления правой части на 256 равен h. Значит h == b % 256. Теперь заметим, что r + m * 256 == b // 256. Если теперь найти остаток от деления данного выражения на 256, то он (остаток) будет равен b // 256 % 256, т.к m * 256 делится на 256, а r - свободный член, являющийся остатком.

Добавлено через 1 минуту
Спасибо, очень помогли!

0

вопрос, а почему мы именно делим на 256. в условии не написано ничего про это и сказано про рандом? за пояснение и за код спасибо

0

Я кажется понял, это работает как с разрядами десятков:
bn = hn + rn * 256 + mn * 256 ** 2, мы сдвигаем каждый элемент на разряд.
например (пример в нашей любимой 10ричной системе исчисления):
n = first + second * 10 + third * (10 ** 2)
n = str(first) + str(second) + str(third) т.е. и в первом и во втором случае они идут друг за другом. Поэтому мы и можем вытаскивать по разряду из блока

2

Добавлено через 21 секунду
Привет! Здорово объяснил, спасибо!
Был один момент, на котором я затупил, объясню для тех, кто тоже не понял:
В решении мы тянем элементы из разрядов в обратном порядке, потому что нам и в задании их дали в обратном порядке.

То есть, 375 = 3 * 100 + 7 * 10 + 5, а не 5 + 7 * 10 + 3 * 100, как нам дали в задании.

1