http://acm.pku.edu.cn/JudgeOnline/problem?id=1174 Обязательная задача на лето для троих :)
Друзья мои, вы должны обязательно за лето решить эту задачку (ну, это я так говорю за лето, а на самом деле - чем быстрее, тем лучше). И не говорите, что вы не читали это сообщение, я все равно не поверю! Даже вижу сейчас ваши три недовольных лица! :) Если вы не поняли о ком речь, перечислю поименно (Д.А. Н.В. И.Д.)Так вот, это важнейшая и интереснейшая задачка в методическом плане, в ней красиво сплетаются воедино несколько серьезных тем: "Указатели" (Н.В. снова отдыхал когда мы разбирали эту тему, поэтому должен разобрать ее самостоятельно по учебнику Окулова стр.346 ), "Системы счисления", "Обработка строк", "Сортировку"(Quicksort) . Сейчас я составляю кучу тестов к этой задаче (через три дня тесты будут) надеюсь, что вы не хотите получать двоечку в 11 классе. С уважением. Ваша добрейшая учительница.Контакт Доктор Астро Ински (Astro Insky) работает в радиотелескопическом центре. Недавно она заметила очень странное пульсирующее микроволновое излучение, исходящее непосредственно из центра галактики. Посланы ли эти сигналы какой-нибудь внеземной формой разумной жизни? Или это простое сердцебиение звезд?
Вы должны помочь доктору Ински отыскать истину, создав инструмент для анализа битовых последовательностей в записанных ею сообщениях. Доктор Ински хочет найти битовые подпоследовательности длиной от А до В включительно, которые встречаются в записанной последовательности наиболее часто. Подпоследовательности могут перекрываться. Определяются N наибольших различных частот (т.е. количество вхождений). Учитываются подпоследовательности, которые встречаются хотя бы один раз.
Решение (моё) и тесты готовы. 1.07.2012 (Два человека сдали.)
Входные данные
Стандартный вход содержит данные в следующем формате:
В первой строке находится число А - минимальная длина подпоследовательности.
Во второй строке находится число В - максимальная длина подпоследовательности.
В третьей строке задано число N - количество различных частот вхождения.
В четвертой задано саму полученную последовательность, состоящую из символов 0 и 1, символ 2 - признак окончания сообщения.
Размер входных данных не превышает 2 Мбайта. Параметры A, B и N имеют такие ограничения:
0 < N <= 20
0 < A <= B <= 12.
Выходные данные
Вы должны вывести не более N строк, каждая из которых содержит одну из N наибольших частот вхождения и соответствующие ей подпоследовательности. Строки должны располагаться в порядке убывания частот вхождения и иметь следующий вид:
частота подпоследовательность подпоследовательность ... подпоследовательность.
Частота - это количество вхождений указанных далее подпоследовательностей. Подпоследовательности в каждой строке должны располагаться в порядке убывания длины. Подпоследовательности одинаковой длины должны располагаться в порядке убывания их числового значения. Если в последовательности встречается менее N различных частот, то выходные данные будут содержать менее N строк
Пример входных данных
2
4
10
010100100100010001111011000010100110011110000100100111100100000002
Пример выходных данных
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
Анализ условия и разбор идеи решения (Смотреть обязательно!)http://narod.ru/disk/54745331001.8d63d53807031ef0be9fcd12527aab00/Kontakt.rar.html
(Скачать !!!)
