Автор | Сообщение |
|
Отправлено: 02.04.22 07:59. Заголовок: 5028(PRO100 ЕГЭ)
Рассмотрим мою проблему на примере файла А. В этом файле К = 9, то есть надо найти подпоследовательность, в которой 9 различных элементов(элементы лежат в диапазоне от 1 до К). Если подпоследовательность состоит из К различных элементов, то и длина этой подпоследовательности будет равна К, потому что если в подпоследовательности будет больше К элементов, то в этой подпоследовательнсти будут находится одинаковые числа и тогда нельзя сказать, что элементы этой подпоследовательнсти различны. Но, руководствуясь этой логикой, я получил неправильный ответ. Помогите найти ошибку в моих рассуждениях пожалуйста.
|
|
|
Ответов - 7
[только новые]
|
|
|
Отправлено: 02.04.22 11:54. Заголовок: Добрый день! Фраза и..
Добрый день! Фраза из условия "последовательности, в которых содержатся K различных чисел" говорит о том, что в подпоследовательности имеются все числа от 1 до к, числа могут повторяться. Например, если к=3, то в последовательности 1 2 1 1 3 1 1 1 2 1 самая короткая подходящая последовательность 2 1 1 3. В ответ идёт длина этой подпоследовательности - 4
|
|
|
|
Отправлено: 02.04.22 12:01. Заголовок: Всё понял. Большое с..
Всё понял. Большое спасибо
|
|
|
|
Отправлено: 04.04.22 19:21. Заголовок: 5028(PRO100 ЕГЭ)
Здравствуйте! А почему вы решили, что числа в подпоследовательности могут повторяться? В задании сказано: Рассматриваются все непрерывные подпоследовательности исходной последовательности, в которых содержатся K различных чисел. И в примере приведена подпоследовательность с различными числами 2, 1, 3, 4, 5. Почему тогда не 1 1 2 1 3 4 5??? Ответ для файла А 13, тогда какая там подпоследовательность была собрана?
|
|
|
|
| Администратор
|
Сообщение: 3436
|
|
Отправлено: 04.04.22 19:28. Заголовок: Елена_10 пишет: Поч..
Елена_10 пишет: цитата: | Почему тогда не 1 1 2 1 3 4 5??? |
|
Потому что мы ищем самую короткую последовательность.
|
|
|
|
Отправлено: 07.04.22 11:18. Заголовок: 5028(PRO100 ЕГЭ)
Спасибо, но на мой взгляд, уж слишком замудрили с этой задачей Либо нужно корректировать условие и в маленьком примере показать, что в последовательности могут быть одинаковые числа... А если ищем самую короткую, то тогда ответ 1.
|
|
|
|
Отправлено: 11.04.22 21:21. Заголовок: файл входных данных:..
файл входных данных: 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 ? подскажите в ответе точно нет ошибки ?
|
|
|
|
| Администратор
|
Сообщение: 3451
|
|
Отправлено: 11.04.22 21:37. Заголовок: 988013@mail.ru пишет..
988013@mail.ru пишет: цитата: | подскажите в ответе точно нет ошибки ? |
|
У вас неверные данные. В первой строке должно быть два числа - N и K. Вот данные файла А: 20 9 1 3 4 9 5 9 2 8 9 1 7 7 8 6 2 3 1 3 3 8 Вот самая короткая последовательность длины 13, в которой есть все числа от 1 до 9: [3, 4, 9, 5, 9, 2, 8, 9, 1, 7, 7, 8, 6]
|
|
|
|