|
-2 / 6 / 5
Регистрация: 19.01.2022
Сообщений: 201
|
|
Деление на два19.02.2022, 10:57. Показов 3111. Ответов 36
Метки нет (Все метки)
Гоша очень любит делить числа на два. Иногда он развлекается следующим образом: берет какое-то число x, и делит его на два, потом результат снова делит на два, и так далее, пока не получит нечетное число. Например, если он выбрал число x=24, то сначала у него получится 12, затем 6, затем 3. Гоше нравится, когда этот процесс продолжается долго, поэтому он просит вас найти число из диапазона от a≤x≤b, выбрав которое можно делить на два как можно больше раз.
Входные данные: Первая строка содержит число a, вторая строка содержит число b (1≤a≤b≤1012). Выходные данные: Выведите число x, которое нужно выбрать. Если ответов несколько, выведите любой. Примеры: входные данные 20 30 выходные данные 24 входные данные 316 412 выходные данные 384 входные данные 1 1000000000000 выходные данные 549755813888 входные данные 15 15 выходные данные 15
0
|
|
| 19.02.2022, 10:57 | |
|
Ответы с готовыми решениями:
36
Деление Wav-файла на два канала
|
|
Диссидент
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
|
|
| 19.02.2022, 19:17 | |
|
Вот еще идея. Ищем такаю M = 2kчто b/M - a/M == 1 (границы надо уточнить.
Дальше - просто ![]() Радует, что практически без перебора. Добавлено через 1 минуту HaisTous, это похоже на ваш подход.
1
|
|
|
Гвоздь Задиров
1719 / 1118 / 337
Регистрация: 25.01.2019
Сообщений: 2,946
|
||||
| 19.02.2022, 20:31 | ||||
|
Хм! А если в битах? Достаточно будет создать двоичное число, которое входит в границы с наибольшим числом нулей сзаду!
Добавлено через 6 минут Т.е. однозначно берём первые единицы максимума, а дальше пока не придумал Добавлено через 18 минут ![]() Добавлено через 2 минуты 1111 1001 Добавлено через 2 минуты
0
|
||||
|
Вездепух
13235 / 6867 / 1827
Регистрация: 18.10.2014
Сообщений: 17,400
|
|
| 19.02.2022, 20:36 | |
|
0
|
|
|
Гвоздь Задиров
1719 / 1118 / 337
Регистрация: 25.01.2019
Сообщений: 2,946
|
||||||||
| 19.02.2022, 20:51 | ||||||||
|
Чую что плясать нужно от первого расхождения в битах минимума и максимума
Добавлено через 6 минут Добавлено через 5 минут
1
|
||||||||
|
Вездепух
13235 / 6867 / 1827
Регистрация: 18.10.2014
Сообщений: 17,400
|
||||||
| 19.02.2022, 21:16 | ||||||
|
Очевидно, что задача заключается в том, чтобы найти число, чья двоичная запись содержит максимальное количество замыкающих нулей.
Если в наш диапазон [a, b] попадают степени двойки, то максимальная из них - ответ задачи. Все. Так что задача является "интересной" только для диапазонов, не содержащих степеней двойки."Поисковое" решение за логарифм очевидно: 1. Берем максимальную степень двойки, не превосходящую b. Если она в диапазоне - это ответ.2. Дописываем в нее еще одну 1 в позицию сразу после старшей 1. Если мы попали в диапазон [a, b], то это ответ. Если мы все еще ниже a - сохраняем эту новую 1 в числе. Если мы оказались выше b - заменяем ее на 0.3. Циклически повторяем шаг 2 для следующей двоичной позиции справа. В какой-то момент мы должны попасть в диапазон [a, b].Добавлено через 7 минут Толком не проверял, но приведенные тесты проходят
Но, разумеется, сохраняется надежда на остроумное "тривиальное" решение .
1
|
||||||
|
-2 / 6 / 5
Регистрация: 19.01.2022
Сообщений: 201
|
|
| 19.02.2022, 21:45 [ТС] | |
|
Надо перевести два числа в двоичную систему, потом добавить нули
Переведем число в двоичную систему счисления. В таком представлении число можно делить тем дольше, чем больше нулей в конце числа. Для решения нужно: - перевести оба числа в двоичный вид (меньшее число дополнить незначащими нулями) - сравнивать биты числа начиная со старших разрядов Пока значения разрядов одинаковые, то переходим к следующему разряду. Если нашли разные разряды (0 в числа a, 1 в числе b), то считаем этот разряд равным единице, а остальные - до младших разрядов - нулями. Код 10100 (20) 11110 (30) --- 11000 (24) - здесь второй слева разряд отличается Код 100111100 (316) 110011100 (412) --- 110000000 (384) - здесь тоже второй слева разряд отличается
0
|
|
|
Вездепух
13235 / 6867 / 1827
Регистрация: 18.10.2014
Сообщений: 17,400
|
||
| 19.02.2022, 22:05 | ||
|
--- Другими словами, вся задача фактически эквивалентна Найти в заданном интервале число двоичная запись которого содержит наибольшее количество единиц Разница только в характере приписываемого хвоста. Там приписывался хвост 011...1, Здесь приписывается хвост 00...0.
0
|
||
|
Гвоздь Задиров
1719 / 1118 / 337
Регистрация: 25.01.2019
Сообщений: 2,946
|
|||||||
| 19.02.2022, 22:10 | |||||||
|
Я тут заколхозил чо в виду имел:
1
|
|||||||
|
Вездепух
13235 / 6867 / 1827
Регистрация: 18.10.2014
Сообщений: 17,400
|
||||||||
| 19.02.2022, 22:13 | ||||||||
b. В цикле сбрасываем у числа b самый младший единичный бит в 0 пока мы находимся не ниже a. Вот и все.
1
|
||||||||
|
Гвоздь Задиров
1719 / 1118 / 337
Регистрация: 25.01.2019
Сообщений: 2,946
|
|||
| 19.02.2022, 22:19 | |||
|
Добавлено через 24 секунды Ну и в таком духе проскакивало
1
|
|||
|
Вездепух
13235 / 6867 / 1827
Регистрация: 18.10.2014
Сообщений: 17,400
|
|||||||
| 19.02.2022, 22:26 | |||||||
0
|
|||||||
|
-2 / 6 / 5
Регистрация: 19.01.2022
Сообщений: 201
|
||||||
| 19.02.2022, 22:27 [ТС] | ||||||
Вот готовый код на питоне, работающий, тут легко в с++ переделать можно
0
|
||||||
|
Вездепух
13235 / 6867 / 1827
Регистрация: 18.10.2014
Сообщений: 17,400
|
|||
| 19.02.2022, 22:52 | |||
|
0
|
|||
|
848 / 651 / 323
Регистрация: 24.02.2017
Сообщений: 2,297
|
||||||
| 20.02.2022, 19:23 | ||||||
0
|
||||||
|
Вездепух
13235 / 6867 / 1827
Регистрация: 18.10.2014
Сообщений: 17,400
|
|
| 20.02.2022, 19:25 | |
|
0
|
|
|
848 / 651 / 323
Регистрация: 24.02.2017
Сообщений: 2,297
|
|||||||||||||
| 20.02.2022, 22:12 | |||||||||||||
0
|
|||||||||||||
|
Вездепух
13235 / 6867 / 1827
Регистрация: 18.10.2014
Сообщений: 17,400
|
|||
| 20.02.2022, 22:45 | |||
|
a=13,b=17. В ответ получаем 12.
0
|
|||
| 20.02.2022, 22:45 | |
|
Деление файла на два
Деление с выводом остатка два двоичных числа Emu8086
Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Особенности gif сгенерированных в Си
russiannick 21.10.2026
Рассмотрим генерацию gif файлов, которые в Си имеют свои особенности.
Gif представляет собой графический формат популярный в интернете. Посмотрим на палитру. Gif файл сгенерированный в си отличается. . .
|
FPS контроллер с анимированными Y-Bot и 3D-звуком miniaudio (Box3D, Recast, BehaviorTree.CPP, ozz-animation, ImGui, OpenGL и SDL3)
8Observer8 18.10.2026
Содержание блога | English Version
Полное мультиплатформенное руководство по стартовому проекту с FPS-контроллером игрока, анимированными роботами Y-Bot с 4-слойным блендингом, 3D-физикой Box3D,. . .
|
Локальный http сервер
Argus19 17.10.2026
Локальный http сервер
На работе, на двух локальных компьютерах круглосуточно работают программы опроса приборов с записью в книги Excel,которые раз в сутки записываются на сервер компании. Т. к. . . .
|
Копировать Windows на новый диск на UEFI
damix 17.10.2026
https:/ / uriesk. wordpress. com/ 2016/ 11/ 01/ move-window-10-to-ssd-on-a-uefi-dualboot-system-with-basic-linux-tools/
TL DR
Вставляем диск, а старый подключаем через переходник, грузимся с лайва. . .
|
|
ИИ не может найти нужный язык в списке
Supersumestria 05.10.2026
Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык.
Возвращает он вот это:
https:/ / i. **********/ vqBWLe2. png
Нужную строчку в 3й колонке просто выдумал. .
Это. . .
|
Новая последняя моя музыка в SUNO
zorxor 05.10.2026
Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor.
Это. . .
|
Программный домашний кинотеатр
russiannick 27.09.2026
Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js.
В помощники взял Яндекс-Алису.
Было создано три зала на разные интересы.
исторические и ретро
сериал Хичкок. . .
|
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого
zorxor 21.09.2026
Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .
|