Codeforces Beta Round #83
Сегодня участвовал в - Codeforces Beta Round #83 (второй дивизион). Решал все на Python.
Первую и вторую задачу решил без особых проблем, плюс по второй 4 успешных взлома. Третья задача не понравилась, не решал.
С четвертой (D. Баскетбольная команда) получилось так. Формулу для решения я вывел, вроде бы все верно. Но проблема в том, что там дробь, где в числителе и знаменателе - примерно равные по величине произведения сотни довольно больших целых чисел.
Длинная арифметика для целых в Python из коробки, так что при умножении переполнения не будет. Но для деления двух больших целых чисел в Python 2.6 надо привести их к float (иначе получится обязательно целое) - и имеем OverflowError:
>>> 1.0 * (1000 ** 200) / (1001 ** 200)
OverflowError: long int too large to convert to float
По хорошему, чтобы этого избежать, надо не считать отдельно числитель и знаменатель, а умножать на одно число - делить на одно число (во float) и т.д.
Но в Python 3 можно поделить целые числа и получить float, без проблем переполнения в случае подсчета отдельно числителя и знаменателя:
>>> (1000 ** 200) / (1001 ** 200)
0.8188125757004808
Еще в Python 2.6 можно было бы использовать тип Decimal:
>>> from decimal import Decimal
>>> Decimal(1000 ** 200) / Decimal(1001 ** 200)
Decimal(‘0.8188125757004809207789472534’)
Интересно, что в C++ при включенных оптимизациях (по крайней мере в g++ с -O2) при вычислении отдельно числителя и знаменателя не происходит переполнения double, т.к. используются регистры процессора с большей разрядностью без пересылки промежуточных результатов в память.
This is crossposted entry. kit1980.ru
Первую и вторую задачу решил без особых проблем, плюс по второй 4 успешных взлома. Третья задача не понравилась, не решал.
С четвертой (D. Баскетбольная команда) получилось так. Формулу для решения я вывел, вроде бы все верно. Но проблема в том, что там дробь, где в числителе и знаменателе - примерно равные по величине произведения сотни довольно больших целых чисел.
Длинная арифметика для целых в Python из коробки, так что при умножении переполнения не будет. Но для деления двух больших целых чисел в Python 2.6 надо привести их к float (иначе получится обязательно целое) - и имеем OverflowError:
>>> 1.0 * (1000 ** 200) / (1001 ** 200)
OverflowError: long int too large to convert to float
По хорошему, чтобы этого избежать, надо не считать отдельно числитель и знаменатель, а умножать на одно число - делить на одно число (во float) и т.д.
Но в Python 3 можно поделить целые числа и получить float, без проблем переполнения в случае подсчета отдельно числителя и знаменателя:
>>> (1000 ** 200) / (1001 ** 200)
0.8188125757004808
Еще в Python 2.6 можно было бы использовать тип Decimal:
>>> from decimal import Decimal
>>> Decimal(1000 ** 200) / Decimal(1001 ** 200)
Decimal(‘0.8188125757004809207789472534’)
Интересно, что в C++ при включенных оптимизациях (по крайней мере в g++ с -O2) при вычислении отдельно числителя и знаменателя не происходит переполнения double, т.к. используются регистры процессора с большей разрядностью без пересылки промежуточных результатов в память.
This is crossposted entry. kit1980.ru