|
|
back to boardShow all messages Hide all messagesis there any solution for this problem that is not based on the exhaustive search? Yes, there is. I recursively try all denominators <= 100000 walking on primes - this way I automatically get all of its divisors at no cost and then DP in order to sum up to nominator using <20 of denoninator's divisors. Interestingly, the bigger the limit, the faster it performs. Next reasoning should work: if (1/(n+1)<A<1/n => A=1/(n+1)+B, where B<1/(n*(n+1)) and cannot contain 1/(n+1) again Thus 1/v1,1/v2,... is basis that converges to A very quickly A is rational then sequence must be finite It's true, but there exists the limit for a denominator of fractions in this problem. I tried this algo in my first solution, and got WA#3.
Edited by author 01.12.2015 19:01 |
|
|
