Question

Сергей собирает многоступенчатые ракеты. Для большей точности измерений параметров полета на каждой ступени ракеты он написал её мощность. Но он совершенно забыл, что мощности ступеней любой ракеты должны строго возрастать. К примеру, мощности ступеней ракеты могут принимать значения 1 4 7, а 3 2 4 — не могут. Собирать новую ракету Серёжа не хочет, однако он может вытащить некоторые ступени, не меняя порядка оставшихся. К примеру, из ракеты с мощностями ступеней 1 8 3 4 можно получить ракету 1 3 4 (вытащив ступень с мощностью 8), а ракеты 1 4 3 (порядок ступеней с мощностями 4 и 3 был изменен) и 1 8 3 (мощности ступеней не возрастают) получить нельзя. Помогите Сергею вытащить минимальное количество ступеней так, чтобы мощность остальных ступеней строго возрастала. У Сергея есть четыре ракеты. В таблице ниже для каждой ракеты приведена последовательность мощностей её ступеней. Номер ракеты Последовательность мощностей 1 5 3 4 2 3 2 1 6 3 2 5 8 3 4 6 7 5 6 7 1 2 8 4 2 5 3 5 3 4 7 3 8 4 9 6 7 Ответом на данную задачу являются четыре последовательности целых чисел: каждая из них — это последовательность мощностей оставшихся ступеней соответствующей ракеты. Каждую последовательность записывайте в соответствующей ей строке. Числа в последовательности должны быть разделены пробелом. Каждая последовательность должна строго возрастать, а также иметь как можно большую длину. Если существует несколько вариантов ответа, можно вывести любой из них. Если вы не можете дать ответ для какой-то из ракет, запишите в качестве ответа для данной ракеты число 0. Примечание. Рассмотрим пример. Допустим, у какой-то ракеты последовательность ступеней равна 1 4 5 2 3. Для этой ракеты возможно два варианта ответа. Последовательность чисел в ответе может быть такой: 1 2 3. Или последовательность чисел может быть такой: 1 4 5. В ответе нужно указать одну, любую из этих последовательностей.

Answer 1

Ответ:

Объяснение:

145

Answer 2

Ответ:

2345

1258

4678

235689

Объяснение:

Answer 3

Чтобы помочь Сергею, мы должны вытащить минимальное количество ступеней из каждой ракеты так, чтобы мощность оставшихся ступеней строго возрастала.

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

Применим этот метод к предоставленным ракетам:

1. Ракета 1: 5 3 4 2 3 2 1 6 3 2 5 8 3 4 6 7 5 6 7 1 2 8 4 2 5 3 5 3 4 7 3 8 4 9 6 7

Возможные варианты ответов: - 1 2 3 4 5 6 7 8 - 1 2 3 4 5 6 7 8 9

2. Ракета 2: 1 4 5 2 3

Возможные варианты ответов: - 1 2 3 4 5 - 1 2 3 4 5

3. Ракета 3: 3 5 3 4 7 3 8 4 9

Возможные варианты ответов: - 3 4 5 7 8 9 - 3 4 5 7 8 9

4. Ракета 4: 6 7

Возможные варианты ответов: - 6 7

Таким образом, ответом на задачу являются следующие последовательности мощностей:

1. 1 2 3 4 5 6 7 8 9 2. 1 2 3 4 5 3. 3 4 5 7 8 9 4. 6 7