Опубликовано 5 лет назад по предмету Информатика от maksvlad00

Есть кучка из 577 орехов. За одну операцию можно любую из уже имеющихся кучек разделить на две. Если при этом получатся две неравные кучки, то взимается штраф 1 рубль. Какова наименьшая возможная сумма штрафа, которую придется заплатить, чтобы получить 577 кучек по одному ореху в каждом?

Ответ

Ответ дан ExGon

Деление до конца без штрафов возможно, если количество орехов в кучке будет какой-либо степенью двойки (2, 4, 8, 16, 32, 64, 128, 256, 512). Число 577 - нечетно, следовательно, его можно представить <четное>+<нечетное>. При делении 576+1 получим первый штраф. Число 576 не является степенью двойки, поэтому необходимо опять поделить орехи на неравные кучки: 512+64 (второй штраф). 512 и 64 - степени двойки, значит дальнейшее разделение можно выполнить без штрафов.
Можно делить, например, так:
1. 512 и 65 орехов (штраф 1 рубль)
2. 65 делим на 2 кучки: 64 и 1 (штраф 1 рубль)
3 и все следующие операции: кучки из 512 и 64 орехов делим на равные кучки (512: 256 и 256, 256: 128 и 128; 64: 32 и 32, 32: 16 и 16 и т.д.).
Получаем, что минимальная сумма штрафа = 2 рубля.

Самые новые вопросы

Математика - 4 года назад

Решите уравнения: а) 15 4 ∕19 + x + 3 17∕19 = 21 2∕19; б) 6,7x - 5,21 = 9,54

Информатика - 4 года назад

Помогите решить задачи на паскаль.1) дан массив случайных чисел (количество элементов вводите с клавиатуры). найти произведение всех элементов массива.2) дан массив случайных чисел (количество элементов вводите с клавиатуры). найти сумму четных элементов массива.3) дан массив случайных чисел (количество элементов вводите с клавиатуры). найти максимальный элемент массива.4) дан массив случайных чисел (количество элементов вводите с клавиатуры). найти максимальный элемент массива среди элементов, кратных 3.

География - 4 года назад

Почему япония - лидер по выплавке стали?

Математика - 4 года назад

Чему равно: 1*(умножить)х? 0*х?

Русский язык - 4 года назад

В каком из предложений пропущена одна (только одна!) запятая?1.она снова умолкла, точно некий внутренний голос приказал ей замолчать и посмотрела в зал. 2.и он понял: вот что неожиданно пришло к нему, и теперь останется с ним, и уже никогда его не покинет. 3.и оба мы немножко удовлетворим свое любопытство.4.впрочем, он и сам только еле передвигал ноги, а тело его совсем застыло и было холодное, как камень. 5.по небу потянулись облака, и луна померкла.