Разбор олимпиадной задачи — Загадка

  • В этой теме 0 ответов, 1 участник, последнее обновление 4 месяца, 3 недели назад сделано Васильев Владимир Сергеевич.
Просмотр 0 веток ответов
  • Автор
    Сообщения
    • #6414
      @admin
      StudLance.ru

      Условие задачи взято с сайта acmp.ru (Время: 1 сек. Память: 16 Мб Сложность: 18%):

      Петя и Катя – брат и сестра. Петя – студент, а Катя – школьница. Петя помогает Кате по математике. Он задумывает два натуральных числа X и Y (X,Y≤1000), а Катя должна их отгадать. Для этого Петя делает две подсказки. Он называет сумму этих чисел S и их произведение P. Помогите Кате отгадать задуманные Петей числа.

      Входные данные

      Входной файл INPUT.TXT содержит два натуральных числа S и P, разделенных пробелом.

      Выходные данные

      В выходной файл OUTPUT.TXT выведите два числа Х и Y, загаданные Петей. Числа следует вывести в порядке неубывания своих значений, разделенные пробелом.

      Примеры

      INPUT.TXT OUTPUT.TXT
      1 4 4 2 2
      2 5 6 2 3

      Разбор решения задачи

      У этой задачи есть множество подходов к решению — это хорошая задача для получения первого опыта в анализе алгоритмов. Наиболее простой — перебрать все возможные X и Y в заданном диапазоне (натуральное число до 1000) и проверить выполнение условия:

      #include <fstream>
      
      using namespace std;
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        int sum, prod;
      
        ifst >> sum >> prod;
      
        for (int x = 0; x < 1000; ++x) {
          for (int y = 0; y < 1000; ++y) {
            if (x + y == sum && x*y == prod) {
              ofst << x << " " << y;
              return 0;
            }
          }
        }
      }

      Вычислительная сложность такого решения — O(n^2) и оно сработает только для небольших N. Однако, его можно ускорить — ведь мы можем выразить y = sum - x, значит перебирать все возможные значения y нет необходимости:

      #include <fstream>
      
      using namespace std;
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        int sum, prod;
      
        ifst >> sum >> prod;
      
        for (int x = 0; x < 1000; ++x) {
          int y = sum - x;
          if (x*y == prod) {
            ofst << x << " " << y;
            break;
          }
        }
      }

      Вычислительная сложность такого варианта решения — O(n). Это гораздо лучше, но мы можем еще ускорить решение — для этого нам потребуются знания алгебры седьмого класса школы. Нам даны два уравнения, запишем их в систему и решим:

      $$
      \begin{cases} x + y = sum \\
      x * y = prod \end{cases} \\ \Rightarrow (sum — y) * y = prod \\ \Rightarrow y^2 — y*sum + prod = 0$$

      В результате мы получили квадратное уравнение. Вычислим дискриминант и найдем корни как мы это уже делали в уроке, посвященном Условному оператору в С++. В нашем случае коэффициенты уравнения уже известны (a = 1, b = -sum, c = prod) и мы точно знаем что есть корень, причем положительный. Решение целиком может выглядеть так:

      #include <fstream>
      #include <cmath>
      
      using namespace std;
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        int sum, prod, x, y;
      
        ifst >> sum >> prod;
      
        int a = 1, b = -sum, c = prod;
      
        double discriminant = b*b - 4*a*c;
      
        if (discriminant < 0.000001)
          x = int(-b / 2*a);
        else {
          x = int((-b + sqrt(discriminant)) / (2*a));
        }
      
        y = sum - x;
      
        ofst << min(x, y) << " " << max(x, y);
      }

      Вычислительная сложность этого решения O(1). Даже для такого ебольшого диапазона значений X и Y мы ускорили наше первое решение примерно в миллион раз.

      StudLance.ru

Просмотр 0 веток ответов
  • Для ответа в этой теме необходимо авторизоваться.
×