#1596

Седловые точки

Темы: [Двумерные массивы]

В двумерном массиве размерностью \(n\) × \(m\), все элементы которого различны, требуется найти такие элементы, которые одновременно являются минимальными в своей строке и максимальными в своем столбце.

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

В первой строке входных данных находятся натуральные числа \(n\), \(m\), \(k\) ≤ 100. В следующих \(n\) строках входных данных расположены по \(m\) натуральных чисел, не превосходящих 10 000.

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

Выведите пары индексов искомых элементов, каждую в отдельной строке. Нумерация строк и столбцов начинается с единицы. Если искомых элементов нет, то выведите 0.

Примеры

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

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

3 1

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

2 2
3 1
2 4

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

#1597

Темы: [Двумерные массивы]

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

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

Шахматная доска описывается в восьми строках входных данных. Первые восемь символов каждой из этих строк описывают состояние соответствующей горизонтали: символ B (заглавная латинская буква) означает, что в клетке стоит слон, символ R – ладья, символ * – что клетка пуста.

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

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

Примеры

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

********
********
*R******
********
********
********
********
********

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

#1599

Темы: [Строки]

Фраза называется палиндромом (перевертышем), если после удаления пробелов и замены всех букв на заглавные она читается одинаково, как слева направо, так и справа налево. Требуется определить, является ли введенная фраза палиндромом.

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

На вход программе подается строка, состоящая не более чем из 255 символов.

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

Выведите YES или NO в зависимости от ответа на вопрос задачи. Примечание. Для русских букв, записанных в кодировке Windows- 1251, можно считать, что коды заглавных и строчных букв отличаются на 32.

#1613

Разрезать четырехугольник

Темы: [Элементарная геометрия]

Дан выпуклый четырехугольник ABCD с ненулевой площадью. Найти точку O, принадлежащую какой-либо стороне четырехугольника, что площади фигур, полученных в результате разреза исходного четырехугольника по линии AO, были бы равны.

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

вводятся координаты 4 точек (целые, по модулю не превышают 100). Гарантируется, что никакие три точки не лежат на одной прямой.

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

вывести координаты точки O с точностью до 4 знака после запятой.

Примеры

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

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

0 2

#1615

Замена робота

Темы: [Динамическое программирование]

Дан новый промышленный робот, максимальный срок службы которого не ограничен. Однако, все механизмы со временем теряют свою ценность, производительность и требуют больше затрат на ремонт. Известно, что затраты на обслуживание робота в \(i\)-м году от начала эксплуатации составляют \(C_i\), прибыль, которую приносит робот за \(i\)-й год своей работы составляет \(P_i\). Также в конце любого года можно продать старого робота и купить нового. Цена нового робота не зависит от времени и равна \(S\). Цена подержанного робота, прослужившего \(i\) лет равна \(R_i\). Определите оптимальный график замены роботов в течение \(N\) лет (то есть чтобы суммарная прибыль от использования была максимальна).

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

в первой строке вводятся числа \(N\) – расчетный период времени (натуральное, не превышает 100) и \(S\) (натуральное, не превышает \(10^5\)) – цена нового робота. В следующей строке указано \(N\) чисел (натуральные, не превышают 500) – затраты на обслуживание робота в течение соответствующего года. В следующей строке следует еще \(N\) чисел (натуральные, не превышают 500) - прибыль, которую приносит робот в соответствующие годы, затем еще \(N\) чисел (натуральные, не превышают 500) – цена подержанного робота, в зависимости от возраста.

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

Выведите максимальную прибыль, которую можно получить к концу \(N\)-го года, при оптимальной смене роботов.

Обратите внимание: рассматривается только операция замены робота. То есть если в конце \(N\)-го года вы решите продать робота, то это означает автоматическую покупку нового. То есть робот, проданный после расчетного периода чистой прибыли не приносит.

Комментарий

если робот работает 2 года без замены, то он приносит прибыли на 100+95=195 и требует 2+3=5 на обслуживание; если мы решим в конце 1-го года заменить робота на нового, то мы получим: 100+100=200 (новый робот будет приносить прибыль 100, так как работает 1-й года) + 90 (выручка от продажи старого робота) мы потеряем: 2+2=4 (новый робот также будет требовать затрат за свой первый год) -100 – уплатим за нового робота итого +200+90-100-4=186. Следовательно, первый вариант предпочтительнее

Примеры

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

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