A1029

Задача о восьми мирных ладьях

Задача о восьми мирных ладьях

Условие

Получить все расстановки   [latex]8[/latex]   ладей на шахматной доске, при которых ни одна ладья не угрожает другой.


Решение

Для начала, выясним, а сколько существует таких расстановок, при условии, что рассматривается стандартная шахматная доска   [latex]8 \times 8[/latex].

Ладья находится под боем, если другая ладья находится с ней на одной строке или в одном столбце. Следовательно, фиксируя, скажем, столбцы, можно разместить ладьи по строкам таким образом, чтобы ни одна пара не находилась под боем.

Заведем массив на восемь элементов и занумеруем его таким образом, чтобы значение   [latex]j[/latex]   по индексу   [latex]i[/latex]   соответствовало строке [  [latex]j[/latex],   в которой находится ладья в   [latex]i[/latex]-м столбце.

Теперь легко видеть, что положение на доске определяется перестановкой чисел   [latex]1,..,8[/latex].   Как известно, число различных перестановок длины [latex]n[/latex]   —   [latex]P_{n}=n![/latex]. Следовательно, всего существует   [latex]8!=40320[/latex]   различных расстановок ладей.

Реализация
ideone: http://ideone.com/tBySY4
Легенда: R — Rook — ладья


Детали реализации

Для получения перестановок использована функция стандартной библиотеки [latex]next\_permutation()[/latex]

В силу большого объёма выходного файла (5.5 мб) он доступен отдельно, по ссылке: https://www.dropbox.com/s/yyaz7vq08jczsnl/out?dl=0

А719б

Условие

Симметричные квадратные матрицы [latex]A[/latex] и [latex]B[/latex] порядка [latex]n[/latex] заданы последовательностями из [latex]\frac{n(n+1)}{2}[/latex] чисел аналогично правым треугольным матрицам. Получить в аналогичном виде матрицу [latex]A^{2}-B^{2}[/latex].


Решение

Безусловно, по входным данным можно восстановить матрицы, тривиальным образом их перемножить и вывести результат в заданном виде. Как пример плохого стиля программирования: наивный алгоритм приводит к почти двукратному перерасходу потребляемой памяти и существенно уступает в производительности. Существует другое решение, прийти к которому можно путем последовательного приспособления стандартных матричных операций к формату входных данных.

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


Замечание 1

Подпространство симметричных матриц незамкнуто относительно умножения: произведением двух симметричных матриц может быть несимметричная матрица.

Пример

[latex] \left(\begin{array}{ccc} 1 & 1 & 3 \\ 1 & 4 & 5 \\ 3 & 5 & 0\end{array} \right) \cdot \left( \begin{array}{ccc} 4 & 0 & 0 \\ 0 & 4 & 3 \\ 0 & 3 & 2 \end{array} \right) = \left( \begin{array}{ccc} 4 & 13 & 9 \\ 4 & 31 & 22 \\ 12 & 20 & 15 \end{array} \right)[/latex]


Замечание 2

Степень симметрической матрицы также является симметрической матрицей. Доказательство основано на представлении матрицы как представления линейного оператора и на свойствах эрмитовых операторов.


Во всех дальнейших выкладках подразумевается, что матрица представлена линейным массивом из [latex]\frac{n(n+1)}{2}[/latex] элементов.

Для начала, заметим, что элемент [latex]c_{i,j}[/latex] матрицы [latex]C=A^{2}[/latex], равен скалярному произведению (как векторов в стандартном базисе) [latex]i[/latex]-ой строки матрицы [latex]A[/latex] на [latex]j[/latex]-ую её строку (в силу того, что в симметричной матрице [latex]j[/latex]-ая строка совпадает с [latex]j[/latex]-м столбцом). Следовательно, для возведения в степень симметричной матрицы необходимо и достаточно реализовать операцию скалярного перемножения двух её строк.

Тогда следует понять, как по данному представлению матрицы получить её [latex]i[/latex]-ую строку. Для удобства, выпишем имеющиеся элементы в виде полной матрицы. Заметим, что первым элементом [latex]i[/latex]-ой строки будет [latex]i[/latex]-ый элемент первой строки, и обобщим это наблюдение. Обозначим позицию текущего интересующего нас элемента [latex]i[/latex]-ой строки как [latex]j[/latex]. Если [latex]j < i[/latex], то следует выбрать [latex]i[/latex]-ый элемент [latex]j[/latex]-ой строки, иначе следует выбрать все элементы [latex]j[/latex]-ой строки, лежащие правее данного. Графически можно интерпретировать алгоритм таким образом: начиная с [latex]i[/latex]-го элемента первой строки, спускаться вертикально вниз по матрице до тех пор, пока не будет достигнута [latex]i[/latex]-ая строка, далее — двигаться вправо до конца строки. Наглядность алгоритма позволяет легко воплотить его программно.
Следует только пронаблюдать, как изменяются расстояния между элементами, лежащими один под другим, при движении вниз по строкам матрицы, что позволит легко перенести алгоритм на линейное представление верхней треугольной матрицы. Предлагаем читателю самому проделать это несложное, но наглядное упражнение, для лучшего понимания алгоритма.

Теперь можно перейти непосредственно к реализации.


Тесты

[latex]n[/latex] [latex]A[/latex] [latex]B[/latex] [latex]A^{2}-B^{2}[/latex]
2 1 2 5 7 4 8 -60 -48 -51
4 1 7 3 -2 3 1 9 2 8 11 4 5 11 -3 4 -7 22 1 4 0 -108 116 -8 -79 -434 -10 75 -109 290 -239

Реализация

ideone: http://ideone.com/Dyte8l


Тесты

Детали реализации

Задачи раздела носят обучающий характер, так что при реализации были произведены определенные обобщения, что делает решение более универсальным.

  • Формулировка задачи не оговаривает тип элементов матрицы, так что класс [latex]symmetric\_matrix[/latex] является шаблоном, пригодным для типов данных, поддерживающих операции сложения, вычитания и умножения (соответствующие операторы определены внутри класса).
  • Алгоритм бинарного возведения матрицы в степень полезен при решении более широкого круга задач, в связи с чем также реализован. При необходимости, программа легко обобщается на большие степени матрицы.
  • Предусмотрены три типа конструкторов: конструктор по умолчанию и два параметрических конструктора, один из которых позволяет заполнить матрицу некоторым наперед заданным значением.
  • Для удобства работы с заданным представлением данных, добавлен синтаксический сахар: перегружен оператор [latex][][/latex], осуществляющий доступ к заданному элементу матрицы в линейном её представлении.

e-olimp 4650. Граф-Турнир

Граф-турнир.

Постановка задачи

Построить на n вершинах турнир, расстояние между любой парой вершин в котором не превышает двух рёбер.

Алгоритм решения

Условию удовлетворяет любая тройка вершин, принадлежащих циклу длины три, следовательно, искомый граф сильно связен. Уместно взять за основу полный неориентированный граф [latex]K_n[/latex] (не ограничивая общности рассуждений, будем представлять граф на плоскости как правильный [latex]n[/latex]-угольник) и задать на нём ориентацию рёбер согласно набору правил:

  1. Контур графа (рёбра вида [latex](k, k+1)[/latex]) ориентирован по часовой стрелке.
  2. В дальнейших построениях будем отталкиваться от контура: каждая вершина графа должна находиться в хотя бы в одном цикле длины три с данной. Опишем процедуру построения такого орграфа: начиная с вершины под номером 1 будем просматривать все остальные вершины. Если на некотором шаге ребро, связывающее вершины, не ориентировано, то ориентируем его образом, противоположным ориентации ребра, соединяющего текущую вершину-исток и предыдущую по номеру вершину в обходе. Более конструктивно процедура формулируется так: обойти все вершины в порядке их следования в контуре. Пусть номер стартовой вершины для исходной итерации — [latex]V_{i}[/latex], рассматриваемой на данном шаге — [latex]V_{k}[/latex] Если ребро [latex]\left(V_{i}, V_{k}\right)[/latex] не ориентировано, и номера обеих вершин (не)чётны — задать ориентацию [latex]\left[V_{i}, V_{k}\right][/latex], иначе — [latex]\left[V_{k}, V_{i}\right][/latex].

КонтурЦиклИсключение
Исключение — граф [latex]K_4[/latex]: степень каждой вершины равна трём, следовательно, одно ребро каждой вершины не принадлежит контуру. Но таких рёбер всего два, следовательно, невозможно задать чередование ориентаций рёбер и получить четыре цикла длины 3. Для всех графов на большем числе вершин построение всегда возможно.

Реализация

ideone: http://ideone.com/XwY7fX
Засчитанное решение: http://codeforces.ru/contest/323/submission/10850799
Для решения задачи достаточно хранить граф в форме матрицы смежности.

ideone: http://ideone.com/eBcMcY

I. Новорічні іграшки

Задача с SEERC 2015, [latex]\frac {1}{8}[/latex] финала.

Формулировка

«У кожного свята є один недолік – рано чи пізно, але воно закінчується. Ось і новорічні свята завершились і малому Дмитрику необхідно скласти іграшки у коробки. Частину іграшок він склав у одну коробку, а частину у іншу. Старший брат Дмитрика Петрик навчається в математичному класі. І його цікавить чи можна перекласти всі іграшки у одну з коробок (кожна коробка вміщує усі іграшки), якщо з одної коробки у іншу можна перекладати стільки іграшок, скільки у іншій коробці.

Вхідні дані:
Два числа N і M — кількість іграшок у першій та другій коробці (1 ≤ N, М ≤ 2000000000).
Вихідні дані:
Bиведіть 1 – якщо можна перекласти іграшки у одну коробку, або 0 – якщо такої можливості немає.»

Алгоритм

  1. Ограничение на входные данные.
    Предположим, что при некоторых [latex]N[/latex], [latex]M[/latex] ответ положительный. Пусть [latex]c = N + M[/latex].
    Будем выстраивать последовательность шагов от конца к началу. Стартовая позиция — [latex]\left(c \quad 0 \right)[/latex](подарков в коробках). Очевидно, что прийти в неё можно только из [latex]\left( \frac {c}{2} \quad \frac {c}{2} \right)[/latex]. Определим вид предыдущей позиции: [latex]\begin{cases} a+b=c, \\ a-b=\frac { c }{ 2 } ; \end{cases}\sim \begin{cases} 2a=c+\frac { c }{ 4 } , \\ b=a-\frac { c }{ 2 } ; \end{cases}\sim \begin{cases} a=\frac { 3c }{ 4 } , \\ b=\frac { c }{ 4 } ; \end{cases}[/latex]. Принципиально важно, что показатель знаменателя на каждом шаге монотонно возрастает. В силу конечности [latex]c[/latex], процесс конечен. Меньший член пары имеет общий вид [latex]\frac {c}{2^{n}}[/latex], следовательно, [latex]c = N + M = 2k[/latex] (здесь и далее предполагается, что все переменные — некоторые натуральные числа).
    Заметим, что постоянный множитель [latex]k[/latex] не влияет на сходимость. Следовательно, на него можно сократить и суммы [latex]N + M[/latex]. Максимальный из таких [latex]k[/latex] будет [latex]gcd \left(N, M \right)[/latex].
    Полученный результат позволяет сформулировать необходимое условие: если решение есть, то сумма чисел [latex]N[/latex] и [latex]M[/latex] равна некоторой степени двойки с точностью до НОД([latex]N, M[/latex]).
    цепочка
  2. Достаточно условие сходимости.
    Пусть [latex]N, M[/latex] — некоторые числа, удовлетворяющие необходимому условию. Тогда [latex]\exists n: N=2^{ n }-M[/latex].
    Рассмотрим следующий шаг, предполагая, что [latex]N \ge M[/latex]: [latex]\left(2N \quad 2^{n}-2N\right) \sim \left(N \quad 2^{n-1}-N \right)[/latex]) — задачу удалось свести к подзадаче. Повторяя аналогичную процедуру, на [latex]n[/latex]-м шаге придём в позицию, эквивалентную [latex]\left(1 \quad 2^{0}-1 \right) \sim \left(1 \quad 0 \right)[/latex], т.е. последнему шагу. Следовательно, для любого набора данных, удовлетворяющих необходимому условию, решение существует. Следовательно, условие является необходимым и достаточным, с поправкой на тривиальный случай [latex]N = M[/latex].

Реализация

ideone: http://ideone.com/OxWVLi

ideone: http://ideone.com/Xnupjz

Детали реализации

Задачи тура подразумевали лаконичные реализации решений. Использование битовых операций позволяет легко ответить на вопрос, является ли сумма чисел некоторой степенью двойки, а также вычислить НОД двух чисел методом приведения в смятение, для чего используется, на мой взгляд, весьма красивое наблюдение о свойствах функции XOR.

e-olimp 4475. Часы

4475. Часы

Постановка задачи

Ученые разработали часы, которые могут налаживаться для отсчета времени на любой планете. Они состоят из шариков, лотка (очереди) и трех чаш: секундной, минутной и часовой. В каждый момент времени количество шариков в чашах показывает время (секунды, минуты и часы соответственно). Каждую секунду первый шарик из очереди попадает в секундную чашу. Если секундная чаша наполнилась (количество шариков равно количеству секунд в минуте на этой планете), то этот шарик переходит в минутную чашу, а остальные шарики переходят из секундной чаши в конец очереди в порядке, обратном к их попаданию в секундную чашу. Аналогично, при наполнении минутной чаши последний шарик переходит в часовую чашу, а остальные шарики из минутной чаши переходят в конец очереди в порядке, обратном к их попаданию в минутную чашу. Если заполняется часовая чаша, то все шарики из нее переходят в конец очереди в порядке, обратном к их попаданию в часовую чашу. Все шарики пронумерованы и в начальный момент времени находятся в очереди.

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

Во входном потоке содержится количество секунд в минуте [latex]S[/latex], минут в часе [latex]M[/latex], часов в сутках [latex]H[/latex] и число шариков [latex]K[/latex].

Алгоритм решения

  1. Интуитивно понятно, что положение шариков в очереди ежесуточно изменяется по одному и тому же закону, в силу однообразия процесса. Отыскать конкретный вид перестановки можно прямым моделированием часов, используя дек для описания лотка и стеки — каждой из чаш (у очереди задействованы оба конца, у чаш — только один).
  2. Определить порядок суточной перестановки можно и возведением её в степень, но это нерациональный способ. Используя теорему о разложении перестановки в композицию циклов (к слову, непересекающихся), можно заметить, что порядок каждого из циклов равен его длине. Если мысленно представить перестановку в виде ориентированного графа, то процесс поиска циклов сведётся к поиску в глубину: обойти каждую компоненту связности, зафиксировать число входящих в неё вершин (на илл.)
  3. Зная длины всех циклов, нетрудно заметить, что задача сводится к поиску НОК полученной последовательности длин. Обосновать такой переход можно индуктивно: порядок перестановки, представимой в виде композиции двух циклов, равен НОК их длин, а случай большего количества циклов в разложении сводится к рассмотренному последовательным рассмотрением пар циклов (результат не зависит от порядка рассмотрения в силу ассоциативности композиции).

Реализация:

ideone: http://ideone.com/nz2JlG
Засчитанное решение: http://www.e-olimp.com/solutions/1937971

Примечания

  • Экспериментально выяснено, что только тип long double является достаточно вместительным для избежания переполнения.
  • Операция взятия остатка для чисел с плавающей точкой не определена аппаратно, так что алгоритм Евклида вычисления НОД реализован в соответствии с его математическим описанием.
  • Модификатор fixed используется для предотвращения вывода чисел в научном формате (с использованием степеней десятки).

e-olimp 2510. Сортировка очередями

e-olimp 2510. Сортировка очередями

Постановка задачи

Рассматривается специальное устройство, содержащее входной поток, выходной поток и k очередей, пронумерованных числами от [latex]1[/latex] до [latex]k[/latex].

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

Программа должна содержать ровно [latex]2n[/latex] операций, каждая из которых либо читает число из входного потока и добавляет его в одну из очередей, либо извлекает число из одной из очередей и выводит его в выходной поток.

Алгоритм решения

  • Естественная идея: поддерживать линейный порядок в каждой из очередей. Для этого следует совершать обход массива очередей сортировочной машины от первой к последней, пока не будет найдена очередь, последний элемент которой не больше данного, либо отсутствует вовсе.
  • Если на одном из шагов подходящей очереди не нашлось, то на таких входных данных задача неразрешима.
  • При выводе следует выбирать очередь, содержающую текущий минимальный доступный элемент, поддерживая линейный порядок в новом массиве.

Реализация:

Ideone: http://ideone.com/X37iWg
Засчитанное решение: http://www.e-olimp.com/solutions/1935453

Детали реализации:

В коде программы активно используется библиотека [latex]algorithm[/latex] и анонимные функции,
объявленные по месту использования (внутри соответствующих методов), что позволяет минимизировать число лишних сущностей
и сделать реализацию более декларативной.

  1. find_if() — найти первый элемент участка контейнера, удовлетворяющий логическому условию. Принимает итераторы
    на левую и правую границу интересующего участка, а также унарное логическое условие. Возвращает итератор на интересующий
    элемент или итератор на область за пределами участка, если условие не выполнилось ни разу.
  2. min_element() — найти минимальный элемент на заданном участке контейнера. Принимает итераторы на левую и правую
    границу интересующего участка и двухместный предикат, задающий отношение порядка. Возвращает итератор на интересующий
    элемент или за на область за пределами участка, если условие не выполнилось ни разу (пустой контейнер, некорректный порядок).

e-olimp: 694. Минимум в очереди

e-olimp: 694 — Минимум в очереди

Постановка задачи

На вход программы подается набор операций с очередью. Каждая операция состоит в добавлении или удаления элемента из очереди. После выполнения каждой операции найдите наименьшее число, которое находится в очереди. Сложите все полученные числа и получите ответ. Если после некоторой операции очередь оказалась пуста, то ничего не прибавляйте к ответу. Если выполнить удаление невозможно, так как очередь пуста, то не выполняйте его.

Алгоритм решения

Классическая модификация очереди с поддержкой минимального хранимого значения подразумевает использование двух модифицированных стеков, один из которых служит только для проталкивания элементов в очередь, а другой — только для выталкивания. Стеки хранят пары значений: непосредственно элемент и минимальное значение в очереди на момент его добавления, что позволяет поддерживать актуальную информацию при выполнении модифицирующих запросов (см. классический труд Кормена и статью на e-maxx). Более подробно механика процесса описана в комментариях к коду.

Реализации:

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

Спортивный подход

ideone: http://ideone.com/pvVixS
засчитанное решение: http://www.e-olimp.com/solutions/1926658

Преимущества

  • Простота. Концепция воплощается буквально — даже в условиях ограниченности во времени ошибиться трудно.
  • Наглядность и компактность кода.
  • Сообразность средств цели: постановка задачи требует реализации только трех функций: проталкивания, выталкивания и взятия крайнего элемента. Каждая из них реализована по возможности наиболее простым способом.

Недостатки

  • Немасштабируемость. При необходимости внедрения дополнительного функционала или изменении постановки задачи (скажем, отсутствии явной верхней границы для входных данных) возникают проблемы, решение которых неизбежно приводит к использованию объектно-ориентированных средств языка.
  • Перерасход памяти. Реальное количество одновременно содержащихся элементов в каждом из стеков на порядок меньше, но из формулировки задания это не следует и выясняется экспериментальным путём.
  • Костыли, избыточные сущности. Отличительная черта одноразового кода. Во время соревнования требования к коду достаточно мягкие: он должен работать. Желательно — предсказуемым образом. Причем, нередко реализуется не оптимальное и логичное решение, а то, которое понимаешь. Отладка и чтение таких программ — занятие не из приятных.

Объектно-ориентированный подход

ideone: http://ideone.com/A6BpwN
засчитанное решение: http://www.e-olimp.com/solutions/1924823

Преимущества

  • Масштабируемость. Добавление функционала сводится к написанию новых методов класса.
  • Универсальность. Основа стека — односвязный список. Следовательно, его размер ограничен только объёмом доступной оперативной памяти.
  • Инкапсуляция. Реализация методов класса отделена от контекста выполняемых им функций в теле программы.
  • Польза процесса. Быстро написать более простое решение, не разобравшись в тонкостях классической реализации, почти наверняка не удастся.

Недостатки

  • Временные затраты. Использование односвязного списка порождает частные случаи, на которые придется обратить внимание. Их классификация и обработка требует вдумчивого подхода.

AA19

Постановка задачи: В заданной строке заменить три точки, идущие подряд, тремя первыми символами строки.

Алгоритм решения: Если строка не начинается с троеточия, последовательно заменять все его вхождения.

Тесты

Input Output
the more I code … better my coding becomes the more I code the better my coding becomes
…what am I supposed to do? …what am I supposed to do?
abc……… abcabcabc

Код программы


1. C, c-string,


2. C++, string


М16. Freshly Pressed Juice

Формулировка задачи

Известно, что каждый посетитель фруктового бара просит сделать наиболее дешевый коктейль из свежевыжатого сока. Объем стакана для сока V. Рассчитайте стоимость и сформируйте рецепт коктейля, который достанется n-тому посетителю. V и n читаются из входного потока. Во входном потоке имеется неизвестное количество строк – справочник в котором для каждого вида фруктов указано его название, текущая стоимость за килограмм, процент выхода сока и количество фруктов на складе.
а) Прочитать справочник в список (vector) соответствующих структур.
б) Сформировать рецепт и рассчитать стоимость наиболее дешёвого коктейля.

Тесты

[latex]V[/latex] [latex]n[/latex] [latex]Menu[/latex] [latex]Recipe[/latex] Комментарий
150 2 Apple 10 60 200

Cherry 20 70 50
Sorry, we are closed for today Объем фруктов на складе меньше 300.
80 8 Dragonfruit 123 50 10

Aplle 10 60 200

Cherry 40 80 100

Coconut 20 5 30

Pineapple 80 90 50

Raspberry 70 95 30

Blackberry 130 95 30

Strawberry 60 95 40

Grape 20 95 120

Orange 10 80 200

Melon 10 98 300

Banana 20 30 120
Apple 80 800 В самом деле, более выгодным будет использование только арбузов и апельсинов, израсходованных ранее.
80 14 (см. тест № 2) Banana 40.000000

Raspberry 30.000000

Pineapple 10.000000

3700
Корректно
110 1 (см. тест №2) Melon 110 1100 Корректно

Анализ задачи

  1. Параметры «количество», «удельная стоимость», «процент выхода сока» описывают сущность типа «фрукт». Следовательно, необходимо создать одноименную структуру, связав конкретное наименование в меню (списке) с его количественными характеристиками.
  2. Условие задачи можно переформулировать как поиск наиболее выгодного фрукта по соотношению (у.е./куб.ед.) — фрукта, из единицы массы которого можно дешевле всего получить кубическую единицу объема, [latex]\frac {price}{volume}[/latex]. Данные, необходимые для сортировки фруктов в порядке возрастания стоимости единицы объема сока, присуствуют в исходных данных. Подробнее: [latex]\frac {price}{volume} = \frac {amount*specificCost}{amount*percentage*\rho} = \frac {specificCost}{percentage*\rho}[/latex]. В условии не указано обратное, потому плотность сока принята равной [latex]\rho = 1[/latex](г/мл). Окончательно, [latex]worth = \frac {specificCost}{percentage}[/latex].

Алгоритм решения

    • Объявить структуру [latex]fruit[/latex] с переменными:
      • name
      • specific_cost
      • percentage
      • amount
    • Необходимо
      1. считывать информацию о фрукте;
      2. сортировать фрукты по некоторому параметру

      Следовательно, уместно определить методы [latex]get()[/latex] и [latex]worth()[/latex] соответственно.

  1. Дальнейшее решение распадается на несколько подзадач:
    1. Сортировка элементов вектора в порядке убывания стоимости единицы объема.
    2. Поиск фруктов, доступных в момент, когда [latex]n[/latex]-ый посетитель делает заказ.
    3. Составление коктейля наименьшей стоимости при заданном объёме порции.

    Был намечен следующий алгоритм действий:

    1. После сортировки определить, какая масса фруктов должна быть израсходована к моменту заказа, и последовательно проходить по вектору, уменьшая количество каждого фрукта, пока не дойдем до требуемого значения.
    2. Если оставшихся фруктов достаточно для приготовления коктейля, последовательно перерабатывать фрукты, пока на складе не закончится текущее наименование, а тогда перейти к следующему, и так пока не прийдем к заданному объему.
    3. На каждом шаге добавлять в рецепт количество использованных фруктов вместе с их названиями. В конце рецепта указать стоимость коктейля.

Программный код

Программа доступна для тестирования по ссылке: http://ideone.com/qj8ovB.

Подробности реализации

Из интереса и эксперимента ради решение было запрограммировано в двух вариантах: в процедурном, в духе классического языка C, и средствами стандарта C++11. Вторая версия получилась более лаконичной, но, при необходимости, может быть предъявлена и первая.

  1. После считывания списка переменная [latex]total amount[/latex] хранит в себе общее количество всех фруктов на складе.
  2. Метод [latex]get()[/latex] возвращает значение булевого типа, так как таким образом можно производить чтение до конца файла средствами [latex]cin[/latex], с автоматической проверкой.
  3. Для работы только с фруктами, доступными в момент совершения заказы [latex]n[/latex]-м посетителем, была создана переменная [latex]used[/latex], хранящая объем всех коктейлей, сделанных для предыдущих посетителей. В цикле [latex]any of()[/latex] на каждом шаге происходит уменьшение переменной [latex]used[/latex] на доступную массу фруктов данного типа. Для наглядности восприятия введена переменная [latex]new amount[/latex]. Если оставшееся на складе количество фруктов позволяет сделать ещё один коктейль, происходит вход во внутренний цикл. В противном случае, пользователя уведомляют о том, что выполнение заказа невозможно.
  4. Во внутреннем цикле, который выполняется, пока не наберется достаточный объем сока, на каждом шаге берут максимально возможное количество фрукта данного типа. Рецепт сохраняется в строку [latex]recipe[/latex].
  5. В лямбда-выражения параметры из тела программы передаются по ссылке. Возможность их изменения гарантируется ключевым словом [latex]mutable[/latex].

А394г

Задача
Дана целочисленная квадратная матрица порядка [latex]n[/latex]. Найти номера строк, элементы каждой из которых образуют образуют монотонную последовательность (монотонно убывающую или монотонно возрастающую).

*Строки матрицы нумеруются с единицы, потому их номера в выводе больше соответствующих индексов в массиве на единицу.
Тесты

[latex]n[/latex] Матрица Результат Комментарий
1 0 1 Квадратная матрица первого порядка состоит из одного элемента, следовательно, является и монотонно возрастающей, и монотонно убывающей.
3
1 1 1
2 2 2
3 3 3
Все элементы каждой строки попарно равны.
4
1 2 2 1
0 1 2 3
0.3 11 -2 3
0 0 1 1
2 В прочих строках монотонность нарушается
3
1 2 2
-1 10 15
3 2 1
2, 3 В первой строке последовательность возрастает нестрого.

Алгоритм решения

  1. Анализировать строку на монотонность можно при помощи знака разности соседних элементов. Если при движении по строке слева направо знак изменяется, последовательность не может быть монотонной (дополнительное ограничение для строгой монотонности: разность не должна равняться нулю).
  2. Отдельно следует рассматривать случай [latex]n \le 1[/latex]. По определению, последовательность [latex]\left\{ { a }_{ n } \right\}[/latex] — монотонна [latex]\Leftrightarrow \forall i,j\in N, j>i: a_{ i }\prec a_{ j } (a_{ i }\succ a_{ j })[/latex]. Последовательность из одного элемента имеет вид [latex]\left\{a_{n}\right\} = a_{1}[/latex], следовательно, невозможно выбрать такие [latex]i,j \in N ,j>i[/latex], чтобы выполнилось условие строгой монотонности. Рассмотренный пример является частным случаем понятия «vacuous truth», часто применяемого при доказательстве теорем.

Программный код

Детали реализации

  1. Считывание элементов строки может прекратиться в трех случаях: если монотонность сменяется с возрастания на убывание (или наоборот), или если найдены два равных соседних элемента. Для выхода из внутреннего цикла применяется присваивание [latex]j = n[/latex].
  2. Для корректной работы внутреннего цикла первый элемент строки считывается перед ним.
  3. Проверить, изменяется ли знак разности соседних элементов последовательности можно двумя способами: первый подразумевает умножение двух разностей, второй — реализацию функции signum(). Так как при умножении можно выйти за границы типа, выбран был второй способ.

Программа доступна для тестирования по ссылке: http://ideone.com/n60As6.
Реализация на Java: http://ideone.com/CnFow1

Ю11.16

Задача:
Для заданной матрицы [latex]A(n, n)[/latex] найти обратную [latex]A^{-1}[/latex], используя итерационную формулу:
[latex]A_{k}^{-1} = A_{k-1}^{-1}(2E-A A_{k}^{-1}),[/latex]
где [latex]E[/latex] — единичная матрица, [latex]A_{0}^{-1} = E[/latex]. Итерационный процесс заканчивается, если для заданной погрешности [latex]\varepsilon[/latex] справедливо:
[latex]\left| det(A A_{k}^{-1})-1 \right| \le \varepsilon[/latex]

Анализ задачи:
Прежде чем приступать к решению средствами языка C++, я создал прототип в системе компьютерной алгебры Wolfram Mathematica, с которым планировал сверяться при тестировании программы. Тем не менее, внимательный анализ показал, что с таким выбором начального приближения процесс уже на пятом шаге в значительной мере расходится даже для матриц размера 2*2. После уточнения условий и анализа дополнительного материала, посвященного методу Ньютона-Шульца, исходное приближение было изменено (по результатам исследования «An Improved Newton Iteration for the Generalized Inverse of a Matrix, with Applications», Victor Pan, Robert Schreiber, стр. 8):
[latex]A_{0}^{-1} =\frac { A }{ \left\| A \right\|_{1} \left\| A \right\| _{\infty } }[/latex], где [latex]{ \left\| A \right\| }_{ 1 }=\max _{ i }{ \sum _{ j=0 }^{ n-1 }{ \left| { a }_{ ij } \right| } } [/latex], [latex]{ \left\| A \right\| }_{ \infty }=\max _{ j }{ \sum _{ i=0 }^{ n-1 }{ \left| { a }_{ ij } \right| } }[/latex].
Эффективность предложенного подхода иллюстрируют результаты работы прототипа:
процесс сходится
Следовательно, из пространства задачи можно переместиться в пространство решения и составить алгоритм реализации предложенного метода на языке C++.

Тесты:

[latex]n[/latex] [latex]A[/latex] [latex]A^{-1}[/latex] Результат
3 1 2 3
5 5 7
11 13 7
-0.964771 0.430661 -0.017183
0.723533 -0.447973 0.137884
0.172358 0.155200 -0.086211
Пройден
2 1 2
2 1
-0.333067 0.666400
0.666400 -0.333067
Пройден
5 1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
Пройден
3 1 2 3
4 5 6
7 8 9
Матрица вырождена Пройден

Программный код:

Программа доступна для тестирования по ссылке: http://ideone.com/7YphoX.

Алгоритм решения
При решении данной задачи оправдывает себя подход «разделяй и властвуй»: вычисление обратной матрицы подразумевает промежуточные этапы, корректной реализации которых следует уделить особое внимание. Наверняка стоило бы написать класс matrix и реализовать перегрузку операций, но задачу можно решить и без применения объектно-ориентированных средств, пусть от этого решение и потеряет в изящности.
Можно выделить следующие подзадачи:

  1. Инициализация динамического двухмерного массива и передача его в функцию.
  2. Вычисление определителя матрицы (с применением метода Гаусса).
  3. Вычисление нормы матрицы.
  4. Транспонирование матрицы.
  5. Умножение матрицы на скаляр.
  6. Матричное умножение матриц.
  7. Сложение двух матриц.
  8. Непосредственно итерационный процесс Ньютона-Шульца

Ниже приведено пояснение к подходу к реализации некоторых подзадач:

  • Выделение памяти для хранения массива происходит не на этапе запуска программы, после компиляции. Для инициализации использован конструктор new
  • Вычисление определителя можно разбить на два последовательных шага:
    1. Приведение матрицы к верхнетреугольному виду (методом Гаусса).
    2. Вычисление определителя как произведения элементов главной диагонали.
    3. Если матрица вырождена, то дальнейшие вычисления не производятся.

  • Нормы матрицы вычисляются как максимальные значения суммы элементов по столбцам и строкам соответственно.
  • При транспонировании обмениваются местами элементы, симметричные главной диагонали.
  • При умножении матрицы на скаляр каждый элемент матрицы умножается на соответствующее вещественное число.
  • При перемножении двух квадратных матриц используется промежуточный массив для хранения результата вычислений.
  • Сложение двух матриц аналогично попарному сложению элементов, расположенных на соответствующих позициях.
  • Максимально допустимая погрешность для метода Ньютона-Шульца [latex]\varepsilon = 0.001[/latex]. Программа использует локальный массив для хранения [latex]A_{k}^{-1}[/latex], инициализация которого происходит в теле цикла.

Технические детали реализации:
При выполнении подзадач часто приходится использовать локальные массивы, так что для очистки выделенной под них памяти создана отдельная функция clear().

Ю4.28

Задача:
Каждый из элементов [latex]x_{i}[/latex]массива [latex]X(n)[/latex] заменить средним значением первых [latex]i[/latex] элементов этого массива.

Тесты

[latex]n[/latex] Input Output Result
2 11 7 11 9 Пройден
12 7 4 33 56 22 3 22 5 6 7 8 9 7 7 5.5 14.667 24.4 20.833 21 19 17.556 16.5 15.7273 15.1667 Пройден
1 136 136 Пройден
3 -1 1 0 1 0 0 Пройден

Программный код:

Задача достаточно простая, так что стадию анализа можно пропустить и перейти сразу к алгоритму решения.

Алгоритм решения
Заполнение массива происходит последовательно. Следовательно, замену можно производить на лету, сразу же после ввода каждого элемента, что и происходит в программе.

Детали реализации:
Для вывода массива на экран использован цикл в стиле С++11.

Реализация на Java: http://ideone.com/gMXpf6

Conway Sequence


Conway Sequence


Conway Sequence — седьмая по счету игра уровня сложности medium, основанная на свойствах последовательности Конвея (правильнее было бы назвать её look-and-say sequence). Последовательность рекурсивна, но в более широком понимании: предыдущая строка полностью характеризует текущую. Изучение последовательности Конвея приводит к занятным открытиям, включая так называемую космологическую теорему, но лучше меня об этом расскажет лично Джон Хортон Конвей. Но начиная с определенного номера получить новую строку становится непросто даже на бумаге. Авторы просят нас помочь математикам и составить программу, которая по заданным значениям выводит определенную строку последовательности.

Алгоритм вывода следующей строки уместно проиллюстрировать на примере:
Sequence seed: 3
Строка №1 имеет вид: «3»
В ней записана одна тройка.
Следовательно, строка №2 запишется как: «1 3».
В ней записаны одна единица и одна тройка
Следовательно, строка №3 выглядит так: «1 1 1 3».
В ней содержатся три единицы и одна тройка,
потому строка №4 имеет вид: «3 1 1 3» et cetera.

Входные данные:

  • [latex]R[/latex] — основание последовательности («sequence seed»)
  • [latex]L[/latex] — номер последней строки

Выходные данные:
Строка №[latex]L[/latex], все элементы которой разделены пробелами.

Код программы:

Алгоритм решения:

  1. Начать просмотр содержимого строки слева направо. Если подряд идут несколько одинаковых чисел, запомнить их количество.
  2. Если следующее число в строке отлично от предыдущего записать в новую строку количество повторов предыдущего числа и само это число.
  3. Если строка подошла к концу, дописать к новой строке количество повторений последнего элемента и сам этот элемент.
  4. Если номер полученной строки меньше [latex]L[/latex], повторить процедуру для новой строки.

Эффективность алгоритма:
Программа успешно проходит все данные тесты.

conway_result

Технические детали реализации:

  • Для удобства работы с строками произвольной длины использована библиотека vector, в частности функции .clear(), .push_back(), .size(), .swap()
  • Так как принципиальное значение имеют только три факта: значение текущего элемента последовательности, значение предыдущего и количество подряд идущих одинаковых элементов, стоящих за ним — достаточно завести три переменные типа int для их хранения.
  • На каждой итерации вектор [latex]next\_line[/latex] копируется в вектор [latex]current\_line[/latex] и очищается. Переменной [latex]previous[/latex] присваивается значение первого элемента вектора [latex]current\_line[/latex].

Skynet: The Chasm

Вторая по списку игра на сайте codingame.com проверяет умение примата пользоваться условными операторами, интуицией и программой по физике за десятый класс. По легенде, на постапокалиптических просторах Земли будущего раскинулась зловещая империя враждебных человеку роботов, но инженерный гений непокоренных программистов-взломщиков дает человечеству шанс на выживание. Подрывная деятельность начинается с малого: под дистанционный контроль удалось взять кремниевые мозги скоростного робота, внешностью и повадками напоминающего модифицированный мотоцикл. Наша задача — создать алгоритм управления, позволяющий машине преодолевать препятствия.

Инициализация:
Каждый уровень поделен на три этапа:

  1. Движение по стартовой площадке.
  2. Прыжок через пропасть.
  3. Торможение на финишной прямой.

До начала игрового цикла программа считывает данные о длине каждого из элементов уровня и сохраняет соответственно в переменные [latex]R, G, L[/latex].

Игровой цикл
На каждой итерации входной поток содержит:

  1. Координату мотоцикла [latex]X[/latex].
  2. Мгновенную скорость мотоцикла [latex]S[/latex].

В выходной поток необходимо вывести одну из четырех команд:

  1. JUMP — совершить прыжок.
  2. SPEED — увеличить скорость на единицу.
  3. SLOW — уменьшить скорость на единицу.
  4. WAIT — ждать следующего хода.

Прежде чем приступить к решению, проанализируем и формализуем задачу.
Continue reading

А165и

Задача:
Даны действительные числа [latex]a_1 , a_2,\ldots[/latex]. Известно, что [latex]a_{1} > 0[/latex] и
что среди [latex]a_2 , a_3,\ldots[/latex] есть хотя бы одно отрицательное число. Пусть
[latex]a_{1} ,\ldots, a_{n}[/latex] – члены данной последовательности, предшествующие
первому отрицательному члену ( n заранее неизвестно). Получить:
и) [latex]n+a_{n}[/latex];

Тесты:

Последовательность [latex]a_{i}[/latex] [latex]n+a_{n}[/latex] Результат
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 -6 24 Пройден
2.7183 -0.0001 3.7183 Пройден
2.7182 81 28 -90 45 -90 31 Пройден

Алгоритм решения:

  1. Ввод элементов последовательности продолжается до первого отрицательного числа. Следовательно, можно создать бесконечный цикл, выход из которого осуществляется по условию.
  2. Если введенное число меньше нуля, происходит выход из цикла. В противном случае текущее количество элементов последовательности увеличивается на единицу, а введенное значение сохраняется в вспомогательную переменную.
  3. После выхода из цикла имеем значение последнего элемента, удовлетворяющего условию, и его номер. Этих данных достаточно для решения поставленной задачи.

Код программы:

Детали реализации:
Ввод элементов последовательности осуществляется средствами языка Си через подключенный заголовочный файл <cstdio>. Числа из входного потока сохраняются в переменную целочисленного типа с двойной точностью double, так как по условию являются вещественными.
Протестировать программу можно по ссылке: http://ideone.com/qn7kfJ
Реализация на Java: http://ideone.com/rHCk2X

WoW 2. В следующее измерение!

Задача
Две землеройки постоянно находятся на спине питона в точках [latex]A[/latex] и [latex]C[/latex]. Однако, по неизвестной причине в момент времени [latex]t_A[/latex] первая землеройка отправляется в пункт [latex]B[/latex] с расчётным временем прибытия [latex]t_B[/latex]. Поскольку такое поведения является характерным для землероек вообще, вторая поступила также и в момент времени [latex]t_C[/latex] отправилась в пункт [latex]D[/latex] с расчётным временем прибытия [latex]t_D[/latex]. На новом месте землеройки в дальнейшем планирует находиться постоянно. Известно, что землеройки обычно движутся по питонам с постоянной скоростью стараясь держаться центра спины, чтобы не соскальзывать. Питоны же во время движения землероек спокойно лежат без самопересечений.
Дано:
Точки [latex]A[/latex], [latex]B[/latex], [latex]C[/latex], [latex]D[/latex] задаются расстоянием от кончика хвоста питона, измеренным вдоль обычного маршрута землероек. Время старта и прибытия землероек также задано. Входные данные задаются целыми числами не превосходящими по модулю 10000 в следующем формате:

A t_A
B t_B
C t_C
D t_D

Найти:
Необходимо определить, удастся ли землеройкам проделать этот маневр или в результате столкновения они свалятся с питона. Если питону удастся избавиться от докучливых землероек выведите “Yes”, в противном питону случае – “No”.
Continue reading

WoW 3: Идем к ним?

Задача Идем к ним?
«У крота и землеройки имеется [latex]n[/latex] зёрен чего-то вкусного. Они по очереди съедают любое количество зерен, но не более половины оставшегося количества. Можно съедать только целое число зёрен. Если игрок не может сделать очередной ход, то он считается проигравшим и ему приходится бежать в магазин за следующей порцией вкусных зёрен. На каждом шаге можно съедать не более [latex]m[/latex]-й части оставшихся зёрен. Составьте программу, которая определяет величину первого выигрышного хода по заданным числам n и m. Если выигрышного хода нет, то нужно вывести [latex]-1[/latex].»

Анализ задачи:

  1. Первыми в голову приходят методы решения, основанные на полном переборе или на поиске производящей функции (к примеру, для [latex]m = 2[/latex] все позиции [latex]n = 2^{k}-1[/latex] — проигрышные), но количество стратегий растет достаточно быстро, а выделение закономерностей в рекурсивных последовательностях — задача нетривиальная. Следовательно, имеет смысл продолжить анализ, но уже с применением теории игр.
  2. Предложенная игра представляет собой версию игры ним. Отличие в том, что множество объектов одно, а количество допустимых на данном шаге ходов зависит от ситуации на игровом поле.
  3. Эффективный поиск выигрышного хода можно провести при помощи функции Шпрага-Гранди.
  4. Выигрышные позиции отличаются только расстоянием до проигрышной для противника (в зернах), следовательно, можно воспользоваться выигрышно-проигрышным разбиением позиций и ввести соответстенные характеристики позиций: [latex]\left\{ 1, -1 \right\}[/latex].
  5. Если все позиции, в которые можно попасть из данной, являются выигрышными для противника (при условии, что он не играет в поддавки), считать её проигрышной.

Алгоритм решения:

  1. Построение базы анализа: позиция [latex]n = m[/latex] — выигрышная (единственным доступным ходом мы заканчиваем игру), следовательно, [latex]n = m + 1[/latex] — проигрышная.
  2. Если на расстоянии [latex]\left\lfloor \frac {step}{m} \right\rfloor [/latex] от текущей позиции [latex]step[/latex] все значения равны [latex]1[/latex], пометить [latex]step[/latex] как [latex]-1[/latex]. В противном случае пометить как [latex]1[/latex].
  3. Если значение для [latex]step = n-1[/latex], то вывести на экран [latex]-1[/latex]. В противном случае вывести расстояние до ближайшей проигрышной для противника позиции.

Результаты тестирования:
Для всех [latex]n[/latex] при [latex]m = 2[/latex] программа предсказуемо выдает последовательность проигрышных ходов при [latex]n = 2^{k}-1[/latex].
На малых значениях [latex]n[/latex] при [latex]m > 2[/latex] установлена корректность алгоритма.

n m Результат
7 2 -1
8 2 1
10 3 3
7 3 -1
12 4 2
10 4 -1

Код программы:

Детали реализации:
Для хранения характеристик позиций использован динамически объявляемый массив (VLA — Variable Length Array). Для упрощения анализа использована булева переменная [latex]good[/latex].При решении применялись методы динамического программирования.
Протестировать работу программы можно по ссылке: http://ideone.com/5nmDxl.
Реализация на Java: http://ideone.com/D5R49n

Ю3.44

Задача: Леспромхоз ведёт заготовку деловой древесины. Первоначальный объем её на территории леспромхоза составлял [latex]p[/latex] кубометров. Ежегодный прирост составляет [latex]k[/latex]%. Годовой план заготовки — [latex]t[/latex] кубометров. Через сколько лет в бывшем лесу будут расти одни опята?

  1. Тесты:
[latex]p[/latex] [latex]k[/latex]% [latex]t[/latex] [latex]years[/latex] Комментарий
111.50 14.57 16 Никогда Пройден: прирост компенсирует вырубку
0 0 0 0 Пройден: абстрактный случай, но результат верный
20 10 30 1 Пройден
200 30 61 16 Пройден
  1. Программный код:

  1. Формализация задачи:
    Дано начальное значение [latex]p \ge 0[/latex]. На [latex]i[/latex]-м шаге оставшийся объем древесины вычисляется из рекуррентного соотношения: [latex]p_{i} = p_{i-1} (1 + \frac {k}{100})-t[/latex]. (*)
    Определить шаг [latex]i[/latex] такой, что [latex]p_{i}<0[/latex].

  2. Алгоритм решения:
    Шаг 1: Проверка условия [latex]p_{1}[/latex] меньше [latex]p[/latex]. В случае, если если естественный прирост не компенсирует вырубку, начать рассчет. В противном случае лес никогда не опустеет, так как прирост и убыль скомпенсированы.
    Шаг 2: До тех пор, пока [latex]p_{i}>0[/latex], рассчитывать [latex]p_{i}[/latex] по соотношению (*), где [latex]i[/latex] — количество прошедших лет.

  3. Детали реализации:
    В задаче используются два типа данных: целочисленный и с плавающей точкой двойной точности. Выбор продиктован отсутствием указания на конкретный тип входных данных в условии задачи. Протестировать работу программы можно по ссылке.
    Реализация на Java: http://ideone.com/fyuDTg

Ю2.21

Задача: Имеются три раствора полезного вещества с концентрациями [latex]p_{1}, p_{2}, p_{3}[/latex] каждый и стоимостью [latex]s_{1}, s_{2}, s_{3}[/latex] соответственно. Можно ли смешать их так, чтобы получить раствор с заданной концентрацией [latex]p[/latex] наименьшей стоимости [latex]s[/latex]?
Указание. Пусть [latex]\alpha_{1}, \alpha_{2}, \alpha_{3}[/latex]- долевые содержания растворов в смеси. Тогда для получения заданной концентрации [latex]p[/latex] необходимо [latex]p_{1}\alpha_{1} + p_{2}\alpha_{2} + p_{3}\alpha_{3}=p[/latex].
Кроме того, нужно учесть условие «комплектности смеси»: [latex]\alpha_{1} + \alpha_{2} + \alpha_{3} = 1[/latex]; [latex]\alpha_{1} \ge 0; \alpha_{2} \ge 0; \alpha_{3} \ge 0;[/latex]
При этих условиях необходимо найти наименьшее значение линейной функции: [latex]s = \min _{ \alpha_{1}, \alpha_{2}, \alpha_{3} } { ( s_{1} \alpha_{2} + s_{2} \alpha_{2} + s_{3} \alpha_{3} ) }[/latex].
С учётом ограничений задача сводится к минимизации линейной функции одного переменного на отрезке, однако искомые выражения и условия получаются достаточно громоздкими. Можно показать, что в решении будут участвовать не более двух растворов. Тогда достаточно среди вариантов:
а) [latex]\alpha_{1} = 0[/latex];
б) [latex]\alpha_{2} = 0[/latex];
в) [latex]\alpha_{3} = 0[/latex];
Выбрать оптимальный, и затем провести необходимые расчеты.
Тесты

1 2 3 p s Комментарий
[latex]p_{i}[/latex] 0 0 0 0 10 Пройден
[latex]s_{i}[/latex] 10 12 14
[latex]p_{i}[/latex] 0 10 30 0 10 Пройден
[latex]s_{i}[/latex] 10 20 30
[latex]p_{i}[/latex] 15.3 49.2 51.6 37.4 29.56 Пройден
[latex]s_{i}[/latex] 40 10 20
[latex]p_{i}[/latex] 30 30 30 40 Impossible Пройден
[latex]s_{i}[/latex] 25 14 40
[latex]p_{i}[/latex] 20.3 20.3 20.3 20.3 30 Пройден
[latex]s_{i}[/latex] 30 40 50
[latex]p_{i}[/latex] 30 40 50 20 Impossible Пройден
[latex]s_{i}[/latex] 19 31 22
[latex]p_{i}[/latex] 20 60 80 40 40 Пройден
[latex]s_{i}[/latex] 60 20 100
[latex]p_{i}[/latex] 20 50 90 50 15.71 Пройден
[latex]s_{i}[/latex] 10 80 20
[latex]p_{i}[/latex] 10 60 90 62.5 62.5 Пройден
[latex]s_{i}[/latex] 190 10 20

Код программы:

Метод решения:
Задача сводится к решению системы уравнений:
[latex]\begin{cases} p_{1} \alpha_{2} + p_{2} \alpha_{2} + p_{3} \alpha_{3} = p,\\ \alpha_{1} + \alpha_{2} + \alpha_{3} = 1,\\ s = \min _{ \alpha_{1}, \alpha_{2}, \alpha_{3} } { ( s_{1} \alpha_{2} + s_{2} \alpha_{2} + s_{3} \alpha_{3} ) }; \end{cases}[/latex]

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

Аналитическое решение в данном случае тривиально:
[latex]\begin{cases} p_{i} \alpha_{i} + p_{j} \alpha_{j} = p,\\ \alpha_{i} + \alpha_{j} = 1; \end{cases} \Rightarrow \begin{cases} \alpha_{i} = \frac { p-p_{i} } { p_{j}-p_{i} },\\ \alpha_{j} = 1-\alpha_{i}; \end{cases} s = s_{i} \alpha_{i} + s_{j} \alpha_{j};[/latex]

Для большей наглядности применяется функция c_price (calculate price), в теле которой рассмотрены крайние случаи:
1) Если [latex]p_{1}=p_{2}=p[/latex], то нужно выбрать раствор наименьшей стоимости.
2) Если [latex]p_{1}=p_{2} \ne p[/latex], то решений нет.
3) Если [latex]p_{1}=p \ne p_{2}[/latex], то [latex]s = s_{1}[/latex]. Аналогично в случае [latex]p_{2}=p \ne p_{1}[/latex].
4) Если доля раствора в смеси [latex]\alpha 1[/latex], то решений нет.

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

Протестировать работу программы можно по ссылке.
Реализация на Java: http://ideone.com/qTQpMX

Ю 3.4

Задача: Прямоугольник на плоскости [latex]a \le x \le b, \quad c \le y \le d[/latex] задаётся четырьмя числами (его габаритами): [latex]a, b, c, d.[/latex] Последовательно вводятся габариты [latex]n[/latex] прямоугольников. В процессе ввода находить площадь их пересечения, не запоминая самих габаритов.

NI — «no intersection» — нет общего сегмента

[latex]a[/latex] [latex]b[/latex] [latex]c[/latex] [latex]d[/latex] [latex]S[/latex] Комментарий
1 -5 -3 1 4 NI Пройден: нет общего интервала
-2 0 1 4
2 0 4.5 1.2 4.6 NI Пройден: нет общего интервала
2 4 5 7.4
3 2 5 1 4 NI Пройден: общая сторона не считается пересечением, т.к. даёт нулевую площадь
5 6 1 4
4 2 4 2 4 4 Пройден
2 4 2 4
5 2 5 1 4 NI Пройден: не все данные прямоугольники имеют общий сегмент
0 3 2 3
6 7 3 5
6 0 7 0 3 1 Пройден
2 6 1 5
3 5 2 5
4 8 2 3

 

Алгоритм решения:
1. Для удобства, запрограммировать задачу можно, сведя её к одномерному случаю: рассматривать проекции сторон прямоугольников на координатные оси. (см. рис. 1)
2. Проверка на пересечение: данные прямоугольники пересекаются и имеют общую площадь, если их проекции имеют общий интервал значений, больший одной точки.
3. Так как запоминать габариты прямоугольников нельзя по условию, работать будем с габаритами «общего» прямоугольника, которые сохраняются соотв. в переменные [latex]x1 \le x2, y1 \le y2[/latex]. Если новый прямоугольник пересекается с «общим», то определить обновленные габариты общего прямоугольника и рассчитать площадь(см. рис. 2). Если не пересекается, то выполнение программы прерывается, т.к. нужно вывести площадь прямоугольника, общего для всех [latex]n[/latex] прямоугольников.

Значения переменных в условии задачи не ограничены, так что для хранения габаритов был использован тип double, для всех порядковых переменных — тип int.

Протестировать решение можно по ссылке.