tvolf

<?php

/*
    Для решения задачи используем рекурсию. Так как по условию задачи на выходе у нас должны получаться
    невозрастающие последовательности, то на каждом шаге рекурсии мы перебираем значения, которые
    меньше либо равны предыдущему значению в последовательности.
*/

function task130($n) {
    $row = [];

tvolf

<?php

/*
Рассмотрим ситуацию, когда у нас число разбито на некоторые слагаемые. Все отдельные единицы мы можем добавить
к любому слагаемому и от этого произведение только увеличится (1 * N = N). Затем, все слагаемые K, которые больше четырех, 
мы можем разбить на 3 * (K - 3). При этом итоговое произведение увеличится (5 < 3 * 2, 6 < 3 * 3, 7 < 3 * 4 и тд). 
Каждые три группы двоек мы можем заменить на 2 тройки, так как 2 * 2 * 2 < 3 * 3.
Таким образом, нам нужно разбить исходное число на максимальное количесто троек, а в остатке у нас не должно быть единицы. 
Если остается единица, мы должно взять одну из троек и суммарное 4 либо оставить так, как есть, либо заменить на 2 двойки (2 * 2 = 4). 
Таким образом, в результате разделения на слагаемые у нас должны остаться в последовательности все тройки и 0, 1 либо 2 двойки.

tvolf

<?php

/*
    Предположим, у нас есть итоговый набор строк для некоторого шага N. Попробуем посчитать, какое количество строк у нас 
    будет на шаге N+1. Допустим, на шаге N мы имеет K строк, заканчивающихся на '1' и L строк, заканчиваюшихся на остальные 
    допустимые символы ('2' и '3'). На новом шаге N+1 мы будем иметь (K + L) строк, заканчиваюшихся на '1' (мы можем добавить
    '1' к каждой входной строке). При этом общее количество строк будет равно K * 2 + L * 3, так как к строке, заканчивающейся 
    на '1', мы можем добавить лишь '1' и '3' (последовательность символов '12' исключена по условию задачи), а к остальным 
    строкам мы можем добавить все три символа ('1', '2' и '3').

tvolf

<?php

/*
  Эвристический алгоритм решения задачи о разбиении массива на две группы таким образом,
  чтобы разность сумм элементов в каждой из групп была минимальной.
  Алгоритм дает оптимальное решение во многих случаях, но не во всех,
  и может быть применен на входных данных большой размерности,
  когда перебор всех вариантов для поиска лучшего решения не является разумным способом
  решения задачи.
  Суть алгоритма: cортируем исходный массив по убыванию, а затем добавляем по очереди элементы

tvolf

<?php

/*
  Классическая задача о разбиении массива на две группы элементов таким образом,
  чтобы разность сумм их элементов была минимальной.
  Для поиска лучшего решения будем рассматривать все возможные выборки
  элементов из заданного массива размерностью N. Для этого рассмотрим двоичные
  представления чисел от 0 до 2^N-1. Единичный бит в числе будет означать, что
  данный элемент выбран.
*/

tvolf

<?php

/*
 Суть алгоритма: перебираем все возможные варианты подматриц по оси x
 (первый и последний столбец, соответственно, xStart и xEnd).
 Затем интереснее. В промежуточном массиве prom, имеющем размерность высоты нашей
 исходной матрицы, накапливаем суммы по всем рядам в заданном диапазоне колонок (от xStart до xEnd).
 Далее, имея эти суммы элементов по рядам, используя алгоритм Кадейна (Kadane) для нахождения максимального
 подмассива в массиве, оставляем только ту последовательность рядов, которая дает максимальную подматрицу
 в диапазоне колонок от xStart до xEnd.

tvolf

<?php

/*
 * Для подсчета длин периметров и фронтовой линии используем
 * классический поиск/обход в ширину. Выбираем свободные точки на карте
 * и далее обходим связанные области, подсчитывая значения длины
 * фронтовой линии и периметров.
 */

class Task120 {

tvolf

<?php

/**
 Для решения задачи используем метод динамического программирования.
 Рассмотрим поддерево с корнем в вершине v. В этом случае возможны 2 ситуации вычисления
 максимальной суммы: когда мы включаем значение вершины v в итоговое множество и когда мы ее
 не используем. В первом случае максимальная сумма вершин равна сумме веса самой вершины v и
 суммы максимальных сумм всех поддеревьев с вершинами, не включающими детей вершины v.
 Во втором случае максимальная сумма вершин поддерева будет равна сумме максимальных сумм поддеревьев
 для каждого ребенка вершины v. При этом выбираем максимальное значение из 2-ух: когда ребенок входит

tvolf

<?php

/**
Для решения задачи используем классический алгоритм Дейкстры для нахождения
кратчайшего пути. Ребро, связывающее две вершины, будет иметь два весовых значения,
отличающиеся для направления в одну и другую сторону. Таким образом, матрица смежности
будет несимметрична относительно главной диагонали.
**/

function calcAdjMatrix($n, $costs, $roads) {

tvolf

<?php

/*
   Пользуясь свойством симметрии, вычисляем количество точек, лежащих
   в правом верхнем квадранте. Итоговое кол-во точек будет равно кол-ву выше,
   умноженному на 4 (4 квадранта в круге), плюс кол-во точек, лежащих на осях,
   проведенных через центр круга.
*/

function task114($r) {