(Можна розглянути частковий випадок, коли вантажі перевозяться тільки в порядку їх нумерації). (10 балів)

 

Задача 2. Трикутник (20 балів)

Задано точку з координатами (х, у) і трикутник з координатами вершин (х1, у1), (х2, у2), (х3, у3). Визначте, чи лежить точка всередині чи зовні трикутника.

 

Задача 3. Банківська справа (40 балів)

Молодий ломбардець Гучно Бальйоні (герой серії творів французького письменника Моріса Дрюона) часто виконував таємні доручення сучасних йому можновладців Франції, Англії та Італії. Не маючи можливості протягом трьох років безпосередньо самому займатися справами, він вирішив отримати зиск, вклавши гроші у справи паризьких банкірів. Виявилося, що розмір винагороди (% зиску) різний у різних банкірів. Звичайно, чим більшу суму він дасть банкіру, тим більшу суму отримає через 3 роки, і не менше, ніж дав банкіру. Але в кожного банкіра % зиску різний для різних сум. Нажаль, за розрахунками Гучно, йому ніколи не отримати більше 1000 ліврів (середньовічних французьких монет).

Завдання

Створіть програму profit.*, яка допоможе молодому ломбардцю отримати якнайбільші статки.

Вхідні дані

Перший рядок вхідного файлу profit.in у вказаному порядку містить 2 натуральних числа:

m – кількість ліврів, яку молодий Гучно може використати для збагачення;

n – кількість паризьких банкірів.

Тут m і n не перевищують 100. Для j в межах від 1 до m  (j+1)-ий рядок цього файлу містить послідовність n натуральних чисел. k-ий член цієї послідовності – це кількість монет, яку отримає Гучно через три роки від k-го банкіра, віддавши йому j монет перед від’їздом.

Вихідні дані

Перший рядок вихідного файлу profit.out має містити найбільшу кількість ліврів, яку може мати молодий ломбардець через 3 роки, використавши m ліврів належним чином. Другий рядок цього ж файлу має містити послідовність n невід’ємних цілих чисел. k-ий член цієї послідовності – це кількість ліврів, яку має дати Гучно k-му банкіру, щоб отримати максимальний зиск від своїх капіталовкладень (потрібно подати хоча б один з варіантів розподілу).

Приклад

 

profit.in

3 10

 

1 1 6 2 2 5 2 1 3 3

2 4 7 8 3 7 8 4 8 5

7 10 12 10 4 9 11 6 13 7

 

profit.out

14

0 0 1 2 0 0 0 0 0 0

Завантажити повністю у doc форматі