Task 50. Спички

Задача: Какое минимальное количество спичек необходимо для того, чтобы выложить на плоскости N квадратов со стороной в одну спичку? Спички нельзя ломать и класть друг на друга. Вершинами квадратов должны быть точки, где сходятся концы спичек, а сторонами – сами спички.

Напишите программу, которая по количеству квадратов N, которое необходимо составить, находит минимальное необходимое для этого количество спичек.

Входные данные: Натуральное число N (N <= 1000)

Вывод: вывести минимальное кол-во спичек, требуемых для составления N квадратов.

Например, 

1. для 4х квадратов достаточно 12 спичек

2. для 14 квадратов потребуется 36 спичек

Идея: один квадрат можно составить из 4х спичек, два квадрата из 7 спичек. Очевидно, что квадраты следует располагать так, чтобы они образовывали прямоугольник, близкий к квадрату. 

Пусть width = корень из N - ширина этого прямоугольника, length = n/width - длина. Для составления такого прямоугольника понадобится

width*(length + 1) + length*(width + 1)

спичек.

Останется ost = N - width*length квадратов, не поместившихся в этот прямоугольник. Их пристроим отдельной строкой внизу прямоугольника, на что дополнительно понадобится 2*ost + 1 списка.

Реализация:

https://gist.github.com/unilecs/923990d7828fdce990e703292f3859a3

Тест:

https://dotnetfiddle.net/LiPk4Y