Яка мінімальна кількість сірників потрібна для того, щоб викласти на площині n квадратів зі стороною в один сірник? Сірники не можна ламати та класти один на одний. Вершинами квадратів повинні бути точки, де сходяться кінці сірників, а сторонами – самі сірники. Напишіть програму, що за кількістю квадратів n, які необхідно скласти, знаходить мінімальну необхідну для цього кількість сірників.
Вхідні дані Одне ціле число n (1 ≤ n ≤ 109). Вихідні дані Вивести мінімальну кількість сірників, потрібних для складання n квадратів. Ліміт часу 1 секунда Ліміт використання пам'яті 64 MiB
Розв'язання
На малюнку зображено перших 101 побудований квадрат. Пони понумеровані в тому порядку в якому будувалтся. На побудову першого квадрата пішло 4 сірники. По три сірники на кодному "кутовому" квадраті і по два сірники для побудови решти.
У прикріплленому файлі створено електронну таблицю залежності кількості сірників, що додаються від номеру квадрату попорядку. Ось її фрагмент:
У даних є закономірність після кожного квадрату на побудову якоговикористано 3-и сірники іде кілка квадратів побудованих двома сірниками. При чому кількість квадратів побудованих двома сірниками зростає після кожних двох повторень. Така залежність прослідковується вже після третьог квадрату.
Для перших двох квадратів програма визначатиме кількість сірників за умової неповного розгалуження. Далі йдуть цикли, що моделюють поступове збільшення кількості повторів у побудові квадратів з двох сірників. У випадку досягненя потрібної кількості квадратів програма переривається командою безумовного переходу goto на мітку у прикінцевій частині програми.
using System;
class Program
{
public static void Main()
{
int n = Convert.ToInt32(Console.ReadLine());// кількість квадратів, що треба побудувати
int s; // cума сірників, що використано
if (n == 1) {s = 4; goto Finish;}; // для припинення виконання використаємо не "return" а "goto Finish", що перенесе виконання програми на мітку "Finish"
if (n == 2) {s = 7; goto Finish;};
int i; // індекс для циклів з додаванням "двійок", по два сірнки за раз
int p = 1; // кількість двійок сірників, що додаються подвоє підряд (у "плостій" версії "сірників" найчастіше додаються по 2-а сірники)
int n0 = 2; //кількість квадратів, що зараз побудовано
s = 7;
while (n0 < n)
{
s=s+3; n0=n0+1; if (n == n0) goto Finish; // додавання трьох сірників за раз
for (i=1; i<=p; i++) {s=s+2; n0=n0+1;
if (n == n0) goto Finish;} // додавання двох сірників р раз підряд
s=s+3; n0=n0+1; if (n == n0) {
goto Finish;};// додавання трьох сірників
for (i=1; i<=p; i++) {s=s+2; n0=n0+1; if (n == n0) goto Finish;} // додавання двох сірників р раз підряд
p++;
}
Finish: // мітка до якої оперетор "goto Finish" переводить перодовження виконання програми
Console.WriteLine(s);
Console.ReadLine();
}
}
Якщо програма у Вашому браузрі відобрзилсь не коректро то нижче наводиться її графічний "скрін".