Editorial

Let us go with the example where ~k = 4~, ~a = 7~, and ~n = 2~.

In other words, summing all positive integers that can be represented with at most ~k = 4~ bits with exactly ~n = 2~ bits that equal to ~1~, average it then round it down will get ~a = 7~.

Question 1: How many numbers are there where ~k = 4~ and ~n = 2~?**

We notice that there will be a total of ~2^{k} = 2^k = 16~ non-negative integers that can be represented with at most ~k = 4~ bits.

Each bit can be either set or unset (either ~1~ or ~0~). There are ~k = 4~ digits for each number, and we are choosing exactly ~n = 2~ of those bits to be set. This is a combination problem, and the number of ways to choose ~n~ bits out of ~k~ is given by the combination formula ~nCr(k, n) = nCr(4, 2) = 6~.

Question 2: What is the sum of all numbers where ~k = 4~ and ~n = 2~?**

A brute-force solution that generates all required numbers then summing it could work for smaller numbers of ~n~ and ~k~, but anything above ~n = 15~ would likely kill your computer.

Instead, we make a few observations:

• There are ~nCr(k, n) = 6~ numbers in total.
• Out of every single digit in all numbers, only ~n / k = 50%~ of all digits will be set.
• For all ~nCr(k, n) = 6~ numbers, each column of digits will have exactly the same number of set bits.

Knowing the above, we can deduce that there will be a total of ~nCr(k, n) * \left(n / k\right)~ bits set for every digit position. In other words, the sum of all numbers can be calculated as ~\sum_{i = 0}^{k - 1}{\left( 2^{i}\times\frac{n}{k}\times\text{nCr}\left(k, n\right) \right)} = 45~.

Question 3: How do we find the rounded-down average?

We have the sum and count from above. Dividing the sum by the count with a floor function attached to it would ~\text{floor}\left(\frac{\sum_{i = 0}^{k - 1}{\left( 2^{i}\times\frac{n}{k}\times\text{nCr}\left(k, n\right) \right)}}{\text{nCr}\left(k, n\right)}\right) = 7~

This formula can be further simplified to ~\frac{n}{k}\times{\left(2^{k}-1\right)}=7~.

Question 4: How do we find ~n~ from ~k~ and ~a~?

Now that we have a formula that calculatees ~a~ from ~n~ and ~k~, ignoring the floor function, the formula can be rearranged as ~n = \frac{a * k}{2^{k} - 1}~. Adding a round function to this would pass all test cases.

Final Implementation

k, a = map(int, input().split())
print(round(a * k / ((1 << k) - 1)))