Блог пользователя OnlyVim

Проверка на квадрат
Автор OnlyVim, 7 лет назад, По-русски

Доброй ночи/рассвета/утра/дня/заката/вечера/ночи, Codeforces! Сегодня я заметил, что у меня задача С в Educational Codeforces Round 42 не прошла из-за теста 12334567891. Проверив свою программу я понял, что проблема была в проверке числа на квадрат, а именно if (sqrt(n) * sqrt(n) == n) это проверку я заменил на if (int(sqrt(n)) == sqrt(n)) и оно прошло все тесты. Можете сказать почему первая проверка не есть правильной.

Моё решение: http://codeforces.me/contest/962/submission/37171806

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Обе проверки плохие, но во второй просто получаем погрешность в вычислении sqrt(n) и ничего с этим не делаем, а в первой мы ее делаем еще и в два раза больше из-за умножения.

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Спасибо. А как можно проверять без погрешности, если это возможно.

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +39 Проголосовать: не нравится

      Можно так:

      int sqr = sqrt(n);
while (sqr * sqr > n) sqr--;
while (sqr * sqr < n) sqr++;
if(sqr * sqr == n) cout << "Square";
      → Ответить
      • »
        »
        »
        »
        7 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится -56 Проголосовать: не нравится

        int n = 2147483647; // WA

        int n = 2147483646; // TLE

        UPD: https://ideone.com/Wl12Mf

        → Ответить
        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится +18 Проголосовать: не нравится

          Никто не запрещал использовать long long, если есть необходимость

          → Ответить
      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        понятно, что тема старая, но вот зачем использовать 2 цикла while не совсем понятно.. вообще вроде и без них всегда работает(если есть примеры где не работает, напишите их пожалуйста), а так можно использовать llrint:

        int sqr = llrint(sqrt(n));

        → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Ещё можно двоичным поиском.

      → Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Все стандартные функции процессора (в том числе и sqrt) имеют точность 10^(-14), чего более чем хватает для чисел до миллиарда.

→ Ответить