Разбор задач

Нужно рассмотреть 3 варианта для размеров параллелепипеда:

1) первых два размера минимальны и равны 1, последний размер на 1 больше максимального ограничения, то есть вариант `(1,\ 1,\ С+1)` (ограничения упорядочены по возрастанию);

2) вариант `(1,\ B+1,\ B+1)`;

3) вариант `(A+1,\ A+1,\ A+1)`.

И выбрать из них параллелепипед с наименьшим объемом, запоминая объем и размеры минимального по объему параллелепипеда среди проверенных вариантов. Тип для переменных лучше выбрать longint, так как возможно переполнение при вычислении объема.

Требуется подсчитать число точек с целыми координатами `(X,\ Y)` таких, что `X` и `Y` принимают в диапазоне от `–R_2` до `R_2`, и выполняется условие `R_1^2\ <\ X^2\ +\ Y^2\ <\ R_2^2`. Два вложенных цикла по `X` и `Y` с указанной проверкой могли дать 15 баллов. Для более быстрого решения требуется разбить парк на 4 части и выполнять подсчет количества деревьев на линии с определенной ординатой без применения цикла.

Сначала нужно вывести формулу для расчета количества подмножеств, начинающихся с определенной буквы. Это просто произведение увеличенных на 1 количеств букв, так как если у нас есть `K` букв 'D' ее можно брать в количестве 0, 1, …, `K` (то есть `K+1` вариант для выбора).

Рассмотрим подмножества, начинающиеся с одинаковой подстроки (префикса). Они упорядочены следующим образом: сначала идут подмножества, в которых количество одинаковых букв (очередной буквы алфавита после последней буквы префикса) постепенно возрастает. Таких строк `K`, если количество букв `K`. Затем идет `(K+1)` группа, у которых число букв (очередной буквы алфавита после последней буквы префикса) постепенно убывает до 0. Формула для количества строк в группе уже выведена.

Алгоритм достаточно простой – проходим по буквам алфавита и набираем нужное их количество, пока не дойдем до нужного номера и в результате получаем подмножество.

Вводим интервалы и находим их пересечение по правилам математики. Интервал лучше всего представлять в виде двух целых чисел – левой и правой границы – и двух флагов для указания типа границы. Можно воспользоваться другим представлением в виде пары двух вещественных чисел. В случае открытой границы из числа можно вычесть или прибавить число 0.01. Левая граница пересечения – это максимум из левых границ интервалов, а правая – минимум из правых. При печати проверяем, что левая граница меньше или равна правой, иначе печатаем %.

Используем динамическое программирование и длинную арифметику для расчета количества чисел с заданной суммой. В ячейке `T[K,S]` таблицы для динамического программирования хранится количество номеров из `K` цифр с суммой `S`. Построив таблицу `T` до `K`-ой строки можно построить `(K+1)` строку, выполнив суммирование для `S` от 0 до `K*9` и для `j` от 0 до 9 `T[K+1,S+j]:=\ T[K+1,S+j]+T[K,S]`. Для вычислений нужны только 2 строки таблицы.

Лобовой вариант – перебор всех чисел от 0 до `10^N` и подсчет количества чисел с заданной суммой среди них давал 8 баллов. 18 баллов можно было получить с помощью динамического программирования и таблицы `T` с ячейками типа extended для `N\ <\ 20`.