Всем доброго здоровья.
Наверное, каждый из нас когда-то (а может, и на вчерашнем соревновании) при решении задач имел проблемы с погрешностями. Думаю, что для каждого из нас это очень неприятно, когда при правильном алгоритме (если можно так выразится) Ваше решение не засчитывается из-за такого рода "ошибок". Моя идея - давайте в этом форуме будем выкладывать разные задачи, реализация решений которых и заключается в нахождении такого рода погрешностей. Ну и, конечно же, будем обсуждать, чем же вызваны эти погрешности.
Part 1
Part 2
Можно записать:
pi / n - angle > 0 + eps
или
pi - angle * n > 0 + eps
очевидно, eps должен различаться в этих выражениях на порядок-два при n до 100... Нехорошо лепить везде 1e-9 просто так, от балды, не вдумываясь в характерные значения... "Авторская" идея тут вроде не при чём... %)
Она итерациями решается... правда, там ещё надо как-то nan обходить...
и нормировать кажется
Тупо в лоб: зная вероятности на текущем шаге, можно посчитать вероятность на следующем. То, что при этом происходит простое перемножение матриц, а следовательно
можнонужно сперва перемножить сами матрицы, я как-то упустил из виду :) Поэтому я и удивился насчет 2^40.UPD: А почему именно в этой клетке, а не в любой другой?
http://acmp.ru/index.asp?main=task&id_task=137
А эта задача?