Подготовка

Мишу из школы направляют на региональную олимпиаду по информатике и выдали примеры задач для подготовки. Он их делает на Питоне, а потом мы сложные случаи разбираем. Задачи проверяются на сервере, который работает с 9 утра до 9 вечера. Ограничения для всех задач: по времени - 2 секунды, по памяти - 256 мегабайт. Задачи очень разные! Есть элементарные:

Задано четыре числа. Требуется разбить их на две пары, чтобы сумма произведений в этих парах была максимальной. Например, для чисел 2,3,4,5 надо вывести 26 (2*3+4*5).

А бывают архисложные, требующие подключения серьёзного математического аппарата:

Для целого положительного числа от 1 до 1000 требуется найти число способов представить его в виде суммы нечётных слагаемых. Порядок слагаемых неважен. Например, для числа 6 надо вывести 4. Сами разбиения выводить не надо:
[1+1+1+1+1+1], [3+1+1+1], [3+3], [5+1]

Я сначала решил "в лоб" - прямым перебором, используя Set для фильтрации. Потом ускорил в несколько сотен раз, отказавшись от Set. Это позволило мне обнаружить, что происходит переполнение для больших чисел. Посему мне пришлось заменить long на BigInteger, замедлив программу раза в два.

fun count(array: IntArray, size: Int): BigInteger {
  var count = BigInteger.ONE
  val size2 = size - 2
  if (size > 2 && array[size - 1] == 1 && array[size2] == 1) {
    array[0] += 2
    count = count.plus(count(list, array, size2))
    array[0] -= 2
    var index = 0
    while (++index < size2) {
      if (array[0] == array[index]) continue
      if (array[0] == array[index] + 2) {
        array[index] += 2
        count = count.plus(count(list, array, size2))
        array[index] -= 2
      }
      break
    }
  }
  return count
}

Тут стало очевидно, что после 170 мы перестаём укладываться в две секунды и подсчёт ответа для 400 занял более двух дней:

in: 100; out: 444793; time: 21 ms
in: 200; out: 487067746; time: 7958 ms
in: 300; out: 114872472064; time: 1873429 ms
in: 400; out: 11962163400706; time: 196301147 ms

Написал код для вывода комбинаций и пытаемся анализировать, чтобы для получившейся выше рекурсивной функции вывести формулу, ибо полный перебор - это уже перебор. 8)