ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1541. Chase

is there a solution?
Posted by RAVEman 8 Mar 2007 04:42
is there any solution for this problem that is not based on the exhaustive search?
Re: is there a solution?
Posted by MikleB 14 Mar 2007 01:35
Google aliquot fractions
Re: is there a solution?
Posted by Denis Koshman 15 Jul 2008 02:21
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.
Re: is there a solution?
Posted by svr 6 Jan 2011 08:49
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
Re: is there a solution?
Posted by bsu.mmf.team 24 Aug 2011 02:48
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