Сообщение Re: этюд или не этюд от 22.11.2016 23:27
Изменено 22.11.2016 23:30 _ilya_
Здравствуйте, мыщъх, Вы писали:
М>дано N целых чисел. пускай для определенности это будет массив A.
М>каждое число массива либо больше либо меньше суммы двух других чисел. то есть для любых X, Y и Z следующее условие ложно: A[X] == A[Y] + A[Z].
Задача по сортировке массива, но хитрого — каждое число в >1,3 раза больше предыдущего, а если условие нарушается то задача решена — массив не валидный. Типа 1 2 4 7 12 20 33 это норм. Для отсортированного 2N операций норм, но не отсортированный — сомнительно что такая линейная сложность сортировки возможна, а без сортировки не выйдет проверить условие, разве что побитовые операции но про такие не сказано в задаче.
М>дано N целых чисел. пускай для определенности это будет массив A.
М>каждое число массива либо больше либо меньше суммы двух других чисел. то есть для любых X, Y и Z следующее условие ложно: A[X] == A[Y] + A[Z].
Задача по сортировке массива, но хитрого — каждое число в >1,3 раза больше предыдущего, а если условие нарушается то задача решена — массив не валидный. Типа 1 2 4 7 12 20 33 это норм. Для отсортированного 2N операций норм, но не отсортированный — сомнительно что такая линейная сложность сортировки возможна, а без сортировки не выйдет проверить условие, разве что побитовые операции но про такие не сказано в задаче.
Здравствуйте, мыщъх, Вы писали:
М>дано N целых чисел. пускай для определенности это будет массив A.
М>каждое число массива либо больше либо меньше суммы двух других чисел. то есть для любых X, Y и Z следующее условие ложно: A[X] == A[Y] + A[Z].
Задача по сортировке массива, но хитрого — каждое число в >1,5 раза больше предыдущего, а если условие нарушается то задача решена — массив не валидный. Типа 1 2 4 7 12 20 33 это норм. Для отсортированного 2N операций норм, но не отсортированный — сомнительно что такая линейная сложность сортировки возможна, а без сортировки не выйдет проверить условие, разве что побитовые операции но про такие не сказано в задаче.
М>дано N целых чисел. пускай для определенности это будет массив A.
М>каждое число массива либо больше либо меньше суммы двух других чисел. то есть для любых X, Y и Z следующее условие ложно: A[X] == A[Y] + A[Z].
Задача по сортировке массива, но хитрого — каждое число в >1,5 раза больше предыдущего, а если условие нарушается то задача решена — массив не валидный. Типа 1 2 4 7 12 20 33 это норм. Для отсортированного 2N операций норм, но не отсортированный — сомнительно что такая линейная сложность сортировки возможна, а без сортировки не выйдет проверить условие, разве что побитовые операции но про такие не сказано в задаче.