10789. Простая частота

Строка содержит цифры (0-9) и символы латинского алфавита (A-Z, a-z). Необходимо вычислить частоту каждого символа (количество раз, которое он встречается) и вывести те символы, частоты которых являются простыми числами.

Вход. Первая строка содержит количество входных тестов T (0 < T < 201). Каждая из следующих T строк содержит цифры и буквы латинского алфавита. Длины строк не более 2001.

Выход. Для каждого теста вывести в отдельной строке его номер и символы, частота которых есть простое число. Символы выводить в лексикографическом порядке (по возрастанию их ASCII кодов). Если не существует ни одного символа, частота которого является простым числом, то вывести слово empty.

Пример входа

3

ABCC

AABBBBDDDDD

ABCDFFFF

Пример выхода

Case 1: C

Case 2: AD

Case 3: empty

РЕШЕНИЕ

простые числа + сортировка за линейное время

Анализ алгоритма

Сгенерируем массив primes длины MAX=2002, для которого primes[i] = 1 если i – простое число и primes[i] = 0 иначе. Используя его можно эффективно проверять числа от 0 до 2001 на простоту. Заведем массив freq, ячейки которого будут содержать частоту использования символов. Далее проверяем значения частот символов на простоту и выводим их в лексикографическом порядке.

Пример

Рассмотрим второй тест. Частота символа А равна 2, символа В – 4, символа D – 5. Поскольку простыми числами являются только 2 и 5, выводить следует лишь символы A и D в порядке возрастания их ASCII кодов.

Реализация алгоритма

Сгенерируем массив primes для тестирования чисел на простоту. Для дальнейшего использования будем полагать, что числа 0 и 1 являются сложными (primes[0] = primes[1] = 0).

void gen_primes(void)

{

int i, j;

for(i = 0; i < MAX; i++) primes[i] = 1;

primes[0] = primes[1] = 0;

for(i = 2; i <= (int)sqrt(1.0*MAX); i++)

if (primes[i])

for(j = i; j * i < MAX; j++) primes[i*j] = 0;

}

Ячейки массива freq[i] будут содержать частоту использования символа с ASCII кодом i. Читаем входную строку, обнуляем массив freq и заносим в него данные о частоте символов.

scanf("%s",&s);

memset(freq,0,sizeof(freq));

len = strlen(s);

for(j = 0; j < len; j++) freq[s[j]]++;

Выясним, существует ли хотя бы один символ, частота которого есть простое число. Установим флаг-переменную found в 1, если такой символ существует.

found = 0;

for(j = '0'; j <= 'z'; j++)

if (primes[freq[j]])

{

found = 1; break;

}

Если found = 0, то выводим слово empty. Иначе следует перебрать все символы от ‘0’ до ‘z’ (в лексикографическом порядке) и вывести те, частота которых есть простое число.

if (!found) printf("Case %d: empty\n",i+1);

else

{

printf("Case %d: ",i+1);

for(j = '0'; j <= 'z'; j++)

if (primes[freq[j]]) printf("%c",j);

printf("\n");

}