Попалась мне интересная задачка:
В соревнованиях по парусному спорту участвуют 226 спортсменов. Специальный прибор фиксирует прохождение дистанции каждой яхтой, записывая номер яхты цепочкой из нулей и единиц минимальной длины, одинаковой для каждого спортсмена. После прохождения половины дистанции некоторой частью участников регаты прибор записал 163 байт информации.
Сколько участников регаты ещё не прошли половину дистанции?
Попробуем разобраться!
Количество участников, не прошедших половину курса, можно найти, вычтя из общего количества участников количество участников, прошедших половину курса. Чтобы найти количество участников, прошедших половину дистанции, нам нужно знать размер каждой записи.
Поскольку каждая лодка записывается с помощью цепочки нулей и единиц минимальной длины, это означает, что каждая лодка записывается с помощью минимального количества битов, необходимых для представления номера лодки. Например, если имеется только 2 лодки, каждая лодка может быть записана с помощью 1 бита, поскольку 2 может быть представлено как 10 в двоичном формате. Если лодок 3, то каждая лодка может быть записана с помощью 2 битов, так как 3 может быть представлено как 11 в двоичном формате.
Учитывая, что существует 226 лодок, количество битов, необходимых для представления каждой лодки, равно log2(226) = log2(2^8 * 3^2 * 19) = 8 + 2 + 4 = 14 битов. Это означает, что для записи каждой лодки используется 14 бит. Таким образом, каждая запись имеет размер 14 бит.
Разделив общее количество записанных битов на размер каждой записи, получим 163 * 8 / 14 = 92,71, что означает, что 92 лодки прошли половину дистанции.
Следовательно, число участников, не прошедших половину дистанции, равно 226 - 92 = 134.
Верно? Пишите в комментариях.