Задача
Предприимчивая и умелая рукодельница решила подзаработать изготовлением «фенечек» из бисера. Любительница симметрии в искусстве, она использовала в своих орнаментах бусинки разных цветов (будем обозначать цвет целым положительным числом) по следующим правилам:
1) при длине ряда рисунка равной [latex]1[/latex] использовала бусинку первого цвета;
2) при длине ряда рисунка равной [latex]3[/latex] использовала бусинки двух цветов: [latex]1 2 1[/latex];
3) при необходимости добавления в рисунок еще одного цвета строился ряд: [latex]1 2 1 3 1 2 1[/latex] и так всякий раз в зависимости от числа используемых цветов, например, при использовании четырех цветов: [latex]1 2 1 3 1 2 1 4 1 2 1 3 1 2 1[/latex].
Напишите программу, которая помогла бы автоматизировать подбор цвета бусинки в ряду по её порядковому номеру.
Входные данные
В первой строке целое число [latex]k[/latex] [latex] (1 ≤ k ≤ 10^9) [/latex] – номер бусинки, цвет которой нужно определить, в ряду рисунка. Нумерация бусинок в ряду начинается с единицы.
Выходные данные
В первой строке одно целое число – номер цвета заданной бусинки.
Тесты
| # | ВХОДНЫЕ ДАННЫЕ | ВЫХОДНЫЕ ДАННЫЕ |
|---|---|---|
| 1 | [latex]10[/latex] | [latex]2[/latex] |
| 2 | [latex]116[/latex] | [latex]3[/latex] |
| 3 | [latex]1[/latex] | [latex]1[/latex] |
| 4 | [latex]454[/latex] | [latex]2[/latex] |
| 5 | [latex]12301230[/latex] | [latex]2[/latex] |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
import java.util.Scanner; class Main { public static void main (String[] args) throws java.lang.Exception { int n, m; double k; Scanner scan = new Scanner(System.in); n = scan.nextInt(); m = (int)(Math.log(n)/Math.log(2)); k = (double)(Math.log(n)/Math.log(2)); while (m != k){ n = (int)(n - (Math.pow(2,m))); m = (int)(Math.log(n)/Math.log(2)); k = (double)(Math.log(n)/Math.log(2)); } System.out.print(m + 1); } } |
Решение задачи
Рассматривая ряды с большим количеством цветов можно заметить закономерность: каждый чётный элемент равен единице, каждый последующий новый цвет будет на месте [latex]n·2[/latex]. Отсюда следует соответствие [latex]n[/latex] и [latex]2^{n-1}[/latex]. Формула для нахождения среднего элемента — [latex]\log_{2}n[/latex]. Программа будет искать средний элемент всегда, пока не найдёт нужный нам. Для чисел, из которых целый логарифм извлечь нельзя, найдем ближайший к нему и от числа отнимем [latex]2[/latex] в степени [latex]\log_{2}n[/latex]. К полученному ответу добавляем единицу, из-за приведённой ранее формулы [latex]2^{n-1}[/latex], и получаем правильный ответ.
Ссылки
• Задача на e-olymp.
• Решение на сайте ideone.