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

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

Изначально пандорианцы обладают запасом золота в 10 золотых слитков. Они решили в один из дней года купить на все это золото воды, а в какой-то последующий день продать всю купленную воду и получить прибыль за счет разницы стоимости. К примеру, если бы стоимость воды в день покупки составляла 1 литр за 4 золотых слитка, а стоимость воды в день продажи – 1 литр за 6 золотых слитков, то пандорианцы могли бы получить купить \(\frac{10}{4}=2.5\) литра воды, а продать они эту воду смогут за \(2.5 \times 6=15\) золотых слитков. Таким образом, прибыль пандорианцев составила бы \(15-10=5\) золотых слитков. Конечно же, пандорианцы хотят максимизировать свой доход в результате этих махинаций. Помогите им выбрать оптимальные дни для покупки и продажи воды!

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

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

Компания RectanGas почти выполнила свой план по добыче нефти на май 2010 года. Для этого ей осталось добыть ровно S баррелей нефти. Заметим, что больше добывать нельзя, иначе компанию обвинят в монополии. Меньше добывать тоже нельзя, потому что исполнительный директор, будучи человеком пунктуальным, очень огорчится, что повлечет за собой увольнение сотрудников и всеобщую безработицу. Геологи, подробно изучив карту местности, определили количество залежей нефти на каждом участке и попросили Вас написать программу, определяющую координаты будущих нефтяных вышек с учетом всех требований.

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

Прямо сейчас юный исследователь полностью поглощён изучением хорошести строк. Хорошестью строки называется количество позиций от 1 до L - 1 (где L — длина строки), таких, что следующая буква в строке является следующей по алфавиту. Например, хорошесть строки "abcdefghijklmnopqrstuvwxyz" равна 25, а строки "abdc" — только 1.

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

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

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

В приведённом примере таблица имеет размер \(4\times5\), в ней символом "I" помечены защищённые клетки. Видно, что двух вирусов достаточно для заражения всей области. Их можно поместить, например, в клетки, помеченные символом "V".