В городском зоопарке содержатся животные n разных видов. Для участия в международной выставке «Три твари» зоопарк должен представить трех животных различных видов.
Требуется написать программу, которая вычислит число способов выбрать трех животных для участия в выставке.
Например, если в зоопарке два медведя, тигр, лев и пингвин, то есть семь способов выбрать трех животных:
    первый медведь, тигр и лев;
    первый медведь, тигр и пингвин;
    первый медведь, лев и пингвин;
    второй медведь, тигр и лев;
    второй медведь, тигр и пингвин;
    второй медведь, лев и пингвин;
    тигр, лев и пингвин.
Входной текстовый файл INPUT.TXT содержит в первой строке натуральное число n – количество видов животных в городском зоопарке (1 ≤ n ≤ 1000). Во второй строке через пробел записаны n натуральных чисел – количество животных соответствующего вида. Число животных каждого вида не превышает 1000.
Выходной текстовый файл OUTPUT.TXT должен содержать одно число – количество способов выбрать трех животных для международной выставки.
Для выполнения программы максимальное время выполнения составляет 0,5 секунд, память ограничена в 16 мегабайт.
Анализ задачи
Так как все данные автоматически вводятся системой тестирования, то нет необходимости реализовать проверку ввода.
Данная задача явно подразумевает использование комбинаторики. Самое простым решением было бы найти все возможные сочетания трех разных видов животных без учета порядка расположения этих видов. Однако количество видов животных может достигать 1000, поэтому количество всевозможных комбинаций становится очень большим, поэтому используем другой подход для решения данной задачи.
Будем использовать методику динамического программирования. Его суть состоит в том, чтобы разбить одну большую задачу на менее сложные подзадачи, затем решив их, использовать полученные результаты для решения основной задачи.
В данном случае мы будем считывать количество животных одного вида и обновлять данные для количества комбинаций. Главным будет то, что мы также будем считать количество комбинаций ещё для ситуаций, где нам бы потребовалось выставить на выставку один и два вида животных.
Функциональные требования: программа должна давать однозначный верный ответ на заданные входные данные, ввод и вывод данных осуществляется через команды консоли.
Нефункциональные требования: время выполнения программы ограничено 0,5 секунды. Память ограничена 16 мегабайтами.
Требования к входным данным: все числа натуральные и не превышают 1000.
Формат входных данных:
    Количество видов – число формата int;
    Количество особей каждого вида – число формата int;
Формат выходных данных:
    Количество сочетаний — число формата int64
Худший расклад: количество видов 1000, и особей в каждом виде тоже 1000, уже понятно, что количество комбинаций будет невероятно большим, поэтому заранее будем использовать int64.
Разработка алгоритма
Записываем количество животных каждого вида в одним массив. Затем последовательно идём по массиву и пересчитываем количество комбинаций. Для вычисления комбинаций 1 вида получаем следующую формулу (1)
    C_1=C_1+k_i
где С1 – количество комбинаций для 1 вида,
ki – количество животных текущего вида.
Для вычисления комбинаций 2 видов получаем следующую формулу (2)
    C_2=C_2+С1×ki

где С2 – количество комбинаций для 2 видов,
Для вычисления комбинаций 3 видов формула будет иметь вид (3)
    C_3=C_3+С2×ki

где С3 – количество комбинаций для 3 видов.
Реализация
Листинг программы прикреплён к приложению (прил. С).
Для ввода и вывода использовались стандартные консольные методы.
Решение задачи не потребовало написания дополнительных методов или классов.
Тестирование
Результаты тестирования в системе acmp представлены ниже (рис 2.1). Номер решения 8451632.

Результат тестирования