Автор | Сообщение |
|
Отправлено: 04.04.17 21:01. Заголовок: Задача C4. Строки. Оцените решение.
Здравствуйте, Константин Юрьевич оцените пожалуйста решение. Задача: цитата: | В командных олимпиадах по программированию для решения предлагается не больше 12 задач. Команда может решать предложенные задачи в любом порядке. Подготовленные решения команда посылает в единую проверяющую систему соревнований. Вам предлагается написать эффективную, в том числе по используемой памяти, программу, которая будет статистически обрабатывать пришедшие запросы, чтобы определить наиболее популярные задачи. Следует учитывать, что количество запросов в списке может быть очень велико, так как многие соревнования проходят с использованием Интернет. Перед текстом программы кратко опишите используемый вами алгоритм решения задачи. На вход программе в первой строке подаётся количество пришедших запросов N. В каждой из последующих N строк записано название задачи в виде текстовой строки. Длина строки не превосходит 100 символов, название может содержать буквы, цифры, пробелы и знаки препинания. Пример входных данных: 6 А+B Крестики-Нолики А+B Простой делитель А+В Простой делитель Программа должна вывести список из трёх задач, встречающихся в запросах наименьшее число раз, с указанием количества запросов по ним. Если в запросах упоминаются менее трех задач, то выведите информацию об имеющихся задачах. Если несколько задач имеют ту же частоту встречаемости, что и третья по частоте встречаемости задача, их тоже нужно вывести. Пример выходных данных для приведённого выше примера входных данных: Крестики-Нолики 1 Простой делитель 2 А+В 3 |
| Алгоритм: цитата: | Создаем два массива (один содержит название задач, другой их кол-во). Обнуляем его. Затем открываем цикл по N элементов. Вводим задачу. Если такая задача уже содержится в массиве, то увеличиваем её кол-во. Если такая задача встречается впервые, то создаем ячейку в массиве с такой задачей и присваиваем кол-во равное 1. Затем сортируем эти массивы по возрастанию (по убываю нельзя, так как содержатся нули). Затем открываем цикл с конца и выводим 3 наименьших элемента. |
| Решение: цитата: | 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. |
| Не очень приятно смотреть. Поэтому вот ссылка C4 В частности вопрос: как заменить данную строку цитата: | 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 |
|
?
|
|
|
Ответов - 6
[только новые]
|
|
|
| Администратор
|
Сообщение: 1341
|
|
Отправлено: 04.04.17 22:06. Заголовок: Optimus пишет: оцени..
Optimus пишет: цитата: | оцените пожалуйста решение. |
|
В целом нормальное решение. Сортировка, как я понимаю, по убыванию, а не по возрастанию. И я не понял, как вы обеспечите условие "Если несколько задач имеют ту же частоту встречаемости, что и третья по частоте встречаемости задача, их тоже нужно вывести. " цитата: | как заменить данную строку |
|
Циклом можно проходить по первым j-1 элементам массива "a" и ставить флаг (нашли/не нашли).
|
|
|
|
Отправлено: 04.04.17 22:27. Заголовок: Я немного не правиль..
Я немного не правильно скопировал задачу с интернета, потому что не нашел точно такую же. Условие таково: Если несколько задач имеют ту же частоту встречаемости, что и третья по частоте встречаемости задача, то вывести только одну из них. Доработка: цитата: | for i:=4 to 12 do if b[3]=b[ i] then b[ i]:=0; |
| Скажите пожалуйста, если полностью вот это решение смотреть сколько баллов вы бы поставили?
|
|
|
|
| Администратор
|
Сообщение: 1343
|
|
Отправлено: 04.04.17 22:45. Заголовок: Optimus пишет: Дораб..
Optimus пишет: Посмотрите сами, это ведь неправильно. У вас сортировка по убыванию, вы идете от конца массива при выводе. цитата: | сколько баллов вы бы поставили? |
|
1) Я не эксперт ЕГЭ. 2) Я не видел критериев. Но решение в целом хорошее. Могут снять баллы за какие-то ляпы типа "необнуления счётчика" и т.п.
|
|
|
|
Отправлено: 04.04.17 23:00. Заголовок: Верно. Но я зануляю ..
Верно. Но я зануляю все элементы после 3-его.А при выводе условие, чтобы элемент был больше нуля.
|
|
|
|
Отправлено: 05.04.17 20:41. Заголовок: Еще вопрос. Можно ли..
Еще вопрос. Можно ли использовать функции StrToInt и IntToStr, если указал среду программирования PascalABC. Не снизят ли балл?
|
|
|
|
| Администратор
|
Сообщение: 1346
|
|
Отправлено: 05.04.17 20:47. Заголовок: Optimus пишет: Можно..
Optimus пишет: цитата: | Можно ли использовать функции StrToInt и IntToStr, если указал среду программирования PascalABC. Не снизят ли балл? |
|
Можно. Не снизят. Но с большой вероятностью задач на строки не будет, потому что таки языки как Python позволяют их решать очен просто за счёт встроенных функций.
|
|
|
|