Зоопарк

Рассмотрим сначала алгоритм, частично решающий данную задачу. Осуществим перебор всех возможных различных троек видов животных и для каждой такой тройки посчитаем количество возможных способов выбора трех животных именно этих видов. Тогда ответ на задачу будет вычисляться как сумма всех таких значений. Пусть i, j и k - номера видов животных, количество выборок из которых мы хотим вычислить. Тогда a_i, a_j и a_k - соответствующие количественные характеристики этих видов (a_i - количество животных i-го вида). Искомое значение количества возможных троек животных для данных видов будет вычисляться по формуле: s_ijk = a_i*a_j*a_k. Алгоритмическая реализация вышеописанного:

  //чтение данных
  read(n)
  for i=1..n read(a[i])
  //перебор всех возможных троек типов без повторений
  sum=0
  for i=1..n-2
    for j=1..n-1
      for k=1..n
        sum = sum+a[i]*a[j]*a[k]     
  //вывод ответа
  write(sum)

К сожалению, такая простая реализация, как уже говорилось ранее, не является совершенной. Дело в том, что при значениях n, близких к 1000 мы получим более 150 млн. операций в теле цикла. Такой объем вычислений не может быть выполнен в установленных временных ограничениях. Помимо этого, следует еще учесть, что ответ может быть достаточно большим числом и переменную sum следует описать 8-байтовым целым типом, либо использовать большой вещественный тип.

Рассмотрим теперь правильное решение, основанное на алгоритме, который описан выше. Идея заключается в оптимизации вычислений искомой суммы, которую мы вычисляли в тройном цикле. Здесь можно обойтись двойным циклом, если заметить, что в искомой сумме каждый элемент a_j*a_k можно вынести за скобки и получить выражение (a₁ + a₂ + ... + a_j-1)*a_j*a_k = s_j-1*a_j*a_k. Значения s_i (сумма элементов с 1-го до i-го) легко определить линейным алгоритмом в процессе чтения данных. Описанная идея формализуется следующим алгоритмическим кодом:

  s[0]=0
  for i=1..n{
    read(a[i])
    s[i] = s[i-1]+a[i]
  }
  sum=0
  for j=2..n-1
    for k=j+1..n
      sum = sum + s[j-1]*a[j]*a[k]
  write(sum)

Наилучшим решением данной задачи является динамическая линейная реализация. Пусть d[k][m] - количество возможных способов выбора m (m=1..3) животных различных видов среди первых k представленных в зоопарке видов. Мы знаем, что d[0][m]=0 (невозможно выбрать положительное количество животных из ничего), постараемся вычислить d[k][m] через меньшие значения k (оказывается, что это возможно сделать через предыдущие вычисления k-1). Действительно, d[k][1] = d[k-1][1] + a[k] (выбор одного животного может быть сделан либо среди значений, меньших k, либо среди k-го вида). Далее, d[k][2] = d[k-1][2] + d[k-1][1]*a[k] (при выборе двух животных оба они могут быть из предыдущих видов, либо одно из них может быть k-го вида). Аналогично, d[k][3] = d[k-1][3] + d[k-1][2]*a[k]. Увеличивая значение k от 1 до n в d[n][3] мы получим ответ на задачу. Данное решение не только самое короткое, но самое быстрое. Алгоритмическая реализация:

  int64 d[0..1000][1..3]={0..0}

  read(n)
  for k=1..n{
    read(x)
    d[k][1] = d[k-1][1]+x
    d[k][2] = d[k-1][2]+d[k-1][1]*x
    d[k][3] = d[k-1][3]+d[k-1][2]*x
  }
  write(d[n][3])

Следует заметить, что использование массива здесь вовсе необязательно, т.к. все вычисления на k-м шаге реализуются с использованием значений, вычисленных на предыдущем шаге. Однако, реализация с использованием массива более проста.

[Обсуждение] [Все попытки] [Задача]