Форум Всеукраїнської інтернет-олімпіади NetOI


На форумі обговорюються лише питання, пов'язані з олімпіадою

Ви не зайшли.

#26 2014-02-08 18:27:32

jurij
Новий користувач
Зареєстрований: 2009-01-23
Повідомлень: 40

Re: Разбор задач

В задаче Garden 365 пример приведен не совсем корректно. Точность вывода нигде не задается. Поэтому ориентировался на вывод в примере. При точности вывода 10 знаков не проходят 5 тестов. Заменив точность вывода на 15 знаков проходят все, кроме одного.

Поза форумом

 

#27 2014-02-08 19:04:14

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Разбор задач

jurij написав:

В задаче Garden 365 пример приведен не совсем корректно. Точность вывода нигде не задается. Поэтому ориентировался на вывод в примере. При точности вывода 10 знаков не проходят 5 тестов. Заменив точность вывода на 15 знаков проходят все, кроме одного.

На самом деле рамки точности здесь установлены достаточно лояльно. Так, при использовании типа long double (в C++) достаточно вывода шести знаков после десятичной точки. С double же всегда будет выходить весьма неприятная ситуация, как минимум, с одним тестом т.к. этот тип не расчитан на такую точность хранения особенно больших чисел.

Поза форумом

 

#28 2014-02-08 19:28:15

jurij
Новий користувач
Зареєстрований: 2009-01-23
Повідомлень: 40

Re: Разбор задач

В задаче Traceroute я прошел алгоритмом Дейкстры от точки Б к точке А, запомнив все расстояния не превышающие расстояния до вершин по кратчайшему пути. К строк по N значений.
Затем из точки А в точку Б алгоритмом Дейкстры, причем запоминал расстояния до всех вершин не превышающие расстояние до следующей вершины из кратчайшего пути как без учета временно не работающей линии, так и с учетом. 2 строки по N значений. Суммировал расстояние к вершинам из точки А (без учета временно не работающей линии) и из точки Б, находил минимум и выводил его.  Брал сохраненный результат с учетом  временно не работающей линии и продолжал далее. Таким образом мне не приходилось  все время начинать с точки А.

Відредаговано jurij (2014-02-08 19:34:30)

Поза форумом

 

#29 2014-02-08 21:15:19

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Разбор задач

И сколько баллов по задаче?

Поза форумом

 

#30 2014-02-08 22:03:11

jurij
Новий користувач
Зареєстрований: 2009-01-23
Повідомлень: 40

Re: Разбор задач

adamant написав:

И сколько баллов по задаче?

К сожалению только 50. 2 неверных ответа. Но алгоритм, я думаю оптимальный.

Поза форумом

 

#31 2014-02-08 22:19:58

jurij
Новий користувач
Зареєстрований: 2009-01-23
Повідомлень: 40

Re: Разбор задач

OArtem3 написав:

Никто не подскажет, что за проблема с 10 тестом в последней задаче? Ни у кого такого не было? У меня в ней сжатие координат + 0-1bfs.

У меня только в 15 тесте WA.  В 10 все в порядке 3 балла 0,01 сек.

Поза форумом

 

#32 2014-02-08 22:30:13

jurij
Новий користувач
Зареєстрований: 2009-01-23
Повідомлень: 40

Re: Разбор задач

adamant написав:

jurij написав:

В задаче Garden 365 пример приведен не совсем корректно. Точность вывода нигде не задается. Поэтому ориентировался на вывод в примере. При точности вывода 10 знаков не проходят 5 тестов. Заменив точность вывода на 15 знаков проходят все, кроме одного.

На самом деле рамки точности здесь установлены достаточно лояльно. Так, при использовании типа long double (в C++) достаточно вывода шести знаков после десятичной точки. С double же всегда будет выходить весьма неприятная ситуация, как минимум, с одним тестом т.к. этот тип не расчитан на такую точность хранения особенно больших чисел.

В том то и дело, что 10 знаков не достаточно. Считал то я с  long double и правильно, раз при более точном выводе в 15 знаков тесты проходят.
Алгоритм не такой как у Вас. Не додумался погуглить. Методом приближенных вычислений с последовательным увеличением точности до неизменного long double.

Поза форумом

 

#33 2014-02-09 14:56:14

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Разбор задач

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;
}

Поза форумом

 

#34 2014-02-10 15:21:41

jurij
Новий користувач
Зареєстрований: 2009-01-23
Повідомлень: 40

Re: Разбор задач

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)

Поза форумом

 

Нижній колонтитул

Powered by Likt
© Copyright 2002–2009 Likt