Описание задачи
Монотонная подпоследовательность представляет собой последовательность чисел , [a1, a2, ..., an]
таких , что
a1 <= a2 <= ... <= an
или a1 >= a2 >= ... >= an
. [1, 3, 3, 7, 9, 13, 13, 100]
является монотонной (неубывающей) подпоследовательностью, а также [9, 4, 4, 3, 0, -10, -12]
(эта не возрастает), но [1, 3, 6, 9, 8]
не является. Если задан список целых чисел (в любом приемлемом формате), выведите наименьшее число N
, чтобы последовательность этих целых чисел можно было разбить на N
монотонные последовательности.
Примеры
[1, 3, 7, 5, 4, 2] -> [[1, 3, 7], [5, 4, 2]] -> 2
[1, 2, 3, 4, 5, 6] -> [1, 2, 3, 4, 5, 6] -> 1
[3, 1, 5, 5, 6] -> [[3, 1], [5, 5, 6]] -> 2
[4, 6, 8, 9, 1, 6] -> [[4, 6, 8, 9], [1, 6]] -> 2
[3, 3, 3, 3] -> [[3, 3, 3, 3]] -> 1
[7] -> [[7]] -> 1
[] -> [] -> anything (you don't actually have to handle an empty list case)
[1, 3, 2, -1, 6, 9, 10, 2, 1, -12] -> [[1, 3], [2, -1], [6, 9, 10], [2, 1, -12]] -> 4
[4,4,8,8,1,4,5] -> 2
0 / undefined
, что это звучит так, как будто это должно быть либо 0, либо представлениеundefined
на нашем языке, но из вашего комментария к ответу Джонатана Аллана на желе это выглядит какundefined
средствоanything
... Какой из них это? ? Во втором случае я бы предложил писатьanything
вместоundefined
Ответы:
Брахилог , 12 байт
Попробуйте онлайн!
Это возвращается
false.
для пустого списка[]
.объяснение
Это вернет наименьший, потому что
~c
будет генерировать точки выбора от наименьшего количества подсписков до самого большого.источник
Z
потому чтоZ
это имя переменной; поэтому мы говорим «вызовите эту программу с выводом в качестве переменной». Вы можете изменитьZ
в любой другой прописной буквы ; это просто имя переменной. Причина, по которой этот аргумент существует, состоит в том, чтобы позволить возможность на самом деле установить вывод для чего-то, а не для переменной.4
в этом примере, он скажет вам, если это правильно или нет )3
потому что не найдет ни одного списка подсписков, где все являются монотонными и имеют длину3
. Это займет много времени, потому что он попробует все возможные списки подсписков, даже те, которые на самом деле длиннее, чем 3 элемента, потому что длина проверяется после нахождения списка. Ибо5
он говорит,true
потому что действительно есть хотя бы один список длины5
с монотонными подсписками, который работает. Таким образом, эта программа возвращает наименьшую длину, когда выходные данные являются переменными и существует ли какой-либо список этой длины, который работает, если выходные данные являются целыми числами.Perl, 65 байт
62 байта кода + 3 байта для
-n
флага.monot_seq.pl:
Введите ввод без окончательного перевода строки с числами, разделенными пробелами:
-5 байтов благодаря @ Габриэлю Бенами.
источник
($&<=>$1)*($1<=>$2)||$1==$2
в($&<=>$1)*($1<=>$2)>=0
Mathematica, 111 байт
Именованная функция,
f
принимающая непустой список чисел (целые или даже вещественные числа). Работает спереди назад, многократно отбрасывая первый элемент и отслеживая, сколько подпоследовательностей необходимо. Более подробный:источник
d=#2-#&@@#&;
Кроме того, определениеf
илиg
как унарный оператор±
, вероятно, сэкономит несколько байтов.Желе , 19 байт
TryItOnline! или запустить все тесты (пустой список приводит к
1
)Как?
(Я не уверен, что это самый подходящий метод, чтобы минимизировать количество байтов, хотя)
источник
1
(что я на самом деле думаю, имеет больше смысла, чем0
).undefined
значит - результат не имеет значения.Perl
98979679 байтВвод предоставляется в виде списка чисел, разделенных пробелами, предоставляемых во время выполнения, например
(4 - это выход)
Удобочитаемый:
«Оператор космического корабля»
<=>
возвращает -1, если LHS <RHS, 0, если LHS = RHS, и +1, если LHS> RHS. При сравнении трех последовательных элементов ,$a,$b,$c
чтобы определить , если они монотонные, необходимо только определить , что это не тот случай , что именно один из$a<=>$b
,$b<=>$c
является 1 , а другим -1 - что происходит только тогда , когда их продукт -1. Если либо$a==$b
или$b==$c
, то последовательность является монотонной, и произведение равно 0. Если$a < $b < $c
, тогда оба результата приводят к -1, и -1 * -1 = 1. Если$a > $b > $c
, то оба они приводят к 1, а 1 * 1 = 1. В любом случае последовательность является монотонной, и мы хотим продолжить.Если произведение меньше 0, мы знаем, что последовательность не является монотонной, и мы отбрасываем значения, которые
$a,$b
мы в данный момент храним, и увеличиваем счетчик подпоследовательностей. В противном случае мы продвигаемся на один номер вперед.Ничего не возвращает, если вход пустой, иначе возвращает наименьшее количество смежных монотонных подпоследовательностей
источник
1
иif
(или, может быть, вы делаете на старых Perl, но на последних вы не делаете). Также вы можете (возможно) заменитьshift
наpop
. Тем не менее, есть некоторые тестовые случаи, в которых ваш код не работает:6 3 6 3
(вы печатаете 3 вместо 2),4 3 2 1
(вы печатаете 2 вместо 1). Использованиеpop
вместоshift
решения тех, но создать новые (1 2 3 4
печатает 3 вместо 1) ...C # 6,
297209 байтРазгромленный с объяснениями
источник
JavaScript (ES6), 69 байт
Принимает ввод как несколько параметров. Работает путем рекурсивного сравнения первых трех элементов, чтобы увидеть, являются ли они монотонными, если это так, удаляет средний элемент, так как он бесполезен, если нет, удаляет первые два элемента и запускает новую последовательность.
источник
Clojure, 97 байт
reduce
отслеживает текущую подпоследовательность и вычисляет, сколько раз<=
и>=
условия не выполняются. Последний1
берет 2-й элемент из результата (являющийся счетчикомi
).источник