Precision issues? Help regarding an implementation question on precision

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	156
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Hello, I recently encountered a problem on Kattis which seems to be just be an implementation problem with precision issues that might need to be handled. However, after several WAs with no leads, I am at a dead end. I'm not even sure if it's precision related at the moment...

Below is my approach:

My Approach

My code:

My Code

C, F = input().split()

i1, i2 = C.find('.'), F.find('.')

if (i1 == -1):
    i1 = len(C)
if (i2 == -1):
    i2 = len(F)

k = 1

while (i1+1 < len(C) or i2+1 < len(F)):
    if (i1+1 >= len(C)):
        C += '0'

    if (i2+1 >= len(F)):
        F += '0'

    i1 += 1
    i2 += 1
    k *= 10

C = int("".join(C.split(".")))
F = int("".join(F.split(".")))

A, B = int(1e9), int(1e9)

for i in range(1, int(1e6)):
    l, r = ((C-F)*i+k-1)//k, ((C+F)*i)//k
    l = max(1, l)
    if (r - l >= 0):
        if (l < A):
            A, B = l, i

print(A, B, sep='\n')

Any help would be appreciated, thanks!

Comments (2)

Write comment?

shakil.ahamed

18 months ago, # |

Whatever you are doing inside the loop isn't very clear. Also, never do integral arithmetic in the real number domain. Google Stern-Brocot_tree.

→ Reply

kelzzin2_fan

18 months ago, # ^ |

The while loop here serves 2 purposes, i1 and i2 here represent the index of the decimal point if any, I wanted C and F to be integers, so I calculate k = some power of 10 and try to "multiply" C and F into integers. Lastly I parse it into actual integers by removing the decimal point.

Since I multiplied by k, I have to divide by k as well to get A back. Hence the floor/ceil division happening later down the line. This means all arithmetic should be only done with integers supposedly.

Thanks for the pointer for Stern-Brocot_tree tho!

kelzzin2_fan's blog