Задача №115429. Колония бактерий
Ученые обнаружили новый вид бактерии и начали проводить эксперименты для его изучения.
В одном из экспериментов они поместили колонию бактерий на бесконечное клетчатое поле, и оказалось, что каждую секунду она расширяется. В каждую чётную секунду колония расширяется в восьми направлениях, то есть занимает клетки, соседние с занятыми по стороне и диагонали, если они ещё не заняты, а в нечётную – только в четырёх направлениях, в клетки, соседние с занятыми по стороне.
Помогите учёным определить, сколько клеток занимает колония бактерий в \(k\)-ю секунду эксперимента, если она была помещена на клетчатое поле в первую секунду.
В первой строке дано целое число \(k\) — время в секундах, когда учёные хотят понять, сколько клеток занимает колония бактерий (\(1 \le k \le 10^8\)).
Вывести одно число – количество занятых колонией бактерий клеток в \(k\)-ю секунду эксперимента.
Заполнение поля первые пять секунд, в клетке указана секунда, когда впервые эта клетка будет занята колонией бактерий.
| 5 | 5 | 5 | 5 | 5 | ||||
| 5 | 4 | 4 | 4 | 4 | 4 | 5 | ||
| 5 | 4 | 4 | 3 | 3 | 3 | 4 | 4 | 5 |
| 5 | 4 | 3 | 2 | 2 | 2 | 3 | 4 | 5 |
| 5 | 4 | 3 | 2 | 1 | 2 | 3 | 4 | 5 |
| 5 | 4 | 3 | 2 | 2 | 2 | 3 | 4 | 5 |
| 5 | 4 | 4 | 3 | 3 | 3 | 4 | 4 | 5 |
| 5 | 4 | 4 | 4 | 4 | 4 | 5 | ||
| 5 | 5 | 5 | 5 | 5 |
1
1
2
9
3
21
4
45
5
69