Олимпиадная задача по информатике - Треугольные числа

Здравствуйте! Сегодня разберём олимпиадную задачу по информатике, которая называется треугольные числа.

Школьник Никита этим летом отдыхал со своими родителями. Его любимым занятием на пляже было складывать из камешков правильные треугольники (правильным называется треугольник, у которого все стороны равны). Никита и не предполагал, что числа, из которых можно сложить правильный треугольник, называются треугольными. Вот несколько треугольных чисел: 1, 3, 6, 10, … .

Помогите Никите по заданному количеству камешков N найти наибольшую сторону правильного треугольника, который из них можно сложить. Например, если у Никиты 30 камешков, то длина наибольшей стороны правильного треугольника, который из них можно сложить, будет 7.

Рассмотрим треугольные числа. Видим, что первое треугольное число - это просто 1. Второе число - это сумма чисел до 2 (1+2), третье число - сумма чисел до 3 (1+2+3) и т.д.

Плюс ко всему, второе число образует треугольник со стороной 2, третье число со стороной 3 и т.д.

Рассмотрим треугольное число по номером n. Видим, что это сумма арифметической прогрессии.

Свернём по формуле арифметической прогрессии. Число Sn (сумма арифметической прогрессии) в нашей задаче это количество камней, которое вводит пользователь. Число n в данном уравнении обозначает порядковый номер треугольного числа или длину стороны правильного треугольника, который можно составить из данного количества камней.

Остаётся решить данное уравнение относительно n в целых числах, чтобы разгадать нашу задачу.

Последние уравнение это и есть ответ в нашей задаче. Если n - будет дробным, значит мы должны его округлить в меньшую сторону, т.к. наше уравнение решается только в целых числах. (Дробное количество камней не может быть).

Запрограммируем данную задачу на C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Numerics;

namespace ConsoleApp69
{
    class Program
    {
        static void Main(string[] args)
        {
             BigInteger n, a;

             a = Convert.ToUInt64(Console.ReadLine());

             n = (BigInteger)(Sqr(1 + 8 * a) - 1) / 2;

             Console.WriteLine(n);

            Console.ReadKey();
        }


        public static BigInteger Sqr(BigInteger a)
        {
            BigInteger x0, e, xn, xnp1;
            e = 1;
            x0 = a;
            xn = (x0 - (x0*x0 - a) / (2 * x0));
            xnp1 = (xn - (xn*xn - a) / (2 * xn));


            while (xn - xnp1 >= e)
            {
                xn = xnp1;
                xnp1 = xn - (xn*xn - a) / (2 * xn);

            }

            return xnp1-1;
        }


    }
}

Т.к. число 9223372036854775807 * 8 превышает максимальное число даже для типа ulong, то будем использовать специальный тип BigInteger.

Для того, чтобы использовать BigInteger, нужно в ссылках добавить System.Numerics. И прописать using System.Numerics в программе.

Для этого типа данных не работает стандартная функция извлечения корня Math.Sqrt(), поэтому мы напишем свою функцию извлечения корня основанную на методе Ньютона. Эта функция извлекает корень и округляет результат в меньшую сторону. Об этом методе можете прочитать подробно в статье на этом сайте.

На этом всё, до свидания!