Задачи районных командных соревнований для школьников 1998

Дана квадратная матрица целых чисел размером `N\ times\ N` (`1\ ≤\ N\ ≤\ 50`). Числа в матрице лежат в диапазоне от –99 до 99. Существует `C_{2*(N-1)}^{N-1}` возможных путей от верхнего левого угла матрицы до нижнего правого угла, если разрешено двигаться по одной клетке вниз или вправо. Найти путь с максимальной суммой чисел (если таких путей несколько, то вывести любой из них).

В первой строке входного файла задан размер матрицы `N`, в последующих `N` строках по `N` целых чисел, разделенных одним или более пробелов (длина строки не превышает 200 символов).

В выходной файл в первой строке выводится найденный максимум, в следующей строке – числа, через которые проходит этот путь.

3
1 2 3
4 5 6
1 2 3

19
1 4 5 6 3

На планете Шелезяка живут роботы, которые делают новых роботов. Группа из двух роботов за год может изготовить 3 робота, а группа из трех роботов – 5 новых роботов. В одиночку робот работать не может! Космические пираты, побывав на планете Шелезяка, насыпали песка в цистерну с машинным маслом. Большинство роботов вышло из строя, осталось только k новых роботов, но смазка сократила время их работоспособности до 1 года. Эти роботы придумали более совершенных роботов, с меньшим количеством трущихся деталей, которые на той же смазке могли работать уже 2 года, и начали их производство. Каждое новое поколение роботов (за счет различных усовершенствований) может работать на год больше предыдущего поколения. Роботы, изготовленные в первый год, работают 2 года, во второй – 3 года, в третий – 4 года и т.д. Требуется найти, какое максимальное число работающих роботов может быть на планете через `n` лет, если первоначально было `k` роботов.

В первой строке входного файла содержатся два целых числа: первоначальное количество роботов `k` и (через пробел) – количество лет `n` `(1\ ≤\ k,\ n\ ≤\ 100)`.

В выходной файл выводится число роботов через `n` лет.

3 3 

29

Подсчитать на сколько частей разрезан прямоугольник из клетчатой бумаги размером `N\ times\ M` (`1\ ≤\ N,\ M\ ≤\ 10`), если разрезы делаются только по линиям клеток листа (по вертикали или по горизонтали).

Черные линии на рисунке изображают сделанные разрезы.

В первой строке входного файла заданы размеры прямоугольника `N` и через пробел `М`, во второй строке – количество разрезов `k` (`0\ ≤\ k\ ≤\ 2*N*M-N-M`), в последующих `k` строках – информация о разрезах в виде:

H `i\ j\ l` – горизонтальный разрез в строке `i`, начиная с колонки `j`, длиной `l`.

V `i\ j\ l` – вертикальный разрез в колонке `j`, начиная со строки `i`, длиной `l`.

Верхняя граница прямоугольника считается 0-й строкой, а левая – 0-м столбцом.

В выходной файл вывести количество получившихся частей.

4 5
9
H 1 1 1
H 1 4 1
H 2 1 1
H 3 2 3
V 1 1 2
V 0 2 1
V 2 2 2
V 0 3 2
V 0 4 3

5

В старой детской игре "Виселица" один игрок загадывает слово, а другой пытается его угадать, называя по одной буквы. Если буквы нет в этом слове, то рисуется один из элементов картинки (вся картинка состоит из 7 элементов: эшафот, виселица, веревка, голова, руки, туловище и ноги). Если игрок угадывает букву, то буква (или буквы, если имеется несколько одинаковых букв) пишется на соответствующем ей месте. Если вся картинка будет нарисована, а слово не угадано, то игрок проигрывает. Если все буквы слова будут открыты, а картинка еще не дорисована, то игрок выигрывает. Буквы "и" (ASCII-код 168) и "й" (ASCII-код 169) считаются одной буквой, буква "ё" в игре не используется.

Требуется по слову и последовательности названных букв определить результат игры.

В первой строке входного файла – загаданное слово, сотоящее только из строчных русских букв, а во второй – названная последовательность букв (тоже строчные русские), не более 32 букв.

Вывести одну из трех строк:

Win – выигрыш,

Lose – проигрыш,

Unknown – при исчерпании набора букв и невыполнении условий выигрыша или проигрыша.

попугай
анеопрстузгй

Win

Составить мини-кроссворд из заданных 3 слов по обычным правилам и напечатать его. Все слова должны пересекаться между собой. Пересекающиеся слова должны быть взаимно перпендикулярны (если одно из них расположено вертикально, то другое должно быть горизонтально). Буквы "И" и "Й" считаются разными буквами. Слова, расположенные в параллельных столбцах или строках, должны быть разделены как минимум одним пустым столбцом или строкой, за исключением случая, когда параллельные слова не накладываются друг на друга (см. пример).

 B         B 
PELE    PELE 
 ADD       ADD 
 R         R

нельзя  можно

В первой строке входного файла записаны через пробел три слова прописными буквами. Длина слов от 2 до 25 букв.

В выходной файл выводится получившийся кроссворд или сообщение "Impossible".

УДАВ ПОПУГАЙ ОБЕЗЬЯНА

    ПОПУГАЙ
       Д
ОБЕЗЬЯНА
       В