Условие
(Московская олимпиада по программированию) Дан неубывающий
массив положительных целых чисел
a[
1]
≤a[
2]
≤...
≤a[
n]. Найти наименьшее
целое положительное число, не представимое в виде суммы
нескольких элементов этого массива (каждый элемент массива
может быть использован не более одного раза). Число
действий порядка
n.
Решение
Пусть известно, что числа, представимые в виде
суммы элементов
a[
1],...,
a[
k], заполняют
отрезок от
1 до некоторого
N. Если
a[
k+
1] >
N+
1, то
N+
1 и будет минимальным числом, не
представимым в виде суммы элементов массива
a[
1]...
a[
n]. Если же
a[
k+
1]
≤N+
1,
то числа, представимые в виде суммы элементов
a[
1]...
a[
k+
1], заполняют отрезок от
1 до
N+a[k+1].
k := 0; N := 0;
{инвариант: числа, представимые в виде суммы элементов
массива a[1]..a[k], заполняют отрезок 1..N}
while (k <> n) and (a[k+1] <= N+1) do begin
| N := N + a[k+1];
| k := k + 1;
end;
{(k = n) или (a[k+1] > N+1); в обоих случаях ответ N+1}
writeln (N+1);
(Снова тот же дефект: в условии цикла при ложном первом
условии второе не определено.)
Источники и прецеденты использования
|
|
|
книга |
|
Автор |
А.Шень |
|
Название |
Программирование: теоремы и задачи |
|
Издательство |
МЦНМО |
|
Издание |
второе |
|
Год издания |
2004 |
|
глава |
|
Номер |
1 |
|
Название |
Переменные, выражения, присваивания |
|
параграф |
|
Номер |
2 |
|
Название |
Массивы |
|
задача |
|
Номер |
1.2.29 |
