Олимпиадная задача - Кризисный бизнес Опции

[Cheburashka]

Сегодня побывал на школьной олимпиаде г.Сургута, на ней мне встретилась интересная (даже может она и проста, но всё-таки). Условие напишу кратко (уж больно оно большое):
Есть N автомобилей, стоимость i-го автомобиля равняется a_i. Нужно найти максимальное количество автомобилей, потратив сумму не более S.
Хотелось бы услышать просто ход решения

[Unconnected]

Упорядочить цены по возрастанию, а потом идти по массиву и увеличивать переменную-счетчик машин, пока общая цена не превысит лимит..

[Cheburashka]

Хмм)) Un, это пол проблемы
Вот к пример из задачи:
n=6 s=18
5 10 1 2 1 20.

Упорядочив массив получим последовательность (1, 1, 2, 5, 10, 20), при этом складывая получим...............
Так-так. Походу дела, что запутался на олимпиаде... Теперь я понимаю. Делал в принципе также, но почему-то у меня не уходила мысль о том, что можно купить больше не смотря на сам порядок.
Просто невнимательность
Но всё равно спасибо

[TarasBer]

> Нужно найти максимальное количество автомобилей, потратив сумму не более S.

Ответ N.
Или за поиск тоже платить надо?

[Cheburashka]

TarasBer, почему именно N?))) мы ведь не можем купить все автомобил,и если у нас сумма денег меньше чем стоят автобили.

[TarasBer]

Зато мы можем найти все автомобили. В условии же сказано, что их надо только найти, а не купить.

[Unconnected]

Ну он в ускоренном личном варианте пересказывал, смысл понятен.. Самое обидное, когда так написано именно в задании, но ответ N точно не примут))

[sheka]

TarasBer, Поржал