Ответы к экзамену: Cистема eJudge Задачи

# Модуль 3

## Рюкзак(A)
Решите задачу о рюкзаке методом динамического программирования. Алгоритм должен быть инкапсулирован.

### Формат входных данных
Данные подаются на стандартный поток ввода. Пустые строки игнорируются.

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

Каждая последующая содержит два целых неотрицательных числа: массу предмета и его стоимость.

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

В последующих строках записаны номера предметов, которые были помещены в рюкзак, в порядке возрастания номера.

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

В любой непонятной ситуации результатом работы любой команды будет "error".

## Сумасшедший богач(B)
Один сумасшедший богач на старости лет впал в маразм и стал еще более сумасшедшим. Он решил отдать половину своих богатств тому, кто выиграет в математической игре.

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

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

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

### Формат входных данных
В стандартном потоке записано единственное натуральное число - размер половины состояния богача (в миллионах).

### Формат результата
Каждая строка выхода содержит ровно одну операцию (inc, dec или dbl) из кратчайшей последовательности действий для победы.

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

## Автокоррекция(C)
Реализуйте программу, которая предлагает варианты замены слова, в котором допущена одна ошибка.

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

Регистр букв для программы коррекции не имеет значения (слова в словаре хранятся в нижнем регистре).

Варианты ошибок - как в алгоритме Дамерау-Левенштейна: вставка лишнего символа, удаление символа, замена символа или транспозиция соседних символов.

### Формат входных данных
Данные подаются на стандартный поток ввода. Пустые строки игнорируются.

Первая строка содержит число N - количество слов в словаре.

Последующие N строк содержат слова из словаря, по одному в строке.

Остальные строки - слова, которые надо проверять.

### Формат результата
Каждая строка выхода содержит предложение для исправления слов, в порядке их появления.

Если слово не содержит ошибок, то выводится "%слово% - ok".

Если слово содержит одну ошибку, то выводится "%слово% -> %слово_в_словаре%". Если вариантов несколько, то они разделяются запятой с пробелом.

Если слово содержит более одной ошибки, то выводится "%слово% -?"

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