e-olymp 165. Симметрия

Задача

Предприимчивая и умелая рукодельница решила подзаработать изготовлением «фенечек» из бисера. Любительница симметрии в искусстве, она использовала в своих орнаментах бусинки разных цветов (будем обозначать цвет целым положительным числом) по следующим правилам:

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]

 

Код программы

 

Решение задачи

Рассматривая ряды с большим количеством цветов можно заметить закономерность: каждый чётный элемент равен единице, каждый последующий новый цвет будет на месте [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.

7 thoughts on “e-olymp 165. Симметрия

  1. У вас написано: «каждый последующий новый цвет будет на месте $n*2$». Во-первых, это неверно. Во вторых, даже если бы там было умножение, то стоило использовать команду $n\cdot2$.
    Напишите подробнее, что за «соответствие $n$ и $2^n-1$»

    • Возможно вы меня не совсем поняли, под «каждый последующий новый цвет» я имел в виду цвет, который мы не встречали ранее. При n=1 новый цвет, а именно двойка, будет на месте n=1*2 и т.д.
      А формулу исправил на более корректную.

    • Это «(1 ≤ k ≤ 109)» тоже формула.
    • $log_2n$ должен выглядеть так — $\log_{2}n.$
    • Вам нравится обезьянка вместо Вашей фотографии? Может быть лучше зарегистрироваться на gravatar.com?
    • Где метки?
    • В коде нужно ставить пробелы между знаками операций. Это поможет Вам расположить к себе читателя Вашей программы. В данном случае преподавателя.

Добавить комментарий