On a positive note, I have certainly improved since participating in GCJ 2013. I just barely made the cut for the Qualification Round in 2013, but my solution for Problem C, Fair and Square, was actually invalid despite passing the autograder because I didn't programmatically generate a series of fair and square numbers (palindromic numbers that are also squares) -- instead I just memoized a sufficiently large list of palindromic squares from OEIS (sequence A002779) against which I tested numbers from the input file.
In 2014, however, I really did pass the Qualification Round "fair and square". I subsequently competed in Rounds 1A and 1C but wasn't able to solve any of the problems within the allotted 2 hours and 30 minutes.
The problem statement for 1C Problem A is as follows:
Vida says she's part Elf: that at least one of her ancestors was an
Elf. But she doesn't know if it was a parent (1 generation ago), a
grandparent (2 generations ago), or someone from even more
generations ago. Help her out!
Being part Elf works the way you probably expect. People who are
Elves, Humans and part-Elves are all created in the same way: two
parents get together and have a baby. If one parent is A/B Elf, and
the other parent is C/D Elf, then their baby will be (A/B + C/D) / 2
Elf. For example, if someone who is 0/1 Elf and someone who is 1/2
Elf have a baby, that baby will be 1/4 Elf.
Vida is certain about one thing: 40 generations ago, she had 2^40
different ancestors, and each one of them was 1/1 Elf or 0/1 Elf.
Vida says she's P/Q Elf. Tell her what is the minimum number of
generations ago that there could have been a 1/1 Elf in her
family. If it is not possible for her to be P/Q Elf, tell her that
she must be wrong!
Input
The first line of the input gives the number of test cases, T. T
lines follow. Each contains a fraction of the form P/Q, where P and Q
are integers.
Output
For each test case, output one line containing "Case x: y", where x
is the test case number (starting from 1) and y is the minimum
number of generations ago a 1/1 Elf in her family could have been if
she is P/Q Elf. If it's impossible that Vida could be P/Q Elf, y
should be the string "impossible" (without the quotes).
Limits
1 <= T <= 100
Small dataset
1 <= P < Q <= 1000
in lowest terms.
Since P and Q are in lowest terms, we know that the denominator Q must be divisible by 2. In cases where \(Q \pmod 2 = 0\) does not hold, we should return "impossible".
Suppose Vida says she is \(\frac {1}{32}\) Elf: we can easily calculate how many generations ago she had a full Elf ancestor by taking the base 2 logarithm of 32:
$$\log_2{32} = 5$$
So at most 5 generations ago Vida had a full-blooded Elf in her family.
Using Python's math module, we can calculate logarithms to arbitrary bases as follows:
math.log(x, base)
where base is an optional argument and x is a float. If no base is specified, the natural logarithm (base e) will be calculated.
Let's start with a simple case. If Vida is currently \(\frac{1}{2}\) Elf, it means that 1 generation ago one of her parents was a full-blooded \(\frac{1}{1}\) Elf and the other had no Elf ancestry whatsoever, i.e. \(\frac{0}{1}\) Elf.
math.log(1.0/2.0, 2)
-1.0
Since this problem asks for number of generations as a positive integer, we will take the absolute value of the logarithm and cast the value to an int.
However, when taking the base 2 logarithm of certain \(\frac{P}{Q}\) values, it is possible to get values smaller than 1.0, which doesn't make sense in the context of generations, which move in discrete steps of 1 rather than being continuous.
Consider the case in which Vida is \(\frac{3}{4}\) Elf. How many generations ago did she have an ancestor who was full-blooded Elf?
math.log(3.0/4.0, 2)
-0.4150374992788438
Taking the absolute value of the above result, we get apprx. 0.415, but there is no such thing as "0.415 generations ago". The minimum number of generations is 1. In the case above, a single generation ago one of Vida's parents was full \(\frac{1}{1}\) Elf while the other was \(\frac{1}{2}\) Elf, making Vida three-quarters Elf. This can be expressed as
$$(\frac{1}{1} + \frac{1}{2})\cdot \frac{1}{2} = \frac{3}{4}$$
Therefore in cases where the absolute value of the base 2 logarithm returns a value less than a whole number, we will round up to the next integer. We can express this calculation as:
math.ceil(abs(math.log((P/Q), 2)))
We can then cast this to int using int() on the above expression.
Here is a gist of my code:
Although I verified that it generates the proper output
Case #1: 1
Case #2: 1
Case #3: 2
Case #4: impossible
Case #5: 8
5
1/2
3/4
1/4
2/23
123/31488
my solution for the small input (100 cases) was deemed incorrect by the GCJ autograder. I suspect that calculating the base 2 logarithm of \(\frac{P}{Q}\) finds the maximum number of generations prior that a full-blooded Elf could have been Vida's ancestor rather than the minimum number of generations prior.
댓글 없음:
댓글 쓰기