|
Четвертий тур
Розв’язок задачі відправляти на адресу:
gymnasiya@gor.lutsk.ua
до 12.12.2004 р.
Лист повинний містити розв’язок однієї задачі.
Тема листа VIO
Вміст листа
Код учасника ...
Код задачі VIO_4
Мова програмування в якій розв’язана задача ...
Розв’язок задачі розмістити, як вкладений текстовий файл з іменем коду завдання програмного коду розв’язку задачі.
Задача: (100 балів)
Koд: VIO_4
Умова
Великий мандрівник прибув на своєму кораблі в невідому країну. На базарі він побачив багато дивних товарів. Він
вирішив закупити ці товари.
Нехай на базарі є товари Р1, Р2,...,Рn, 1<=n<=1000 (кожний товар в єдиному екземплярі). Відомо вагу кожного товару
g1, g2,...,gn і його вартість С1, С2,..., Сn. На корабель можна завантажити товарів на загальну вагу рівну Q. Які
товари повинен закупити мандрівник, щоб їх сумарна вартість (при сумарній вазі товарів <= Q) була максимальна?
Вхідний файл: input.txt
Вихідний файл: output.txt
Вхідні дані: В першому рядку записане число, що вказує яку вагу товарів можна навантажити на корабель, в другому -
кількість предметів, в наступних рядках записані два числа через пропуск, що вказують відповідно вагу і ціну кожного
товару.
Вихідні дані: Вихідний файл повинен містити в першому рядку загальну суму витрачену на закупівлю товарів, в другому -
порядкові номери товарів, записані через пропуск, які закупив мандрівник.
Приклад:
input.txt
100
5
20 40
40 60
50 100
20 30
10 20
output.txt
190
1 3 4 5
|