Почти программирование.

[nikvic]

Дан список А1....Аn целых неотрицательных чисел.
Требуется найти первый его элемент такой, что для каких-то k, m
A(k+m) не равен ни A(k)+A(m), ни A(k)+A(m)+1.
За линейное время - по числу членов.

[EtCetera]

Рассмотрите "правильный массив", в котором $A_{m}=A_{k}+A_{m-k}$ или $A_{m}=A_{k}+A_{m-k}+1$ (для некоторого $0<k<m$). Начните с $A_2$, может быть что-нибудь и вылупится.

[nikvic]

(Оффтоп)

Мне неизвестны другие авторы задачи и её решения, кроме ВПС

[EtCetera]

(Оффтоп)

nikvic в сообщении #658246 писал(а):

Мне неизвестны другие авторы задачи и её решения, кроме ВПС

Это Вы к чему? И что/кто такое/такой это/этот ВПС?

[nikvic]

(Оффтоп)

Ваш покорный слуга

[EtCetera]

(Оффтоп)

Т.е. это не ПР/Р (П), а ОЗ (П)?

Жаль, что нули могут быть. Они всю малину портят. А так, очевидно, что $0\le A_m-m A_1\le m-1$. Дальше надо думать.

[cepesh]

Тема перемещена из форума «Программирование» в форум «Олимпиадные задачи (CS)»
Причина переноса: не указана.