Окружности

Если записать очевидные решения для N≤3, то можно ошибочно предположить, что ответом служит 2^N, но для N=4 мы можем видеть, что нельзя получить более 14 областей. Здесь используется другой подход. Действительно, мы можем вести построение так, что при наличии K окружностей мы всегда можем добавить еще одну так, что она пересечет все окружности и образует еще 2*K новых полуплоскостей. Так, на каждом шаге к ранее имеющимся полуплоскостям добавляется очередной член арифметической прогрессии: 2, 4, 6, 8, 10 … Ответ связан с суммой элементов данной прогрессии. Данную сумму можно вычислять либо по формуле N²-N+2, либо можно суммировать данные значения в цикле. Следует заметить, что единственным исключением из этого правила является случай при N=0, где мы имеем одну плоскость, а не две.

В простейшей реализации мы получаем следующий алгоритм:

  read(n)
  if(n=0) write(1) 
     else write(n*n-n+2)

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