ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
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
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