Интересные интересности и задачи/головоломки

[Poma][a]

а поконкретнее. что не так?

Решение неправильное. Что не понятно?

ну или что-то типа этого

1 2 100500
Спорим 49 составить нельзя и это меньше, чем 1+2+100500?

[Sibedir]

(1 + 2) + 1 < 1000500
=>
x = (1+2) + 1 = 4

как же это ты меня не понял? я же в #1340 так все понятно объяснил.

[Poma][a]

Пардон. Верно

[Вадим Мошев]

Позвольте задачу задать.

Пусть у нас есть массив из 5 строк. Каждая строка представляет собой разделённые пробелами коэффициенты многочленов, а сам массив выглядит следующим образом:
s[1] = 1 2
s[2] = 3 2 1 4
a[3] = 2 3 1 0
s[4] = 7 6 5 4 4 1
s[5] = 256 1

Задача состоит в том, чтобы найти количество элементов массива, которые содержат коэффициенты многочлена, не имеющего ни одного действительного корня.

Важно: степени одночленов возрастают слева направо, например, если у нас есть строка "22 33 14", то это будет означать, что нам дан многочлен 22 + 33x + 14x^2

[Аватар]

Sibedir

Похоже на правду. А как насчет доказательства #1340?

Вадим Мошев

По многочленам нечетных степеней вопросов нет, а определить наличие действительных корней у многочлена четной степени далеко не тривиальная задача. Ну если только он не квадратный. По конкретному примеру решить одно кв.уравнение

[Poma][a]

А как насчет доказательства #1340?

Про это верно и написал
Сортируем массив, идем и суммируем его. Как только сумма на подотрезке (1..k) стала меньше, более чем на 1, чем (k+1)ый элемент, то ответом является эта сумма +1

[Аватар]

Poma][a

Я понял, но это утверждение. Вот и спрашиваю - а как насчет доказательства его истинности?

[Poma][a]

Вот и спрашиваю - а как насчет доказательства его истинности?

А какое доказательство Вы хотите?
Мы говорим, пусть мы рассмотрели все элементы массива от 1 до k. Добавим туда еще один элемент (k+1)'ый. И мы могли получить сумму чисел от 1 до sum(a[1..k]). Теперь смотрим на a[k+1]. Если он равен sum, то нас это не волнует. Если он больше на 1, то тоже все хорошо. А если он больше на 2 (и более), то это наш случай. Число sum(a[1..k])+1 мы получить не можем, ибо все числа натуральные, отсортированные по возрастанию. Значит, рассмотрев первые k чисел, мы не смогли получить sum(a[1..k])+1. Единственный вариант получить это число - прибавить некое число из a[1..k] к a[k+1], но числа-то натуральные. Значится прибавив, мы получим число, большее sum(a[1..k])+1

[Аватар]

Число sum(a[1..k])+1 мы получить не можем, ибо все числа натуральные, отсортированные по возрастанию.

Да, получили число, которое нельзя представить частичной суммой элементов нашего массива. Почему оно минимально? Или, что то же самое, где доказано, что sum(a[1..k])-1, например, можно представить частичной суммой?

[Poma][a]

Или, что то же самое, где доказано, что sum(a[1..k])-1, например, можно представить частичной суммой?

В самом рассуждении и доказано.
Начнем с того, что 1 должна быть в сумме обязательно. Если такой не имеется - ответ 1.
Значит мы исключаем из суммы 1-ку и радуемся