ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1001. Обратный корень

Newton Raphson instead of sqrt() but getting WA on test case 2
Послано thanos 5 авг 2017 18:22
#include<iostream>
#include <iomanip>
#include<vector>

int main(){
    long long num;
    std::vector<double> v;
    int count=0;
    while(std::cin>>num){
        if(num==0){
            v.push_back(num);
            }
    else{
    int i=0;
    double n=num/10;
    while(i<10000){
        n=n-(n*n-num)/(2*n);
        i++;
    }
    v.push_back(n);
    }

    }
    for(int i=v.size()-1;i>=0;i--)
        std::cout<<std::fixed<<std::setprecision(4)<<v[i]<<std::endl;
    return 0;
}
Re: Newton Raphson instead of sqrt() but getting WA on test case 2
Послано Mahilewets 5 авг 2017 19:56
Suppose you have no WA.

Then you might have 15000+ square roots by 10000 iterations each

(If pay attention there are maximum 256KB of numbers)

TLE for sure
Re: Newton Raphson instead of sqrt() but getting WA on test case 2
Послано thanos 6 авг 2017 10:30
Yup. I just realized it. But I think it converges to 4 decimal places much, much before 10000 iterations (say, like 300-400). Thanks for the help :)