Перевёртыш строки на JavaScript

[Xaositect]

Ой, действительно не хватает. Значит, надо считать по двум взаимно простым модулям в районе $2^{57}$ (или по четырем в районе $2^{29}$).
Я проверил - вычисление в double методом Горнера выдает на моем примере $+0$.

[_Ivana]

Xaositect в сообщении #1328033 писал(а):

Ох. Таких вещей без знания теории делать нельзя.

Но если очень хочется нет бортовой длинной арифметики, то можно. И о знании какой теории речь? Мне тоже не нравится использование плавающей арифметики в этой задаче, я в курсе, что точности 15 знаков не хватит при 10-й степени, но я увидел, что и целочисленной 64-битной арифметики при наивной реализации (без взаимно простых модулей) также не хватит, и написал такой хак, с целью проверить прохождение тестов, не усложняя расчет - они прошли. Тем более, этот момент не является хоть сколь-нибудь критичным в плане самого алгоритма. При наличии более серьезных тестов разумеется я бы рассчитал в целых, написав для этого свой велосипед или подключив какую-нибудь либу.

ЗЫ если на то пошло, там и функцию сортировки результата надо поменять, ибо она сортирует через приведение к даблам, а на близких рациональных числах при больших числителях/знаменателях это тоже может привести к ошибке - и я отлично это понимаю, и знаю, что таких вещей делать нельзя

ЗЗЫ если бы я добавлял эту задачу на сайт, я бы разумеется добавил самые жесткие тесты, чтобы подобная халява не проходила - как я делал в подобных случаях, например в моих катах на Кодоворсах. Результат - народ просто не решает и все А в случае данной задачи достаточно просто один в один переписать алгоритм на Питоне, где тоже есть авторесайзящиеся вектора и из коробки длинная арифметика - благо в списке языков для проверки решений он есть И пары на Питоне тоже в ядре и не такие страшные по синтаксису, и скорость алгоритма позволяет его реализовать на любом медленном скрипте - прямо все аргументы за Питон, действительно зря я по инерции на плюсах решал.

[Xaositect]

_Ivana, извините, если что не так. Здесь все-таки тема для обучения начинающих, нельзя же просто так без объяснения такие хаки писать.

[_Ivana]

Xaositect, и Вы тоже извините меня за несдержанность.

GAA:

Замечание за уход от тематики программирования на обсуждение личных отношений. Оффтопик в этом сообщении удалён. Последующие сообщения с оффтопиком на эту тему удалены.

Кстати, пользуясь случаем (С), предлагаю Вам попробовать мои вышеупомянутые каты на Кодоворсах. Адрес Вы знаете. По крайней мере, пара-тройка из них народу весьма понравилась - бурные обсуждения и портирования на кучу других языков, а пару пока так никто и не решил

ЗЫ а по сабжу - я бы и в кучу камней добавил жестких тестов, чтобы наивная рекурсия без мемоизации не проходила.

[Geen]

Xaositect в сообщении #1328046 писал(а):

Значит, надо считать по двум взаимно простым модулям

Прошу прощения, а где можно об этом почитать? (а то столкнулся с критичной потерей точности)

[Xaositect]

Используя китайскую теорему об остатках, можно целочисленные вычисления по модулю $p_1 p_2 \dots p_k$ проводить как вычисления по модулям $p_i$ отдельно. Остаются проблемы на входе и выходе, но часто делать так проще, чем использовать полноценную длинную арифметику.

[Geen]

Xaositect в сообщении #1328134 писал(а):

часто делать так проще, чем использовать полноценную длинную арифметику

Мммм, за счёт откладывания на потом "переносов в старший разряд"?.. (хотя, боюсь это оффтоп уж совсем)

[_Ivana]

Монеты - сайт проверки прилег, но по моим ощущениям алгоритм и код должен быть правильный. На тесте из условия задачи работает нормально.

Используется синтаксис C++

int n; double m[100];

double al (double r, double a, double b) { double x=r*(r+a+b); return acos( (x-a*b)/(x+a*b) ); }

double f (double r) {
    double z=2*M_PI;
    for (int i=0; i<n; i++) z-=al(r, m[i], m[(i+1)%n]);
    return z;
}
int main() {
    cin>>n; for (int i=0; i<n; i++) cin>>m[i];
    double l=0, r=n*m[0];
    while (r-l>1E-3) { double c=(l+r)/2; if (f(c)<=0) l=c; else r=c; }
    cout<<setprecision(2)<<l;
}
 

ЗЫ имхо эту задачку и Ktina могла бы решить - программизма мало, в основном геометрия из начальной школы.