На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
Модераторы: ElcnU, ANDLL, fatalist
  
> Вероятно проблема с точностью
    Продолжаю решать задачки CodeForces. Задача 478B.

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

    ExpandedWrap disabled
      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++(которое я написал вторым, максимально сократив) проходит отлично:

    ExpandedWrap disabled
      #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 от других участников, нет ни одного.
      Вставил вычисление второго числа полностью идентично тому, как делал в C++, получилось вот что:

      ExpandedWrap disabled
        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'


      - по-моему, это - проблема с точностью, однозначно.
        А если попробовать не делить внаглую число n*(n-1) на 2, а вставить нанопроверку:
        ExpandedWrap disabled
          var x;
          if( n-чёт ) x = n/2*(n-1);
          else x = (n-1)/2*n;
        ?
          Цитата Славян @
          А если попробовать не делить внаглую число n*(n-1) на 2, а вставить нанопроверку:


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

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

          ExpandedWrap disabled
            var x = (n-m+1);
            var outmax = (x*x-x)/2;


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

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


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

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

            ExpandedWrap disabled
              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-м тесте.

            Добавлено
            отчёт точно такой же, как и ранее(см выше).
              Цитата ya2500 @
              Продолжаю решать задачки CodeForces. Задача 478B.

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

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


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

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

              499500000000 499000500499499970
              Сообщение отредактировано: Cfon -
                ya2500, если немножко соптимизировать последний пример, то будет так:
                ExpandedWrap disabled
                  nn1 = n1*(n1-1)/2; // ещё здесь можно бит сэкономить
                  //nn2 = nn1 + n1;
                  outmin = nn1*m + n1*m2;
                n2, nn2 и m1 не нужны. Да и m2 не нужна, в итоге.
                  Цитата Cfon @
                  А меня тот же вывод что у участника :D


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

                  Цитата Славян @
                  n2, nn2 и m1 не нужны. Да и m2 не нужна, в итоге.


                  Это outmin, с ним всё в порядке. До сих пор фэйлился только максимум(второе выводимое число).
                    Цитата ya2500 @
                    Цитата Cfon @
                    А меня тот же вывод что у участника :D

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

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


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

                      Добавлено
                      Если так, то можно считать вопрос решённым.
                      0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                      0 пользователей:


                      Рейтинг@Mail.ru
                      [ Script execution time: 0,0325 ]   [ 15 queries used ]   [ Generated: 29.03.24, 05:45 GMT ]