Codeforces Rd #368 (Div. 2) Problem C

In this problem, we have to deal with large integer to get the answer. The key to preserve precision is to use // operator for integer division because / will convert your int to float.

According to Python documentation, int has unlimited precision while float has only 53 bit precision (~15 digits) for integer part.

>>> import sys
>>> sys.float_info
sys.float_info(max=1.7976931348623157e+308, max_exp=1024, max_10_exp=308, min=2.2250738585072014e-308, min_exp=-1021, min_10_exp=-307, dig=15, mant_dig=53, epsilon=2.220446049250313e-16, radix=2, rounds=1)

>>> n = 9234567890123451
>>> n
9234567890123451
>>> float(n) # precision lost when > 53 bits
9234567890123452.0
>>> n/2 # as a result the division return wrong answer
4617283945061726.0

>>> n = 111222333444555666777888999
>>> print('%.0f' % n)
111222333444555672616173568
>>> int(n / 111)
1002003004005006060814336

Notes: For python3. int behaves the same way as long in python 2.

Tags: python,