Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[18.118.200.197] |
|
Сообщ.
#1
,
|
|
|
Продолжаю решать задачки CodeForces. Задача 478B.
Решение на JavaScript(которое я написал первым) фэйлится: 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++(которое я написал вторым, максимально сократив) проходит отлично: #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 от других участников, нет ни одного. |
Сообщ.
#2
,
|
|
|
Вставил вычисление второго числа полностью идентично тому, как делал в C++, получилось вот что:
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' - по-моему, это - проблема с точностью, однозначно. |
Сообщ.
#3
,
|
|
|
А если попробовать не делить внаглую число n*(n-1) на 2, а вставить нанопроверку:
var x; if( n-чёт ) x = n/2*(n-1); else x = (n-1)/2*n; |
Сообщ.
#4
,
|
|
|
Цитата Славян @ А если попробовать не делить внаглую число n*(n-1) на 2, а вставить нанопроверку: Выводятся два числа. Первое - минимум и с ним проблем пока не было. Второе - максимум и именно с ним возникают проблемы. Ранее максимум вычислялся так: var x = (n-m+1); var outmax = (x*x-x)/2; - и фейлилось на 11-м тесте. Сейчас максимум вычисляется непосредственно в операторе print, так: (n-m+1)*(n-m)/2 - и фэйлится на 12-м тесте. НО, да - совет, пожалуй, можно бы и попробовать. И сначала разделить чётный множитель, а потом умножить на нечётный. |
Сообщ.
#5
,
|
|
|
Сделал:
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-м тесте. Добавлено отчёт точно такой же, как и ранее(см выше). |
Сообщ.
#6
,
|
|
|
Цитата ya2500 @ Продолжаю решать задачки CodeForces. Задача 478B. Вот тест, на котором фэйлится Java Script: Цитата Ввод 1000000000 1000000 Вывод участника 499500000000 499000500499499970 Ответ жюри 499500000000 499000500499500000 по-моему, тут дело в точности И я не нашёл, как это лечится на Java Script. Решений этой задачи на Java Script от других участников, нет ни одного. А меня тот же вывод что у участника 499500000000 499000500499499970 |
Сообщ.
#7
,
|
|
|
ya2500, если немножко соптимизировать последний пример, то будет так:
nn1 = n1*(n1-1)/2; // ещё здесь можно бит сэкономить //nn2 = nn1 + n1; outmin = nn1*m + n1*m2; |
Сообщ.
#8
,
|
|
|
Цитата Cfon @ А меня тот же вывод что у участника А вот реализация на C++ даёт тот же ответ, что и у жюри. Вопрос в том, как такой точности добиться на JavaScript. Цитата Славян @ n2, nn2 и m1 не нужны. Да и m2 не нужна, в итоге. Это outmin, с ним всё в порядке. До сих пор фэйлился только максимум(второе выводимое число). |
Сообщ.
#9
,
|
|
|
Цитата ya2500 @ Цитата Cfon @ А меня тот же вывод что у участника А вот реализация на C++ даёт тот же ответ, что и у жюри. Вопрос в том, как такой точности добиться на JavaScript. У меня твой второй вариант дает результат жюри 499500000000 499000500499500000 |
Сообщ.
#10
,
|
|
|
Цитата Cfon @ У меня твой второй вариант дает результат жюри Ну тогда проблема на их стороне: для прохождения тестов приходится отправлять код им, а он не проходит. Добавлено Если так, то можно считать вопрос решённым. |