Пицца
(Время: 1 сек. Память: 16 Мб Сложность: 20%)
В данной задаче можно заметить, что каждый очередной k-й разрез пиццы может проходить через все предыдущие k-1 разрезы, что добавляет к уже имеющимся кускам еще ровно k кусков, откуда следует динамическое решение: a[k]=a[k-1]+k. Заметим, что a[0]=1 (до разрезания у нас был только один кусок). Таким образом, можно увеличивая значение k получить значение a[n], которое и будет ответом на задачу.
Если мы преобразуем a[k] к виду:
a[k] = a[k-1]+k = a[k-2]+k-1+k = a[k-3]+k-2+k-1+k = … = a[0]+1+2+…+k = 1+1+2+…+k,
то становится понятно, что для решения задачи возможно использовать формулу:
a[n] = n*(n+1)/2+1
| 
