UVa 10909
Contents |
[edit] UVa 10909 - Lucky Number
[edit] Summary
Consider the sequence of all natural numbers (1, 2, 3, etc.). In the first step, delete all even ones. In the k-th step (k>1) strike out every x-th number, where x is the k-th smallest number that is still in the sequence. The numbers that survive forever are called lucky.
Given is a set of numbers. For each of them, decide whether it can be written as a sum of two lucky numbers.
[edit] Explanation
The most difficult part of this task is generating the set of lucky numbers. To do this reasonably fast, you need to implement your own set-like structure (e.g., a balanced tree) that supports the following operations in logarithmic time:
- given k, finding the k-th smallest element
- given a pointer to an element, erase it
Having this structure, simulate this process until the first removed number exceeds the input constraints.
Once we have the set of lucky numbers, the rest is straightforward. One possibility is to use an array saying whether a number is lucky. Now if we want to get the sum K, we may loop over all possibilities for one of the numbers (x) and use the array to check whether K-x is lucky, too.
[edit] Gotcha
- Don't forget that if there are more possible answers, you have to print a fixed one. To find the correct one, the first summand has to be the largest possible lucky number between 1 and N/2, inclusive.
[edit] Notes
- For the given input constraints (and probably also in general) the lucky numbers are dense enough, thus each even number can be obtained as a sum of two lucky numbers. Obviously, all lucky numbers are odd, so no odd number can be obtained as a sum of two lucky numbers.
[edit] Input
11 12
[edit] Output
11 is not the sum of two luckies! 12 is the sum of 3 and 9.
