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

Автор TheMartian0x48, история, 3 года назад, По-английски

You are given an integer K.
A function F is defined over non-negative integers as the following:

$$$ F(x) = \sum((x | i) - (x \& i)) $$$

for i such that the given conditions hold true:

$$$ 0 <= i <= x \text{ and } ((x | i) - (x \& i)) = x - i $$$

Determine the number of non-negative integers x such that

$$$ F(x) \leq K $$$

| = bitwise or
& = bitwise and

Example for K = 6, possible x is 0, 1, 2, 3 and 4 as F(0) = 0
F(1) = 1
F(2) = 2
F(3) = 6
F(4) = 4
So, the answer is 5.

Constraints

$$$ 1 \leq T \leq 10^{5} \\ 1 \leq K \leq 10^{18} \\ \text{Time Limit: 5.0 sec(s) for each input file.} \\ \text{Memory Limit: 256 MB} $$$

It was asked in nokia coding hackthon.
I wasn't able to find any pattern to approach any optimal solution. How would you approach this problem?

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

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

not sure but $$$ x \triangle i = x - i$$$ seems like $$$ i \subseteq x$$$, so I guess now that you know the contribution of each bit, the growth of sum is very fast, that is it will reach to $$$ K $$$ in very less number of operations, so precalculate and then answer for each test case from your precalculated stuff.