Решение задачи #29. Python Яндекс CodeRun, Количество треугольников

Вариант решения задачи на языке программирования Python с Яндекс CodeRun.
Категория: Алгоритмы.
Название задачи: Количество треугольников.
Сложность: Средняя.
Статус решения: "Решено".

Условие задачи:
Рассмотрим фигуру, аналогичную показанной на рисунке (большой равносторонний треугольник, составленный из маленьких равносторонних треугольников). На рисунке приведена фигура, состоящая из 4-х уровней треугольников.

Напишите программу, которая будет определять, сколько всего в ней треугольников (необходимо учитывать не только «маленькие» треугольники, а вообще все треугольники — в частности, нас интересуют треугольник, выделенный жирным, вся фигура).

Решение:

Python

import sys

def main():
    """
    Функция main для решения задачи подсчета треугольников в фигуре.

    Считывает количество уровней N и выводит общее количество треугольников.
    Используется оптимизированная формула для избежания переполнения стека и превышения времени исполнения.
    """
    n = int(sys.stdin.readline())  # Считываем количество уровней N

    # Используем формулу для прямого вычисления количества треугольников: (n * (n + 2) * (2 * n + 1)) // 8
    # // - целочисленное деление, чтобы избежать float
    result = (n * (n + 2) * (2 * n + 1)) // 8
    
    print(result) # Выводим результат


if __name__ == "__main__":
    main()
	

Объяснение кода

Импорт sys:
Модуль sys используется для более эффективного считывания ввода с помощью sys.stdin.readline(). Это особенно важно для больших объемов данных, чтобы избежать TimeoutError при проверке на больших наборах данных.

Формула для подсчета:
Ключевым моментом решения является использование прямой формулы для подсчета количества треугольников. Вместо рекурсивного или итеративного подсчета, что могло бы привести к превышению лимита времени или памяти (особенно при больших N), применяется следующая математическая формула:

(n * (n + 2) * (2 * n + 1)) // 8

Где n — количество уровней.

Эта формула выводится математически и позволяет получить результат напрямую, что делает решение очень быстрым и эффективным.

Целочисленное деление //:
Использование оператора целочисленного деления // вместо обычного деления / гарантирует, что результат будет целым числом, что соответствует условию задачи. Это также немного быстрее, чем преобразование float в int.

Обработка ввода:
Использование int(sys.stdin.readline()) для чтения ввода гарантирует, что входные данные будут корректно преобразованы в целое число.

Структура if name == "main"::
Эта конструкция гарантирует, что функция main() будет вызвана только при непосредственном запуске скрипта, а не при его импорте в качестве модуля. Это стандартная практика в Python.

Источник решения: hdhai.com