Форум » Обработка числовых последовательностей » 5028(PRO100 ЕГЭ) » Ответить
5028(PRO100 ЕГЭ)
L4vanda: Рассмотрим мою проблему на примере файла А. В этом файле К = 9, то есть надо найти подпоследовательность, в которой 9 различных элементов(элементы лежат в диапазоне от 1 до К). Если подпоследовательность состоит из К различных элементов, то и длина этой подпоследовательности будет равна К, потому что если в подпоследовательности будет больше К элементов, то в этой подпоследовательнсти будут находится одинаковые числа и тогда нельзя сказать, что элементы этой подпоследовательнсти различны. Но, руководствуясь этой логикой, я получил неправильный ответ. Помогите найти ошибку в моих рассуждениях пожалуйста.
Ответов - 7
PRO100 ЕГЭ: Добрый день! Фраза из условия "последовательности, в которых содержатся K различных чисел" говорит о том, что в подпоследовательности имеются все числа от 1 до к, числа могут повторяться. Например, если к=3, то в последовательности 1 2 1 1 3 1 1 1 2 1 самая короткая подходящая последовательность 2 1 1 3. В ответ идёт длина этой подпоследовательности - 4
L4vanda: Всё понял. Большое спасибо
Елена_10: Здравствуйте! А почему вы решили, что числа в подпоследовательности могут повторяться? В задании сказано: Рассматриваются все непрерывные подпоследовательности исходной последовательности, в которых содержатся K различных чисел. И в примере приведена подпоследовательность с различными числами 2, 1, 3, 4, 5. Почему тогда не 1 1 2 1 3 4 5??? Ответ для файла А 13, тогда какая там подпоследовательность была собрана?
Поляков: Елена_10 пишет: Почему тогда не 1 1 2 1 3 4 5??? Потому что мы ищем самую короткую последовательность.
Елена_10: Спасибо, но на мой взгляд, уж слишком замудрили с этой задачей Либо нужно корректировать условие и в маленьком примере показать, что в последовательности могут быть одинаковые числа... А если ищем самую короткую, то тогда ответ 1.
988013@mail.ru: файл входных данных: 20 1 3 4 9 5 9 2 8 9 1 7 7 8 6 2 * 3 * 1 * 3 * 3 * 8 получается непрерывающаяся последовательность 2+3+1+3+3=12 с минимальной суммой 12 ? подскажите в ответе точно нет ошибки ?
Поляков: 988013@mail.ru пишет: подскажите в ответе точно нет ошибки ? У вас неверные данные. В первой строке должно быть два числа - N и K. Вот данные файла А: [pre2]20 9 1 3 4 9 5 9 2 8 9 1 7 7 8 6 2 3 1 3 3 8[/pre2]Вот самая короткая последовательность длины 13, в которой есть все числа от 1 до 9: [pre2][3, 4, 9, 5, 9, 2, 8, 9, 1, 7, 7, 8, 6][/pre2]
полная версия страницы