В командных олимпиадах по программированию для решения предлагается не
Условие
В командных олимпиадах по программированию для решения предлагается не больше 12 задач. Команда может решать предложенные задачи в любом порядке. Подготовленные решения команда посылает в единую проверяющую систему соревнований. Вам предлагается написать эффективную, в том числе по используемой памяти, программу, которая будет статистически обрабатывать пришедшие запросы на проверку, чтобы определить популярность той или иной задачи. Следует учитывать, что количество запросов в списке может быть очень велико, так как многие соревнования проходят с использованием сети Интернет. Перед текстом программы кратко опишите используемый Вами алгоритм решения задачи. На вход программе в первой строке подаётся количество пришедших запросов N. В каждой из последующих N строк записан номер задачи от 1 до 12. Пример входных данных: 6 1 2 1 1 5 2 Программа должна напечатать сведения о количестве запросов на проверку для каждой задачи. Сведения о каждой задаче выводятся в отдельной строке: сначала выводится номер задачи, потом — соответствующее количество запросов. Сведения о задачах, которые не поступали на проверку, выводить не нужно. Строки должны быть упорядочены по убыванию количества запросов, при равенстве количества запросов — по возрастанию номеров задач. Пример выходных данных для приведённого выше примера входных данных: 1 3 2 2 5 1
Формат задания
Решение по шагам
Как рассуждать
Решение. Программа читает все входные данные один раз, не запоминая все входные данные в массиве, размер которого равен 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 шага
< Count(j) THEN t = Count(j): Count(j) =…
= t t = Names(j): Names(j) = Names(j - 1)…
= t END IF NEXT j NEXT i FOR i = 1 TO 12 IF…
Бесплатно · займёт минуту