- 22, Oct 2024
- #1
В этот вопрос Я просил вас определить, можно ли составить восходящий список. Это был код-гольф, поэтому, естественно, большинство ответов приходят очень медленно. Но что, если мы хотим, чтобы это было быстрый. В этом задании я прошу вас решить ту же задачу, но вашей целью будет минимизация асимптотической временной сложности.
Вот еще раз задача:
А запустить восходящий список — это список, длина серий последовательных одинаковых элементов которого строго увеличивается.
В этом задании вам будет предоставлен список \$n\$ положительных целых чисел, \$x_i\$, в качестве входных данных. Ваша задача — определить, можно ли составить восходящий список из чисел от \$1\$ до \$n\$, в котором каждое число \$k\$ будет встречаться. точно \$x_k\$ раз.
Правила
В качестве входных данных вам следует взять непустой список целых положительных чисел. Вы должны вывести одно из двух различных значений. Один, если можно создать восходящий список, другой, если нельзя.
Ваши ответы будут оцениваться по их асимптотической временной сложности в худшем случае относительно размер входа.
Размер входного списка \$x_i\$ будет считаться \$\sum_{n=0}^i 8+\lfloor\log_2(x_i)\rfloor\$ бит. Хотя для удобства вам разрешено использовать форматы, которые не имеют такого точного использования памяти.
Алгоритм перебора имеет сложность \$O(2^n!)\$.
Тай-брейк будет .
Тестовые случаи
Входные данные, которые не могут составить список по возрастанию
[1], [1] [10], [1,1,1,1,1,1,1,1,1,1] [6,7], [1,1,1,1,1,1,2,2,2,2,2,2,2] [7,6], [2,2,2,2,2,2,1,1,1,1,1,1,1] [4,4,2], [1,3,3,1,1,1,2,2,2,2] [4,4,7], [1,3,3,1,1,1,2,2,2,2,3,3,3,3,3] [4,4,8], [1,3,3,1,1,1,2,2,2,2,3,3,3,3,3,3]
Входные данные, которые могут сделать восходящий список потенциальных решений, даются после , for clarity but is not necessary for you to compute.
[2,2]
[40,40]
[40,40,1]
[4,4,3]
[3,3,20]
[3,3,3,3]
#код-гольф #задача принятия решения #комбинаторика #самый быстрый алгоритм
![[Евгений Гилаев] 1С:Программист — Быстрый старт в профессию](/assets/images/icons/forum4.png){kind=icon}
