В командных олимпиадах по программированию для решения предлагается не
Условие
В командных олимпиадах по программированию для решения предлагается не больше 12 задач. Команда может решать предложенные задачи в любом порядке. Подготовленные решения команда посылает в единую проверяющую систему соревнований. Вам предлагается написать эффективную, в том числе по используемой памяти, программу, которая будет статистически обрабатывать пришедшие запросы на проверку, чтобы определить популярность той или иной задачи. Следует учитывать, что количество запросов в списке может быть очень велико, так как многие соревнования проходят с использованием сети Интернет. Перед текстом программы кратко опишите используемый Вами алгоритм решения задачи. На вход программе в первой строке подаётся количество пришедших запросов N. В каждой из последующих N строк записан номер задачи от 1 до 12. Пример входных данных: 6 1 2 1 1 5 2 Программа должна напечатать сведения о количестве запросов на проверку для каждой задачи. Сведения о каждой задаче выводятся в отдельной строке: сначала выводится номер задачи, потом — соответствующее количество запросов. Сведения о задачах, которые не поступали на проверку, выводить не нужно. Строки должны быть упорядочены по убыванию количества запросов, при равенстве количества запросов — по возрастанию номеров задач. Пример выходных данных для приведённого выше примера входных данных: 1 3 2 2 5 1 Критерии оценивания выполнения задания | Баллы | Программа работает для любых входных данных произвольного размера и находит ответ, не сохраняя входные данные в массиве, размер которого соответствует числу N (количеству запросов), а подсчитывая в массиве размером 12, сколько раз встретилась та или иная задача. Допускается наличие в тексте программы трёх синтаксических ошибок: пропущен или неверно указан знак пунктуации; неверно написано или пропущено зарезервированное слово языка программирования; не описана или неверно описана переменная; применяется операция, недопустимая для соответствующего типа данных (если одна и та же ошибка встречается несколько раз, то это считается за одну ошибку) | 4 | Программа работает верно, но входные данные сохраняются в массиве, размер которого соответствует числу N. Этот массив, возможно, потом сортируется. Или для увеличения числа встречаемости очередной задачи используется цикл от 1 до 12, или оператор case, или 12 операторов if. Допускается наличие до пяти синтаксических ошибок, описанных выше. Возможно, в принципиально верно организованном вводе данных есть одна ошибка. 3 балла также выставляется, если в эффективной программе, удовлетворяющей критериям выставления 4 баллов, есть одна ошибка, в результате которой программа работает неверно на некоторых наборах нетипичных входных данных (например, все запросы относятся к одной и той же задаче). Также 3 балла выставляется, если программа выводит на экран все задачи с верным числом запросов, но среди них есть и те, которые не встречаются в списке исходных данных (выводятся задачи, на которые не было запросов, с указанием количества запросов, равного 0) | 3 | Программа работает в целом верно, эффективно или нет, но в реализации алгоритма содержится до двух ошибок (неверная инициализация счетчиков, хотя в предложенных выше решениях обнулять их не требуется; возможно, программа работает неверно, если в списке упомянуто меньше 12 задач, выход за границу массива, допущена ошибка в принципиально верно организованной сортировке, используется знак “<” вместо “<=”, “or” вместо “and” и т.п.). Возможно, некорректно организовано считывание входных данных. Допускается наличие до семи синтаксических ошибок, описанных выше | 2 | Программа, возможно, работает неверно при некоторых входных данных, но по приведённому тексту решения ясно, что экзаменуемый понимает, из каких этапов должно состоять решение задачи. При использовании сортировки она может быть реализована принципиально неверно (например, вместо двух циклов используется один). Всего допускается до четырёх различных ошибок в реализации алгоритма, в том числе описанных в критериях присвоения 2 баллов. Допускается наличие любого количества синтаксических ошибок, описанных выше | 1 | Задание не выполнено или выполнено неверно | 0 | Максимальный балл | 4 |
Формат задания
Решение по шагам
Как рассуждать
Решение. Программа читает все входные данные один раз, не запоминая все входные данные в массиве, размер которого равен N, а подсчитывая в массиве номеров задач, сколько запросов было по каждой из них. После окончания ввода производится одновременная сортировка массивов номеров задач и количества запросов, отданных за них, в порядке убывания количества запросов; затем выводится список задач, которые встретились в списке запросов хотя бы один раз, с указанием частоты встречаемости. Баллы начисляются только за программу, которая решает задачу хотя бы для одного частного случая. Ниже приведены примеры решения задания на языках Паскаль и Бейсик. Допускаются решения, записанные на других языках программирования. При оценивании решений на других языках программирования необходимо учитывать особенности этих языков программированияПример правильной и эффективной программы на языке Паскаль: | Пример правильной и эффективной программы на языке Бейсик: | Var n, Num, i, j, t: integer; Count: array[1..12] of integer; Names: array[1..12] of integer; Begin For i := 1 to 12 do begin Count[i] := 0; Names[i] := i; end; ReadLn(N); { Считываем количество запросов} for i:=1 to N do begin ReadLn(t); {считали очередной запрос} Count[t] := Count[t] + 1; end; {Сортируем массивы Names и Count в порядке убывания значений массива Count} for i:=12 downto 2 do for j:=2 to i do if Count[j-1] < Count[j] then begin t:=Count[j]; Count[j]:=Count[j-1]; Count[j-1]:=t; t:=Names[j]; Names[j]:=Names[j-1]; Names[j-1]:=t; end; for i:=1 to 12 do if Count[i] > 0 then WriteLn(Names[i], ' ', Count[i]); end. | DIM N, i, j, t AS INTEGER DIM Count(12) AS INTEGER DIM Names(12) AS INTEGER FOR i = 1 TO 12 Count(i) = 0 Names(i) = i NEXT i INPUT N ' Считываем количество запросов FOR i = 1 TO N INPUT t ' считали задачу 'Подсчитываем её Count(t) = Count(t) + 1 NEXT i 'Сортируем массивы Names и Count в порядке убывания 'значений массива Count FOR i = 12 TO 2 STEP -1 FOR j = 2 TO i IF Count(j -
Осталось ещё 3 шага
Шаг 2
Шаг 3
Шаг 4
Бесплатно · займёт минуту