Вероятно проблема с точностью -> Форум на Исходниках.RU [Powered by Invision Power Board]

Версия для печати
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум на Исходниках.RU > JavaScript, DOM/DHTML > Вероятно проблема с точностью

Автор: ya2500 18.08.19, 14:55

Продолжаю решать задачки CodeForces. Задача 478B.

Решение на JavaScript(которое я написал первым) фэйлится:

<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>

var inp = readline().split(" ");

var n = parseInt(inp[0]);

var m = parseInt(inp[1]);

var x = (n-m+1);

var outmax = (x*x-x)/2;

var ost = n%m;

var m1 = m-ost;

var m2 = ost;

var n1 = (n-ost)/m;

var n2 = n1+1;

var nn11 = (n1*n1-n1)/2

var nn22 = (n2*n2-n2)/2

var outmin = nn11*m1 + nn22*m2;

print(outmin+" "+outmax);

Решение на MS VC++(которое я написал вторым, максимально сократив) проходит отлично:

<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>

#include<iostream>

using namespace std;

int main()

{

long long n,m;

cin>>n>>m;

cout<<m*(n/m-1)*(n/m)/2+(n%m)*(n/m) <<" "<<(n-m+1)*(n-m)/2<<endl;

}

Вот тест, на котором фэйлится Java Script:

Цитата

Ввод
1000000000 1000000
Вывод участника
499500000000 499000500499499970
Ответ жюри
499500000000 499000500499500000

по-моему, тут дело в точности И я не нашёл, как это лечится на Java Script. Решений этой задачи на Java Script от других участников, нет ни одного.

Автор: ya2500 18.08.19, 15:38

Вставил вычисление второго числа полностью идентично тому, как делал в C++, получилось вот что:

<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>

var inp = readline().split(" ");

var n = parseInt(inp[0]);

var m = parseInt(inp[1]);

var x = (n-m+1);

var outmax = (x*x-x)/2;

var ost = n%m;

var m1 = m-ost;

var m2 = ost;

var n1 = (n-ost)/m;

var n2 = n1+1;

var nn11 = (n1*n1-n1)/2;

var nn22 = (n2*n2-n2)/2;

var outmin = nn11*m1 + nn22*m2;

print(outmin+" "+(n-m+1)*(n-m)/2);

И, что интересно, тот тест(11-й) прошло, но на следующем(12-м) зафейлилось:

Цитата

Test: #11, время: 15 мс., память: 128 КБ, код возврата: 0, код возврата чекера: 0, вердикт: OK
Ввод
1000000000 1000000
Вывод
499500000000 499000500499500000
Ответ
499500000000 499000500499500000
Протокол тестирования
ok 2 number(s): "499500000000 499000500499500000"

Цитата

Test: #12, время: 30 мс., память: 144 КБ, код возврата: 0, код возврата чекера: 1, вердикт: WRONG_ANSWER
Ввод
1000000000 32170
Вывод
15541930838100 499967831017438340
Ответ
15541930838100 499967831017438365
Протокол тестирования
wrong answer 2nd numbers differ - expected: '499967831017438365', found: '499967831017438340'

- по-моему, это - проблема с точностью, однозначно.

Автор: Славян 18.08.19, 18:27

А если попробовать не делить внаглую число n*(n-1) на 2, а вставить нанопроверку:

<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>

var x;

if( n-чёт ) x = n/2*(n-1);

else x = (n-1)/2*n;

Автор: ya2500 18.08.19, 19:09

Цитата Славян @ 18.08.19, 18:27

А если попробовать не делить внаглую число n*(n-1) на 2, а вставить нанопроверку:

Выводятся два числа. Первое - минимум и с ним проблем пока не было. Второе - максимум и именно с ним возникают проблемы.

Ранее максимум вычислялся так:

<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>

var x = (n-m+1);

var outmax = (x*x-x)/2;

- и фейлилось на 11-м тесте. Сейчас максимум вычисляется непосредственно в операторе print, так:

<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>

(n-m+1)*(n-m)/2

- и фэйлится на 12-м тесте.

НО, да - совет, пожалуй, можно бы и попробовать. И сначала разделить чётный множитель, а потом умножить на нечётный.

Автор: ya2500 18.08.19, 19:14

Сделал:

<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>

var inp = readline().split(" ");

var n = parseInt(inp[0]);

var m = parseInt(inp[1]);

var outmax = 0;

var x1 = (n-m+1);

var x2 = (n-m);

if(x1%2 == 0)

{

outmax = x1/2;

outmax *= x2;

}

else

{

outmax = x2/2;

outmax *= x1;

}

var ost = n%m;

var m1 = m-ost;

var m2 = ost;

var n1 = (n-ost)/m;

var n2 = n1+1;

var nn11 = (n1*n1-n1)/2;

var nn22 = (n2*n2-n2)/2;

var outmin = nn11*m1 + nn22*m2;

print(outmin+" "+outmax);

- фейлится на 12-м тесте.

Добавлено 18.08.19, 19:16
отчёт точно такой же, как и ранее(см выше).

Автор: Cfon 19.08.19, 11:19

Цитата ya2500 @ 18.08.19, 14:55

Продолжаю решать задачки CodeForces. Задача 478B.

Вот тест, на котором фэйлится Java Script:

Цитата

Ввод
1000000000 1000000
Вывод участника
499500000000 499000500499499970
Ответ жюри
499500000000 499000500499500000

А меня тот же вывод что у участника

499500000000 499000500499499970

Автор: Славян 19.08.19, 16:46

ya2500, если немножко соптимизировать последний пример, то будет так:

<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>

nn1 = n1*(n1-1)/2; // ещё здесь можно бит сэкономить

//nn2 = nn1 + n1;

outmin = nn1*m + n1*m2;

n2, nn2 и m1 не нужны. Да и m2 не нужна, в итоге.

Автор: ya2500 20.08.19, 22:40

Цитата Cfon @ 19.08.19, 11:19

А меня тот же вывод что у участника

А вот реализация на C++ даёт тот же ответ, что и у жюри. Вопрос в том, как такой точности добиться на JavaScript.

Цитата Славян @ 19.08.19, 16:46

n2, nn2 и m1 не нужны. Да и m2 не нужна, в итоге.

Это outmin, с ним всё в порядке. До сих пор фэйлился только максимум(второе выводимое число).

Автор: Cfon 21.08.19, 07:13

Цитата ya2500 @ 20.08.19, 22:40

Цитата Cfon @ 19.08.19, 11:19

А меня тот же вывод что у участника

А вот реализация на C++ даёт тот же ответ, что и у жюри. Вопрос в том, как такой точности добиться на JavaScript.

У меня твой второй вариант дает результат жюри
499500000000 499000500499500000

Автор: ya2500 22.08.19, 11:16

Цитата Cfon @ 21.08.19, 07:13

У меня твой второй вариант дает результат жюри

Ну тогда проблема на их стороне: для прохождения тестов приходится отправлять код им, а он не проходит.

Добавлено 22.08.19, 11:17
Если так, то можно считать вопрос решённым.