print1625. Шоколад

printШоколад

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Новый тип шоколада поступил в местный магазин. Шоколад поставляется в виде плиток, каждая плитка состоит из `N` кусочков. Плитки с кондитерской фабрики приходят только в размерах, которые являются степенями двойки. Другими словами размер одной плитки равен 1, 2, 4, 8, 16, … кусочков.
Чтобы в полной мере насладиться вкусом шоколада Мирко должен съесть как минимум `K` кусочков. Его друг Славко также хотел бы попробовать немного шоколада. Поскольку Мирко спешит, чтобы попробовать шоколад сам, он решает разделить плитку, которую он купил, на куски так, чтобы у него осталось ровно `К` кусочков, и дать остальное (если останется) Славко. Плитки немного хрупкие, поэтому Мирко может ломать их только точно по их центру. Другими словами, из одной плитки из `D` кусочков, он может получить две плитки из `D/2` кусочков.
Напишите программу, которая будет определять минимальное количество разломов, которое Мирко необходимо выполнить, чтобы получить ровно `K` кусочков (не обязательно в одном куске). Кроме того, определить минимальный размер плитки Мирко должен купить, чтобы иметь по крайней мере `K` кусочков.
Ввод
Первая и единственная строка ввода будет содержать одно целое число `K` (`1\ ≤\ K\ ≤\ 1\ 000\ 000`) – число кусочков, которое Мирко должен продегустировать.
Вывод
Первая и единственная строка вывода должна содержать два целых числа, разделенных одним пробелов. Первое целое – самый маленький размер плитки, которую Мирко должен купить, второе – наименьшее количество разломов.

Пример ввода 1

6

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

8 2

Пример ввода 2

7

Пример вывода 2

8 3

Пример ввода 3

5

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

8 3
Источник: COCI 2009/2010 contest #7
loading