Заказы Tim1 | портал Профессор

Заказы Tim1

Науки

Экономические науки

Технические науки

Естественные науки

Математические науки

Программирование

Гуманитарные науки

Юридические науки

Иностранные языки

Работа с текстом

Дисциплины

Типы работ

Курсовая

Дипломная работа

Контрольная

Реферат

Статья

Решение задач

Отчет по практике

Шпаргалки

Чертеж

Рецензия

Лабораторная

Ответы на вопросы

Презентация

Перевод

Диплом МБА

Доклад

Диссертация

Бизнес-план

On-line тест

Другое

Статус заказа

В аукционе

Черновик

В работе

На гарантии

В корректировке

В арбитраже

Отменен

Завершен

Найти заказы

1 работа

Стоимость

Дата добавления

Срок сдачи

Решение задач

Написать программу на Pascal либо на C++

2 июля 2018 в 11:42

Pascal

до 0

5 июля

Описание работы

В аукционе

Ставок еще нет

Описание работы

Tim1

Обратные задачи часто встречаются в исследованиях по теоретической информатике. Обычно обратная задача формулируется так: по заданному решению требуется построить набор входных данных, на котором это решение достигается. В этой задаче вам требуется решить обратную задачу о наибольшей возрастающей подпоследовательности. Напомним, что возрастающей подпоследовательностью последовательности a[1..n] длины n называют последовательность a[i1] < a[i2] < ...< a[ik], где 1 ? i1 < i2 < ... < ik ? n. Задача о наибольшей возрастающей подпоследовательности (НВП) заключается в том, чтобы найти возрастающую подпоследовательность заданной последовательности, имеющую максимальное число элементов. При решение задачи о НВП, строится массив d[1..n], где d[i] — длина наибольшей возрастающей последовательности последовательности a[1..i], заканчивающейся на a[i]. Например, для последовательности a = [3, 2, 4, 1, 5, 6] построенный массив d имеет вид d = [1, 1, 2, 1, 3, 4]. Требуется по заданному массиву d найти такую последовательность a, такую что при решении задачи о НВП построенный массив d совпадает с заданным. Все числа в последовательности a должны быть различными целыми положительными и не превосходить 10^15. Формат входных данных: Первая строка содержит целое положительное число t — число тестовых примеров во входных данных. Далее следуют описания тестовых примеров. Каждый тестовый пример описывается двумя строками. Первая строка содержит целое положительное число n — длину последовательности (1 ? n ? 300 000). Вторая строка содержит n целых положительных чисел — массив d. Гарантируется, что сумма значений n по всем тестовым примерам не превышает 300 000. Формат выходных данных: Для каждого тестового примера выведите n различных целых положительных чисел, не превосходящих 1015 — искомую последовательность a. Гарантируется, что входные данные таковы, что искомая последовательность существует. Если возможных решений несколько, можно вывести любое. Примеры: Входные данные 2 5 1 2 2 1 3 8 1 2 3 1 4 2 3 5 Выходные данные 2 5 3 1 4 4 6 8 1 9 2 7 10

Свернуть