Вот предлагаю задачи, которые были на студенческой олимпиаде днепропетровского национального университета

oi.dp.ua

Задача CONTACT

Радиосигналы, принимаемые астрономами из космоса, порой очень похожи на послания внеземного разума. Распознание "разумных" сообщений чрезвычайно важно для установления Контакта.
Сообщение - это последовательность нулей и единиц. Признак разумности сообщения - количество повторяющихся фрагментов в сообщении. Для анализа сообщений требуется составить программму CONTACT, которая отбирает в заданном сообщении N наиболее часто встречающихся фрагментов среди всех тех, которые имеют которые имеют длину от A до B включительно. Фрагменты могут перекрываться. Учитываются только те фрагменты, которые встречаются в сообщении хотя бы один раз.
Входные данные вводятся их текстового файла CONTACT.IN и имеют следующий вид: в первой строке назходится число A, во второй строке число B, в третьей строке - целое число N, в четвертой строке - последовательность нулей и единиц, заканчивающаяся цифрой 2. (0<A<=B<=12, 0<N<=20). Размер файла может достигать 2 МБайт.
В выходной файл CONTACT.OUT программа выводит N строк, которые соответствую N наиболее часто встречающимся частотам. Каждая строка имеет такой вид: ЧАСТОТА ФРАГМЕНТ ФРАГМЕНТ ..... ФРАГМЕНТ. Строки упорядочены по убыванию частот. Внутри строки фрагменты упорядочены по убыванию длин фрагментов, при этом фрагменты равной длины идущие подряд упорядочены по убыванию их числовых значений. В том случае, если количество различных фрагментов меньше N, в выходном файле будет меньше N строк.

ПРИМЕРЫ ВХОДНЫХ И ВЫХОДНЫХ ДАННЫХ:

CONTACT.IN
2
4
10
010100100100010001111011000010100110011110000100100111100100000002

CONTACT.OUT
23 00
15 10 01
12 100
11 001 000 11
10 010
8 0100
7 1001 0010
6 0000 111
5 1000 110 011
4 1100 0011 0001

Ну так че там? Никому не интересно? Вы хотябы реагируйте как-нибудь...

Цитата(Fedor @ 11.3.2005, 19:23)

Учитываются только те фрагменты, которые встречаются в сообщении хотя бы один раз.

Страно получается

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

Счас посмотрим...

Перебором? 2 метра? разве что на асме... за минуту. Хотя, кто его знает 12 символов. Может составить список возможных вариантов и посчитать? Памяти много, но может по быстрее будет считать. Скорее список надо динамический, на что и намекивают. Хорошая задачка. Завтра решу. А срочно надо, или просто интересно?

Цитата(Fixin @ 11.3.2005, 22:45)

А срочно надо, или просто интересно?

Да я то решил. Вернее, на олимпиаде нарешал на 8 баллов из 20. Сейчас вроде поправил, должно лучше работать. Это вам пищу для ума подбрасываю
Памяти использовать можно не больше 10 МБ.

Secandr точно не перебор.

Цитата(Secandr @ 11.3.2005, 22:03)

Честно говоря в школе были задачки попроще

когда я учавствовал во всеукраинской олимпиаде по информатике, были и посложнее

З.Ы. Вот я ж скромный

Вообще идея вроде простая.
Разобъем все на слова длинной A(например, если А == 2), то словами будут 00,01,10,11.Очевидно(т.е. насколько я себе представляю), что любое слово длинны A+1, не может встреяться чаще, чем составляющие его (сейчас покажу как) слова длинны А. т.е Если встретилось слово
0100, то встерится слово 010 и 100(сдвинутое, относительно первого на .
Поэтому, алгоритм такой
--Ищем слова длинны А(их powl(2,A));
--Вычисляем возможные комбинации в словах A+1
--Ищем слова А+1
Как только набрали N слов с ненулевыми частотами, завершаем.
Требуется вроде k = log_2_(N/A) проходов по файлу

По-моему, вы немного не поняли задание

Цитата(De @ 12.3.2005, 11:42)

Как только набрали N слов с ненулевыми частотами, завершаем.

Это не много не то ИМХО. Смотрим условие:

Цитата(Fedor @ 11.3.2005, 17:23)

требуется составить программму CONTACT, которая отбирает в заданном сообщении N наиболее часто встречающихся фрагментов среди всех тех, которые имеют которые имеют длину от A до B включительно.

Вот. Хотя я может не так тебя понял

Можно построить префиксное дерево по всем суффиксам строки, но похоже найдём мы самые длиные подстроки. Надо проверить...

Fedor ты задачу за 20 минут решил?

Цитата(Sardar @ 12.3.2005, 13:04)

Fedor ты задачу за 20 минут решил?

ну как... Идею я придумал за 15 минут плюс еще 20 я ее набивал. А потом я 2 часа не мог отладить QSort так как забыл его начисто. Весь прошлый год подобными задачами не занимался.
Добавлено @ 14:18
И в итоге не успел ее оттестировать нормально, вследсвие чего получил мало балов.

Цитата(Fedor @ 12.3.2005, 13:52)

Вот. Хотя я может не так тебя понял

Как только набрали N слов с ненулевыми частотами, завершаем.
Я только хотел сказать, что это и будет максимально часто встречающиеся слова.

Это сообщение отредактировал(а) De Gray - 12.3.2005, 14:37

Цитата(De @ 12.3.2005, 13:37)

Как только набрали N слов с ненулевыми частотами, завершаем. Я только хотел сказать, что это и будет максимально часто встречающиеся слова.

Но их же может быть не N
Вот хотя бы на примере...

Цитата(Fedor @ 13.3.2005, 08:27)

Но их же может быть не N

Остальные искать смысла нет.

De Gray В примере в условии при N = 10 в ответе 19 самых частых последовательностей. Просто например последователности 01 и 10 встречаются одинаковое количество раз.

можно попробовать так:
1. пока сузим задачу: будем искать только фрагменты длины A (от 1 до 12)
2. последовательность - поток битов, если взять A последних битов последовательности, получим число от 0 до 2^A
3. создаем массив из целых чисел размером 2^A, array[i] - количество повторений фрагмента i, i - от 0 до 2^A, массив будет занимать sizeof(in)*2^A<16K
4. инициализируем нулями
5. идем по последовательности:

Код

y<<=1; y&=(2^A-1); y+=x[n++]; array[y]++;

6. выбираем из массива 20 наиболее частых последовательностей (сортировать я бы не стал, 20 самых частых можно просто выбрать)
Добавлено @ 12:42
памяти было использовано меньше 16K
если нужно для нескольких размеров - просто параллельно пускаем несколько подобных операций, памяти получится не больше 12*16K=192K (очень грубая оценка)