На форумі обговорюються лише питання, пов'язані з олімпіадою
Ви не зайшли.
В задаче Garden 365 пример приведен не совсем корректно. Точность вывода нигде не задается. Поэтому ориентировался на вывод в примере. При точности вывода 10 знаков не проходят 5 тестов. Заменив точность вывода на 15 знаков проходят все, кроме одного.
Поза форумом
jurij написав:
В задаче Garden 365 пример приведен не совсем корректно. Точность вывода нигде не задается. Поэтому ориентировался на вывод в примере. При точности вывода 10 знаков не проходят 5 тестов. Заменив точность вывода на 15 знаков проходят все, кроме одного.
На самом деле рамки точности здесь установлены достаточно лояльно. Так, при использовании типа long double (в C++) достаточно вывода шести знаков после десятичной точки. С double же всегда будет выходить весьма неприятная ситуация, как минимум, с одним тестом т.к. этот тип не расчитан на такую точность хранения особенно больших чисел.
Поза форумом
В задаче Traceroute я прошел алгоритмом Дейкстры от точки Б к точке А, запомнив все расстояния не превышающие расстояния до вершин по кратчайшему пути. К строк по N значений.
Затем из точки А в точку Б алгоритмом Дейкстры, причем запоминал расстояния до всех вершин не превышающие расстояние до следующей вершины из кратчайшего пути как без учета временно не работающей линии, так и с учетом. 2 строки по N значений. Суммировал расстояние к вершинам из точки А (без учета временно не работающей линии) и из точки Б, находил минимум и выводил его. Брал сохраненный результат с учетом временно не работающей линии и продолжал далее. Таким образом мне не приходилось все время начинать с точки А.
Відредаговано jurij (2014-02-08 19:34:30)
Поза форумом
И сколько баллов по задаче?
Поза форумом
adamant написав:
И сколько баллов по задаче?
К сожалению только 50. 2 неверных ответа. Но алгоритм, я думаю оптимальный.
Поза форумом
OArtem3 написав:
Никто не подскажет, что за проблема с 10 тестом в последней задаче? Ни у кого такого не было? У меня в ней сжатие координат + 0-1bfs.
У меня только в 15 тесте WA. В 10 все в порядке 3 балла 0,01 сек.
Поза форумом
adamant написав:
jurij написав:
В задаче Garden 365 пример приведен не совсем корректно. Точность вывода нигде не задается. Поэтому ориентировался на вывод в примере. При точности вывода 10 знаков не проходят 5 тестов. Заменив точность вывода на 15 знаков проходят все, кроме одного.
На самом деле рамки точности здесь установлены достаточно лояльно. Так, при использовании типа long double (в C++) достаточно вывода шести знаков после десятичной точки. С double же всегда будет выходить весьма неприятная ситуация, как минимум, с одним тестом т.к. этот тип не расчитан на такую точность хранения особенно больших чисел.
В том то и дело, что 10 знаков не достаточно. Считал то я с long double и правильно, раз при более точном выводе в 15 знаков тесты проходят.
Алгоритм не такой как у Вас. Не додумался погуглить. Методом приближенных вычислений с последовательным увеличением точности до неизменного long double.
Поза форумом
jurij написав:
В том то и дело, что 10 знаков не достаточно. Считал то я с long double и правильно, раз при более точном выводе в 15 знаков тесты проходят.
Алгоритм не такой как у Вас. Не додумался погуглить. Методом приближенных вычислений с последовательным увеличением точности до неизменного long double.
Вот такой код проходит все тесты. По всей видимости, проблема не в точности вывода, а в точности подсчёта ответа.
int main()
{
long double a,b,c,d;
cin>>a>>b>>c>>d;
long double p=(a+b+c+d)/2;
cout<<setprecision(6)<<fixed<<sqrt(p-a)*sqrt(p-b)*sqrt(p-c)*sqrt(p-d)<<endl;
return 0;
}Поза форумом
adamant написав:
jurij написав:
В том то и дело, что 10 знаков не достаточно. Считал то я с long double и правильно, раз при более точном выводе в 15 знаков тесты проходят.
Алгоритм не такой как у Вас. Не додумался погуглить. Методом приближенных вычислений с последовательным увеличением точности до неизменного long double.Вот такой код проходит все тесты. По всей видимости, проблема не в точности вывода, а в точности подсчёта ответа.
Код:
int main() { long double a,b,c,d; cin>>a>>b>>c>>d; long double p=(a+b+c+d)/2; cout<<setprecision(6)<<fixed<<sqrt(p-a)*sqrt(p-b)*sqrt(p-c)*sqrt(p-d)<<endl; return 0; }
Значит у меня округленный до 15 знаков вариант ближе к правильному ответу и поэтому проходит, чем округленный до 10 знаков который не прошел. Все-равно получается точность вывода имеет значение.
Разобрался. Я исходил из точности 10 значащих цифр. А проверялось по точности 6 знаков после запятой, то есть по абсолютной погрешности. Поэтому добавив еще несколько знаков, я проходил.
Відредаговано jurij (2014-02-10 18:20:38)
Поза форумом