| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Интересные и занимательные задачи по программированию > ЗАДАЧА №1 (CONTACT) |
| Автор: Fedor 11.3.2005, 18:23 |
| Вот предлагаю задачи, которые были на студенческой олимпиаде днепропетровского национального университета 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, 22:51 |
| Ну так че там? Никому не интересно? Вы хотябы реагируйте как-нибудь... |
| Автор: Secandr 11.3.2005, 23:03 | ||
Страно получается Честно говоря в школе были задачки попроще Я кроме простейшего перебора предложить ничего не могу  |
| Автор: Fixin 11.3.2005, 23:32 |
| Счас посмотрим... |
| Автор: Fixin 11.3.2005, 23:45 |
| Перебором? 2 метра? разве что на асме... за минуту. Хотя, кто его знает 12 символов. Может составить список возможных вариантов и посчитать? Памяти много, но может по быстрее будет считать. Скорее список надо динамический, на что и намекивают. Хорошая задачка. Завтра решу. А срочно надо, или просто интересно? |
| Автор: Fedor 11.3.2005, 23:51 | ||||
Да я то решил. Вернее, на олимпиаде нарешал на 8 баллов из 20. Сейчас вроде поправил, должно лучше работать. Это вам пищу для ума подбрасываю Памяти использовать можно не больше 10 МБ. Secandr точно не перебор.
когда я учавствовал во всеукраинской олимпиаде по информатике, были и посложнее З.Ы. Вот я ж скромный |
| Автор: De Gray 12.3.2005, 12:42 |
| Вообще идея вроде простая. Разобъем все на слова длинной A(например, если А == 2), то словами будут 00,01,10,11.Очевидно(т.е. насколько я себе представляю), что любое слово длинны A+1, не может встреяться чаще, чем составляющие его (сейчас покажу как) слова длинны А. т.е Если встретилось слово 0100, то встерится слово 010 и 100(сдвинутое, относительно первого на . Поэтому, алгоритм такой --Ищем слова длинны А(их powl(2,A)); --Вычисляем возможные комбинации в словах A+1 --Ищем слова А+1 Как только набрали N слов с ненулевыми частотами, завершаем. Требуется вроде k = log_2_(N/A) проходов по файлу |
| Автор: Fedor 12.3.2005, 13:52 | ||||
 По-моему, вы немного не поняли задание
Это не много не то ИМХО. Смотрим условие:
 Вот. Хотя я может не так тебя понял |
| Автор: Sardar 12.3.2005, 14:04 |
| Можно построить префиксное дерево по всем суффиксам строки, но похоже найдём мы самые длиные подстроки. Надо проверить... Fedor ты задачу за 20 минут решил? |
| Автор: Fedor 12.3.2005, 14:17 | ||
ну как... Идею я придумал за 15 минут плюс еще 20 я ее набивал. А потом я 2 часа не мог отладить QSort так как забыл его начисто.  Весь прошлый год подобными задачами не занимался.  Добавлено @ 14:18 И в итоге не успел ее оттестировать нормально, вследсвие чего получил мало балов. |
| Автор: De Gray 12.3.2005, 14:37 | ||
Как только набрали N слов с ненулевыми частотами, завершаем. Я только хотел сказать, что это и будет максимально часто встречающиеся слова. |
| Автор: Fedor 13.3.2005, 08:27 | ||
Но их же может быть не N  Вот хотя бы на примере... |
| Автор: De Gray 13.3.2005, 10:25 | ||
Остальные искать смысла нет. |
| Автор: Fedor 13.3.2005, 10:40 |
| De Gray В примере в условии при N = 10 в ответе 19 самых частых последовательностей. Просто например последователности 01 и 10 встречаются одинаковое количество раз. |
| Автор: maxim1000 14.3.2005, 12:40 | ||
| можно попробовать так: 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. идем по последовательности:
6. выбираем из массива 20 наиболее частых последовательностей (сортировать я бы не стал, 20 самых частых можно просто выбрать) Добавлено @ 12:42 памяти было использовано меньше 16K если нужно для нескольких размеров - просто параллельно пускаем несколько подобных операций, памяти получится не больше 12*16K=192K (очень грубая оценка) |