Precision issues? Help regarding an implementation question on precision

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

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

19 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

19 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