Pyro Tubes

Interview

Time limit13sMemory limit256 MB

Summary

For each value in a sorted list, count larger list values whose 18-bit patterns differ in at most two bits.

Level: Medium5 of 10
Topics: Bit manipulation, Hash map
Solved: No attempts yet

Problem

A rock festival stage carries 18 pyro tubes, numbered 1 to 18. Each tube fires one flame burst of a fixed luminosity.

Figure 1: tube numbering

Tube 1 produces a luminosity of 1. For $N > 1$ , tube $N$ produces double the luminosity of tube $N-1$ , so tube $N$ produces $2^{N-1}$ .

To reach a wanted luminosity, several tubes fire at the same time. The luminosity achieved is the sum of the luminosities of the tubes that fire, written as a single integer $L$ . The control software takes $L$ as input and decides which tubes to activate and which to leave deactivated.

Figure 2: tube states

For a given $L$ there is exactly one set of activated tubes that produces it.

A sticky valve or a clogged tube sometimes stops the system from firing the requested set. The crew then activates and deactivates tubes to fire a different set. Switching one tube from activated to deactivated, or the other way round, counts as one state change.

Figure 3: the requested tube states (left) and a set 2 state changes away (right)

The two groups in figure 3 differ in two places. Tube 7 is activated on the left and deactivated on the right, and tube 8 is deactivated on the left and activated on the right.

Figure 4: the requested tube states (left) and a set 1 state change away (right)

The left side of figure 4 shows the tube states for a requested luminosity of 45393. On the right, tube 10 is activated as well, which gives a luminosity of 45905.

The producers accept a different luminosity as long as it is brighter than the original one. They give the list of $L$ values scheduled for the show, and for each original value in the list you count the alternative $L$ values that meet all three requirements below.

The alternative value is greater than the original value.
The alternative value is another value in the given list.
The alternative value can be reached from the original set by changing at most 2 tube states.

Input

The scheduled $L$ values are given one per line in increasing order. Each value satisfies $1 \le L \le 250000$ , so there are at most 250000 values. A single -1 on the last line ends the input.

Output

For each original $L$ value, in the order given, print one line of the form L:C, where $L$ is the originally requested luminosity and $C$ is the number of alternative values that meet the three requirements above. Do not put spaces around the colon.

Some strategies produce correct results but do not finish inside the time limit, so an efficient algorithm is needed.

Examples2

Example 1
Input
```
1
3
8
10
25
-1
```
Expected output
```
1:3
3:1
8:2
10:0
25:0
```

Example 2

Input

Expected output