|
Тренажёр · Поразрядные операции Как вырастить ровно x бактерий?Проследи по дням, как ночное удвоение помогает получить нужное число бактерий, добавив как можно меньше новых. Задача 579A · Raising Bacteria (Выращиваем бактерии)Сначала ящик пуст. Каждое утро в него разрешено положить сколько угодно бактерий. Каждую ночь каждая бактерия делится надвое. Нужно в какой-то момент получить ровно x бактерий. Какое наименьшее число бактерий придётся положить в ящик за всё время? Ввод: одно целое число Мы будем строить один оптимальный вариант: утром добавлять 0 или 1 бактерию. Одна бактерия, добавленная раньше, успеет несколько раз удвоиться. Симуляция: проживём задачу по днямВыбери цель, попробуй предсказать добавление на ближайшее утро и нажимай «Следующий день». Ночь между днями симуляция учитывает сама. Быстрый выбор:
Цель в двоичной записи: 1101₂ 12³12²02¹12⁰
Каждый разряд: верхняя цифра — 0 или 1; снизу — сколько эта единица даст к последнему дню. Жёлтым отмечен следующий разряд. Перед первым утромЯщик пуст. Начни опыт, чтобы узнать, сколько добавлять утром. За прошедшую ночьНочи ещё не было
После добавления утром0 бактерий
Всего добавлено0 бактерий
Каждая точка обозначает одну бактерию. Для больших чисел показана лишь часть точек; точное количество написано выше. Сколько добавим в день 1?
День 0 из 4
Если кнопки недоступны: покажи разбор числа 13
Как узнать ответ без симуляции?Двоичная запись Для любого Почему нельзя добавить ещё меньше?Каждая бактерия, которую мы положили в ящик, к нужному моменту даст 1, 2, 4, 8 и так далее бактерий: её потомки удваиваются ночью. Если две добавленные бактерии дали равные группы, например 4 и 4, их можно мысленно объединить в 8. Такое объединение уменьшает число слагаемых. В конце останутся именно степени двойки из двоичной записи Решение для отправкиПрограмма считает единицы в двоичной записи числа. Выражение Симуляция читает биты слева направо, чтобы показать дни. Код читает их справа налево — на количество единиц порядок не влияет. Показать код на C++ и PythonC++
#include <iostream>
using namespace std;
int main() {
int x, answer = 0;
cin >> x;
while (x > 0) {
answer += (x & 1);
x >>= 1;
}
cout << answer << '\n';
}
Python
x = int(input()) answer = 0 while x > 0: answer += x & 1 x >>= 1 print(answer) Самопроверка перед отправкой: запусти программу для | |
|
| |
| Просмотров: 7 | | |
| Всего комментариев: 0 | |