UVa 10916

From Algorithmist
Jump to navigation Jump to search

10916 - Factstone Benchmark[edit]

Summary[edit]

Given a year, find out what the Amtel processor word size will be in that year, and then figure out the largest for which will fit in an unsigned integer of that word size.

Explanation[edit]

In 1960, the word size was a measly four bits, with the word size doubling every ten years. That means that given the year Y, the number of bits can be calculated as .

The largest unsigned integer that will no longer fit in K bits is . For to fit, then it must clearly be less than that. Now, consider . If this quantity is less than , then will fit. This suggests a fairly simple algorithm: given the number of bits K, keep adding terms (incrementing i each time) until this number exceeds K. The largest number that still fit is the required Factstone rating.

Notes[edit]

Strictly speaking, the running sum must actually be less than or equal to , but the difference between that quantity and K is so miniscule that it makes no difference to solving this problem.

Solutions[edit]

Input[edit]

1960
1981
2160
0

Output[edit]

3
8
254016