Блог пользователя KONAKONA666

"простая" математика
Автор KONAKONA666, история, 8 лет назад, По-русски

Добрый день, помогите решить задачу http://acmp.ru/index.asp?main=task&id_task=644, все сводится к ~ O (klogn), а лучшее решение в голову не приходит. В общем A[i] = A[i-1] + S(A[i-1]),A[1] = N, где S(X) — кол-во единиц в двоичной записи числа X,надо найти A[k].Есть ли эффективные способы вычислить S(X) или A[i]?

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Эффективно S(X) можно вычислять следующим способом: представим X = 216 * A + B, где 0 <  = A, B < 216.
Тогда можно сделать преподсчет S(X) для значений до 216 по формулам S(1) = 1;S(2 * X + 1) = S(X) + 1;S(2 * X) = S(X). После этого S(X) можно будет считать за O(1): S(X) = S(216 * A + B) = S(A) + S(B).

Но это только сокращает тупое решение до O(K), что вообще не дело. Как решать правильно — пока не курнул.

→ Ответить
  • »
    »
    8 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

    Как решать правильно — пока не курнул.

    Курите правильные мануалы.

    Задача — на несложный прекалк. Опирается на следующий эмпирический факт (уверен, что доказывается он довольно легко, но мне сейчас правда лень этим заниматься): последовательности, порождаемые различными N, имеют общий бесконечный хвост (причем, сходятся к этому общему хвосту они очень быстро).

    Давайте запустим тупое решение для N = 2 * 10^9 и K = 2 * 10^9, чтобы оценить порядок максимальной величины ответа. Получим 36 с копейками миллиардов. Теперь запустим генерацию последовательности, начиная с N = 1, и до 37 миллиардов. Сохраним каждый миллионный по порядку член этой последовательности. На моей машине генерация отработала за 36 секунд.

    Теперь, чтобы найти ответ для произвольных N и K, мы начинаем с N и идем "пешком" до тех пор, пока не встретим табличную запись. Далее мы идем вперед гигантскими прыжками по миллиону, а когда нам останется сделать меньше миллиона шагов, опять пойдем "пешком".

    Мое решение на C++ зашло за 238 миллисекунд.

    P.S. Оптимизацию предпосчетом для количества ненулевых бит в числе я не использовал, зато использовал вот этот широко известный (и популярный в качестве вопроса на собеседованиях) алгоритм:

    int bitCount(long long n)
{
	int ans = 0;
	while (n != 0) {
		n &= n - 1;
		ans++;
	}
	return ans;
}
    → Ответить