Найти в заданном интервале число двоичная запись которого содержит наибольшее количество единиц

@bad boy · Регистрация: 30.10.2020

Студворк — интернет-сервис помощи студентам

Алиса учится работать с двоичными числами. Она уже поняла, что число в двоичной записи получается в несколько раз длиннее, чем в десятичной. А еще она поняла, что нули писать дольше чем единицы. И теперь ее любимые числа — это те, двоичная запись которых содержит как можно больше единиц. Алисе дали задание — выбрать одно произвольное число из заданного закрытого интервала [a;b] и перевести его в двоичную запись. И теперь Алиса просит, чтобы вы написали программу, которая найдет в этом интервале число, двоичная запись которого содержит наибольшее количество единиц. Если таких чисел будет несколько, то Алиса будет рада любому из них.

Формат входных данных
На вход через пробел подаются два натуральных числа a и b. При этом 1≤a≤b≤10^18. Обратите внимание, что для хранения таких чисел в программе на С++ вам потребуется тип long long. В программе на PascalABC такой тип называется Int64.

Формат выходных данных
Программа должна вывести одно целое число из заданного диапазона, двоичная запись которого содержит наибольшее количество единиц. Само число следует выводить в десятичной записи.

Методика проверки и пояснение к тесту
Программа проверяется на 20 тестах. Прохождение каждого теста оценивается в 1 балл. При этом в первых пяти тестах
1≤a≤b≤1000. Тесты из условия задачи при проверке не используется.

Пример ввода 1:
150 200

Пример вывода 1:
191

Пример ввода 2:
1 255

Пример выводаt 2:
255

Пример ввода 3:
127 200

Пример вывода 3:
127

Time Limit: 1 секунда
Memory Limit: 256 MB

@zss · 15.10.2021, 18:16

Полный перебор для такой задачи не прокатит.
Нужно найти число x, такое, что 2^x<=b<2^x+1
Тогда число y= x-1 будет содержать наибольшее к-во единиц.
Остается проверить, что это число больше a.
Если это не так, то придется перебрать все числа между a и b (их будет мало).

@TheCalligrapher · 15.10.2021, 22:13

Сообщение от zss

Нужно найти число x, такое, что 2^x<=b<2^x+1
Тогда число y= x-1 будет содержать наибольшее к-во единиц.

y = 2^x-1 ?

Сообщение от zss

Если это не так, то придется перебрать все числа между a и b (их будет мало).

Мало? Длина этого интервала может достигать расстояния между соседними степенями двойки. Это совсем не мало.

Сообщение от bad boy

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

Запишем числа a и b в двоичном формате одно под другим с одинаковой длиной (дополним a нулями слева, если необходимо).

Если у чисел a и b есть общий префикс из 1, то этот префикс обязан войти в искомое результирующее число, ибо иначе оно не попадет в диапазон [a, b].

Как только мы при просмотре слева-направо найдем первый отличающийся бит между a и b (он, разумеется, будет равен 1 в b и 0 в a), нам нужно будет просто приписать к результирующему числу "хвост" вида 011...1 до конца числа.

Это и есть искомый результат.

Например: a = 8045 и b = 8091, т.е. 1111101101101₂ и 1111110011011₂

Code
1
2
3
4
5
6
7
8
9
a = 11111 0 1101101
b = 11111 1 0011011
    |---| ^ |-----|
      |   |    |
      |   |    хвост длины 7
      |   |
      |   первое отличие при просмотре слева-направо
      |
      общий префикс

Тогда ответом является 11111 0 1111111: 1111101111111₂ = 8063.

Очевидно, что такое число содержит максимальное количество единиц: в нем установлены все единицы, кроме того единственного нуля, который нужен для попадания в диапазон. То есть фактически задача сводится к поиску самого старшего различающегося бита между числами a и b.

Добавлено через 9 минут
---

Аааа... В решении есть неточность. Получаемое в результате число будет заведомо меньше b, т.е. будет принадлежать диапазону [a, b). А что если ответ задачи - именно b, что будет иметь место когда b целиком состоит из единиц? Подозреваю, что достаточно изначально взять диапазон [a, b + 1) и просто применить то же самое решение.

Добавлено через 2 часа 48 минут
---

Кстати, пораженческий поиск в инете находит еще один алгоритм, который, впрочем достаточно хорошо виден и при рассмотрении результатов того, что я привел выше:

Просто берем число a в качестве отправной точки и начинаем осторожно наращивать количество единиц в нем. "Осторожно" означает, что мы берем самый младший 0, заменяем его на 1 и проверяем, не превысили ли мы при этом b.

Тут нам на помощь приходят известные бит-хаки:

C++
1
2
n &= n - 1; // сбросить в 0 самую младшую 1 в числе
n |= n + 1; // установить в 1 самый младший 0 в числе

то есть получаем

C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
 
int main()
{
  unsigned long long a = 0, b = 0, next_a;
  std::cin >> a >> b;
  
  while ((next_a = a | (a + 1)) <= b)
    a = next_a;
  
  std::cout << a << std::endl;
}

Новые блоги и статьи Все статьи Все блоги /
JWT аутентификация в ASP.NET Core UnmanagedCoder 18.06.2025 Разрабатывая веб-приложения, я постоянно сталкиваюсь с дилеммой: как обеспечить надежную аутентификацию пользователей без ущерба для производительности и масштабируемости? Классические подходы на. . .	Краткий курс по С# aaLeXAA 18.06.2025 Здесь вы найдете все необходимые функции чтоб написать програму на C# Задание 1: КЛАСС FORM 1 public partial class Form1 : Form { Spisok listin = new Spisok(); . . .	50 самых полезных примеров кода Python для частых задач py-thonny 17.06.2025 Эффективность работы разработчика часто измеряется не количеством написаных строк, а скоростью решения задач. Готовые сниппеты значительно ускоряют разработку, помогают избежать типичных ошибок и. . .	C# и продвинутые приемы работы с БД stackOverflow 17.06.2025 Каждый . NET разработчик рано или поздно сталкивается с ситуацией, когда привычные методы работы с базами данных превращаются в источник бессонных ночей. Я сам неоднократно попадал в такие ситуации,. . .	Angular: Вопросы и ответы на собеседовании Reangularity 15.06.2025 Готовишься к техническому интервью по Angular? Я собрал самые распространенные вопросы, с которыми сталкиваются разработчики на собеседованиях в этом году. От базовых концепций до продвинутых. . .
Архитектура Onion в ASP.NET Core MVC stackOverflow 15.06.2025 Что такое эта "луковая" архитектура? Термин предложил Джеффри Палермо (Jeffrey Palermo) в 2008 году, и с тех пор подход только набирал обороты. Суть проста - представьте себе лук с его. . .	Unity 4D GameUnited 13.06.2025 Четырехмерное пространство. . . Звучит как что-то из научной фантастики, правда? Однако для меня, как разработчика со стажем в игровой индустрии, четвертое измерение давно перестало быть абстракцией из. . .	SSE (Server-Sent Events) в ASP.NET Core и .NET 10 UnmanagedCoder 13.06.2025 Кажется, Microsoft снова подкинула нам интересную фичу в новой версии фреймворка. Работая с превью . NET 10, я наткнулся на нативную поддержку Server-Sent Events (SSE) в ASP. NET Core Minimal APIs. Эта. . .	С днём независимости России! Hrethgir 13.06.2025 Решил побеседовать, с утра праздничного дня, с LM о завоеваниях. То что она написала о народе, представителем которого я являюсь сам сначала возмутило меня, но дальше только смешило. Это чисто. . .	Лето вокруг. kumehtar 13.06.2025 Лето вокруг. Наполненное бурями и ураганами событий. На фоне магии Жизни, священной и вечной, неумелой рукой человека рисуется панорама душевного непокоя. Странные серые краски проникают и. . .

@bad boy 0 / 0 / 0 Регистрация: 30.10.2020 Сообщений: 4

	Найти в заданном интервале число двоичная запись которого содержит наибольшее количество единиц 15.10.2021, 17:08. Показов 4170. Ответов 2 Метки c++, python, битовые операции, информатика, олимпиадные задачи, системы счисления (Все метки) Алиса учится работать с двоичными числами. Она уже поняла, что число в двоичной записи получается в несколько раз длиннее, чем в десятичной. А еще она поняла, что нули писать дольше чем единицы. И теперь ее любимые числа — это те, двоичная запись которых содержит как можно больше единиц. Алисе дали задание — выбрать одно произвольное число из заданного закрытого интервала [a;b] и перевести его в двоичную запись. И теперь Алиса просит, чтобы вы написали программу, которая найдет в этом интервале число, двоичная запись которого содержит наибольшее количество единиц. Если таких чисел будет несколько, то Алиса будет рада любому из них. Формат входных данных На вход через пробел подаются два натуральных числа a и b. При этом 1≤a≤b≤10^18. Обратите внимание, что для хранения таких чисел в программе на С++ вам потребуется тип long long. В программе на PascalABC такой тип называется Int64. Формат выходных данных Программа должна вывести одно целое число из заданного диапазона, двоичная запись которого содержит наибольшее количество единиц. Само число следует выводить в десятичной записи. Методика проверки и пояснение к тесту Программа проверяется на 20 тестах. Прохождение каждого теста оценивается в 1 балл. При этом в первых пяти тестах 1≤a≤b≤1000. Тесты из условия задачи при проверке не используется. Пример ввода 1: 150 200 Пример вывода 1: 191 Пример ввода 2: 1 255 Пример выводаt 2: 255 Пример ввода 3: 127 200 Пример вывода 3: 127 Time Limit: 1 секунда Memory Limit: 256 MB 0

@zss Модератор 13760 / 10956 / 6488 Регистрация: 18.12.2011 Сообщений: 29,218
	15.10.2021, 18:16
	Полный перебор для такой задачи не прокатит. Нужно найти число x, такое, что 2^x<=b<2^x+1 Тогда число y= x-1 будет содержать наибольшее к-во единиц. Остается проверить, что это число больше a. Если это не так, то придется перебрать все числа между a и b (их будет мало). 0

Опции темы