Дистанционная подготовка: Задача на нахождение наименьшего числа, которое нельзя представить суммой других чисел из данной последовательности.
Задача на нахождение наименьшего числа, которое нельзя представить суммой других чисел из данной последовательности.
от Глеб Шевчук - Понедельник 5 Декабрь 2016, 17:16
653. Несоставляемое число
  Хочу знать идею решения данной задачи, у меня есть программа, однако она не проходит тесты. Размышлял я таким образом: 1) прогоняем массив циклом for и на каждом шаге смотрим на сумму элементов, если a[i+1]>sum+1 тогда выводит sum+1 и заканчиваем программу через Halt.
Таким образом вы проверили массив на наличие искомого числа внутри массива;
2) если данного числа внутри массива нет, но наибольшее число, которое можно составить из данных чисел - есть сумма элементов массива, а так же все предыдущие числа так же можно составить, ведь массив уже прошел проверку внутри. Таким образом ответ будет sum+1;
3) ну и в самом начале стоит указать, что, если a[1]!=1, тогда наименьшим таким числом и будет единица;
Помогите пожалуйста!
Re: Задача на нахождение наименьшего числа, которое нельзя представить суммой других чисел из данной последовательности.
от Михаил Хозин - Вторник 6 Июнь 2017, 17:29
  Может быть кому-то поможет.

Посмотрите переполнение int.