×

# TO FIND NEAREST FRACTION

 1 problem (http://codeforces.com/problemset/problem/281/B) how to approach this problem ....is there any article or concept which needs to be covered to solve this kind of problem(if it is please suggest )....i am stuck with this since 2 days ...actually i have a logic but that is not efficient enough so getting TLE asked 26 Jun '17, 13:20 15●4 accept rate: 0%

 2 So, here is the approach: Given that 1<=b<=n and a>=0, you have to find a pair a,b such that abs(x/y-a/b) is minimum. 1.Declare a variable min = 100000000; 2.Loop from i=1 to i<=n; 3.Do binary search for number, where low = 0 and high = 100001 and made a check for mid/i < z; 4.After binary search check which one is minimum (low/i-z) or (high/i-z), save it accordingly. 5.Now check for Minimum b/w saved number and min, change min accordingly. Here is the heart of the problem: for(int i = 1;i <= n;i++) { ll l = 0; ll r = 100001; ll mid; ll a; int b; double k; while(r - l > 1) { mid = (r + l) / 2; if((double)mid / i < z)l = mid; else r = mid; } if(fabs((double)l / i - z) <= fabs((double)r / i - z)) { k = fabs((double)l / i - z); a = l; b = i; } else { k = fabs((double)r / i - z); a = r; b = i; } if(k < Min) { Min = k; flag1 = a; flag2 = b; } }  Happy coding! answered 26 Jun '17, 16:14 241●7 accept rate: 9% I was bounding the search b/w 0 and 100001, according to the max. limit of constraints. (26 Jun '17, 18:23) thanx man!! for the solution and the last problem you answered that was really helpful(union find ds).... (26 Jun '17, 18:24)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×832
×682

question asked: 26 Jun '17, 13:20

question was seen: 438 times

last updated: 26 Jun '17, 18:24