6260. Организация соревнования

Маленькие Дима и Петя хотят организовать соревнование. Их маленькие друзья выслали им несколько задач. Теперь Дима и Петя должны выбрать несколько задач для соревнования. Поскольку они еще маленькие, то не могут оценить качество задач, однако они знают что в хорошем контесте заглавия первой задачи начинаются с буквы A, заглавия второй задачи – с буквы B и так далее.

Заданы заглавия предложенных задач. Помогите братьям определить наибольшее количество задач в хорошем соревновании, которое они смогут организовать.

Вход. Первая строка содержит одно число n – количество предложенных задач, полученных маленькими братьями (1 ≤ n ≤ 100).

Следующие n строк содержат заглавия предложенных задач, по одной в строке. Длина каждого заглавия не превосходит 30 символов. Каждое заглавие начинается с заглавной буквы и содержит буквы только латинского алфавита, цифры и символы подчеркивания.

Выход. Вывести одно число – наибольшее возможное количество задач в хорошем соревновании. Если хорошего соревнования устроить нельзя, вывести 0.

Пример входа

12

Arrangement_of_Contest

Ballot_Analyzing_Device

Correcting_Curiosity

Dwarf_Tower

Energy_Tycoon

Flight_Boarding_Optimization

Garage

Heavy_Chain_Clusterization

Intellectual_Property

J

Kids_in_a_Friendly_Class

Lonely_Mountain

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

12

РЕШЕНИЕ

сортировка подсчетом

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

Используя сортировку подсчетом найдем, сколько имеется названий задач, начинающихся с каждой буквы. Далее найдем лексикографически наименьшую заглавную букву c, с которой не начинается ни одного названия. Тогда наибольшее возможное количество задач в хорошем соревновании равно c – 'A’.

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

Объявим используемые массивы. m[i] содержит количество названий задач, начинающихся с буквы, ASCII код которых равен i.

#define MAX 260

int m[MAX];

char s[50];

Читаем входные данные. Совершаем сортировку подсчетом.

scanf("%d\n",&n);

for(i = 0; i < n; i++)

{

gets(s);

m[s[0]]++;

}

Ищем лексикографически наименьшую заглавную букву, с которой не начинается ни одного названия. Целочисленная переменная i содержит ASCII код такой буквы.

for(i = 'A'; i <= 'Z'; i++)

if (m[i] == 0) break;

Выводим наибольшее возможное количество задач в хорошем соревновании.

printf("%d\n", i - 'A');