Форум » Обработка числовых последовательностей » Задача C4. Строки. Оцените решение. » Ответить

Задача C4. Строки. Оцените решение.

Optimus: Здравствуйте, Константин Юрьевич оцените пожалуйста решение. Задача: [quote]В командных олимпиадах по программированию для решения предлагается не больше 12 задач. Команда может решать предложенные задачи в любом порядке. Подготовленные решения команда посылает в единую проверяющую систему соревнований. Вам предлагается написать эффективную, в том числе по используемой памяти, программу, которая будет статистически обрабатывать пришедшие запросы, чтобы определить наиболее популярные задачи. Следует учитывать, что количество запросов в списке может быть очень велико, так как многие соревнования проходят с использованием Интернет. Перед текстом программы кратко опишите используемый вами алгоритм решения задачи. На вход программе в первой строке подаётся количество пришедших запросов N. В каждой из последующих N строк записано название задачи в виде текстовой строки. Длина строки не превосходит 100 символов, название может содержать буквы, цифры, пробелы и знаки препинания. Пример входных данных: 6 А+B Крестики-Нолики А+B Простой делитель А+В Простой делитель Программа должна вывести список из трёх задач, встречающихся в запросах наименьшее число раз, с указанием количества запросов по ним. Если в запросах упоминаются менее трех задач, то выведите информацию об имеющихся задачах. Если несколько задач имеют ту же частоту встречаемости, что и третья по частоте встречаемости задача, их тоже нужно вывести. Пример выходных данных для приведённого выше примера входных данных: Крестики-Нолики 1 Простой делитель 2 А+В 3 [/quote] Алгоритм: [quote]Создаем два массива (один содержит название задач, другой их кол-во). Обнуляем его. Затем открываем цикл по N элементов. Вводим задачу. Если такая задача уже содержится в массиве, то увеличиваем её кол-во. Если такая задача встречается впервые, то создаем ячейку в массиве с такой задачей и присваиваем кол-во равное 1. Затем сортируем эти массивы по возрастанию (по убываю нельзя, так как содержатся нули). Затем открываем цикл с конца и выводим 3 наименьших элемента.[/quote] Решение: [quote]program one; var a:array [1..12] of string[100]; n,j,z,t,i:integer; st,p:string; b:array [1..100] of integer; begin readln(n); //вводим кол-во задач for i:=1 to 12 do //обнуляем массивы begin a:=''; b:=0; end; j:=1; for i:=1 to n do begin readln(st); //вводим название задачи if (st=a[1])or(st=a[2])or(st=a[3])or(st=a[4])or(st=a[5])or(st=a[6])or(st=a[7])or(st=a[8])or(st=a[9])or(st=a[10])or(st=a[11])or(st=a[12]) then begin for z:=1 to 12 do //если задача уже есть такая в массиве, то мы увеличиваем кол-во этой задачи на одну if st=a[z] then b[z]:=b[z]+1; end else //если это задача встречается впервые, мы вбиваем её в массив и присваеваем ей кол-во=1 begin a[j]:=st; b[j]:=1; j:=j+1; end; end; for i:=1 to 11 do for j:=i+1 to 12 do if b[j]>b then //выполняем сортировку по возрастанию, потому что содержатся нули begin t:=b; b:=b[j]; b[j]:=t; p:=a; a:=a[j]; a[j]:=p; end; for i:=4 to 12 do if b[3]=b[ i] then b[ i]:=0; z:=0; for i:=12 downto 1 do //открываем цикл с конца if (z<>3)and(b>0) then begin //выводим 3 задачи, которые встречаются меньше всего writeln(a,' ',b); //a-название задачи; b-кол-во z:=z+1; end; readln; end. [/quote] Не очень приятно смотреть. Поэтому вот ссылка C4 В частности вопрос: как заменить данную строку [quote] if (st=a[1])or(st=a[2])or(st=a[3])or(st=a[4])or(st=a[5])or(st=a[6])or(st=a[7])or(st=a[8])or(st=a[9])or(st=a[10])or(st=a[11])or(st=a[12]) then [/quote]?

Ответов - 6

Поляков: Optimus пишет: оцените пожалуйста решение. В целом нормальное решение. Сортировка, как я понимаю, по убыванию, а не по возрастанию. И я не понял, как вы обеспечите условие "Если несколько задач имеют ту же частоту встречаемости, что и третья по частоте встречаемости задача, их тоже нужно вывести. " как заменить данную строку Циклом можно проходить по первым j-1 элементам массива "a" и ставить флаг (нашли/не нашли).

Optimus: Я немного не правильно скопировал задачу с интернета, потому что не нашел точно такую же. Условие таково: Если несколько задач имеют ту же частоту встречаемости, что и третья по частоте встречаемости задача, то вывести только одну из них. Доработка: for i:=4 to 12 do if b[3]=b[ i] then b[ i]:=0; Скажите пожалуйста, если полностью вот это решение смотреть сколько баллов вы бы поставили?

Поляков: Optimus пишет: Доработка: Посмотрите сами, это ведь неправильно. У вас сортировка по убыванию, вы идете от конца массива при выводе. сколько баллов вы бы поставили? 1) Я не эксперт ЕГЭ. 2) Я не видел критериев. Но решение в целом хорошее. Могут снять баллы за какие-то ляпы типа "необнуления счётчика" и т.п.


Optimus: Верно. Но я зануляю все элементы после 3-его.А при выводе условие, чтобы элемент был больше нуля.

Optimus: Еще вопрос. Можно ли использовать функции StrToInt и IntToStr, если указал среду программирования PascalABC. Не снизят ли балл?

Поляков: Optimus пишет: Можно ли использовать функции StrToInt и IntToStr, если указал среду программирования PascalABC. Не снизят ли балл? Можно. Не снизят. Но с большой вероятностью задач на строки не будет, потому что таки языки как Python позволяют их решать очен просто за счёт встроенных функций.



полная версия страницы