1285. How Wide Each Field Has To Be
A record is to hold n fields. For each, the largest value it must store is
given. Print how many bits each field needs, then the total, then whether the
record fits in a 64-bit word.
``` maxima 1023 1023 1023 -> 10 10 10 30 FITS
maxima 1000000000 1000000000 1000000000 -> 30 30 30 90 TOO WIDE ```
## What most people try first
ceil(log2(v)), which is wrong by one on every power of two, and
ceil(log2(v + 1)), which is right in exact arithmetic and unreliable in
floating point. At v = 2^53 a double can no longer represent v + 1
distinctly from v, so the two expressions collapse into each other; and even
below that, log2 of a large power of two can come back as 29.999999999999996
and round to 29 where 30 is correct. Deciding an exact integer question with a
library function that returns an approximation is the wrong tool, whatever
guards are added.
## Count the bits instead
A field storing every value from 0 to v needs exactly as many bits as v has:
w = 0
t = v
while t > 0:
t = t / 2 integer division
w = w + 1
This is exact at every magnitude because it never leaves the integers, and it is at most 60 iterations.
## Why that is the right count, argued rather than asserted
A w-bit field holds exactly the values 0 through 2^w - 1. So the field is
big enough precisely when v <= 2^w - 1, that is v < 2^w, and the smallest
such w is the number of binary digits of v. The loop counts those digits,
halving once per digit.
Check the boundaries, which is where the off-by-one lives:
v = 1 1 bit holds 0 and 1
v = 2 2 bits holds 0 to 3; one bit would only hold 0 and 1
v = 3 2 bits holds 0 to 3 exactly
v = 1023 10 bits holds 0 to 1023 exactly
v = 1024 11 bits
So the count jumps AT each power of two, not just after it, which is exactly
what ceil(log2(v)) gets wrong: it says 10 for v = 1024 where 11 is needed.
## Where the total matters
If the widths sum to more than 64, the record cannot be one machine word and either a field has to be narrowed, a field has to be dropped, or the record has to become two words. Reporting the total rather than silently truncating is the entire point of checking, and it is the validation step #1282's unpacker assumes somebody else has done.
The threshold is 64 inclusive: a total of exactly 64 fits, and 65 does not.
## Width
The maxima reach 10^18, below 2^60, so each needs at most 60 bits and the
values themselves need a 64-bit integer. 10^18 is past the 2147483647 a
signed 32-bit integer holds by nine orders of magnitude, and past
2^53 = 9007199254740992, so a JavaScript Number cannot hold the inputs
either and the reference uses BigInt for them. The WIDTHS are at most 60 and
the total at most 480, both of which fit in anything. In Java the maxima must be
read with Long.parseLong rather than through StreamTokenizer, whose nval
is a double.
Constraints - `1 ≤ n ≤ 8` - `1 ≤ each maximum ≤ 1000000000000000000`
Input
The first line contains the integer n.
The second line contains n integers: the largest value each field must store.
Output
Print three lines. The first holds the n field widths in order, separated by single spaces. The second holds their total. The third holds the single word FITS if the total is at most 64, or the two words TOO WIDE otherwise.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.