Отправлено: 02.04.22 07:59. Заголовок: 5028(PRO100 ЕГЭ)

Рассмотрим мою проблему на примере файла А. В этом файле К = 9, то есть надо найти подпоследовательность, в которой 9 различных элементов(элементы лежат в диапазоне от 1 до К). Если подпоследовательность состоит из К различных элементов, то и длина этой подпоследовательности будет равна К, потому что если в подпоследовательности будет больше К элементов, то в этой подпоследовательнсти будут находится одинаковые числа и тогда нельзя сказать, что элементы этой подпоследовательнсти различны. Но, руководствуясь этой логикой, я получил неправильный ответ. Помогите найти ошибку в моих рассуждениях пожалуйста.

 Отправлено: 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, тогда какая там подпоследовательность была собрана?

 Отправлено: 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 ? подскажите в ответе точно нет ошибки ?

 Отправлено: 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]