В телевизионном танцевальном марафоне с определением победителя с помощью телезрителей после каждого тура объявляется sms-голосование, в котором зрители указывают наиболее понравившуюся им пару из максимум 16 пар, которые участвуют в проекте. Вам предлагается написать программу, которая будет обрабатывать результаты sms-голосования по данному вопросу. Результаты голосования получены в виде номеров пар (каждый элемент списка соответствует одному sms-сообщению).
Вам предлагается два задания с похожими условиями: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Задание Б более сложное, его решение оценивается выше. Итоговая оценка выставляется как максимальная из оценок за задания А и Б.
Задание А. Имеется набор данных, состоящий из 15 чисел.
Напишите программу для решения такой задачи. В этом варианте задания оценивается только правильность программы, время работы и размер использованной памяти не имеют значения.
Максимальная оценка за правильную программу – 2 балла.
Задание Б. Имеется набор данных, состоящий из целых чисел. Набор может быть очень большим.
Напишите программу для решения этой задачи.
Постарайтесь сделать программу эффективной по времени и используемой памяти (или хотя бы по одной из этих характеристик).
Программа считается эффективной по времени, если время работы программы пропорционально количеству пар чисел N, т. е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.
Максимальная оценка за правильную программу, эффективную по времени и памяти, — 4 балла.
Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла.
Следует учитывать, что количество голосов в списке может быть очень велико. Перед текстом программы кратко опишите используемый Вами алгоритм решения задачи. На вход программе в первой строке подаётся количество пришедших sms-сообщений N. В каждой из последующих N строк записан номер пары от 1 до 16.Пример входных данных:
4
2
16
3
2
Программа должна вывести список всех пар, встречающихся в списке, в порядке убывания (невозрастания) количества голосов, отданных за ту или иную пару, с указанием количества отданных за неё голосов. При этом каждая пара должна быть выведена ровно один раз вне зависимости от того, сколько раз она встречается в списке. Пример выходных данных для приведённого выше примера входных данных:
2 2
3 1
16 1
Программа читает все входные данные один раз, не запоминая все входные данные в массиве, размер которого равен N, а сразу подсчитывая в массиве пар, сколько голосов отдано за каждую из них. После окончания ввода производится одновременная сортировка массивов номеров пар и количества голосов, отданных за них, в порядке убывания количества голосов; затем выводится список пар, за которые подано ненулевое число голосов, с указанием частоты встречаемости. Баллы начисляются только за программу, которая решает задачу хотя бы для одного частного случая. Ниже приведены примеры решения задания на языках Паскаль и Бейсик. Допускаются решения, записанные на других языках программирования. При оценивании решений на других языках программирования необходимо учитывать особенности этих языков программирования
| Пример правильной и эффективной программы на языке Паскаль: | Пример правильной и эффективной программы на языке Бейсик: |
|---|---|
Var n, i, j, t: integer; Count, Names: array[1..16] of integer; Begin For i := 1 to 16 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:=16 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 16 do if Count[i] > 0 then writeLn(Names[i], ' ', Count[i]); end. | DIM N, i, j, t AS INTEGER DIM Count(16) AS INTEGER DIM Names(16) AS INTEGER FOR i = 1 TO 16 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 = 16 TO 2 STEP -1 FOR j = 2 TO i IF Count(j - 1) < Count(j) THEN 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 IF NEXT j NEXT i FOR i = 1 TO 16 IF Count(i) > 0 THEN PRINT Names(i), Count(i) NEXT i END |
Приведём решение Даниила Доценко, Pascal ABC.
var a:array [1..16] of integer;
k,i,n,j:integer;
begin
readln(n);
for i:=1 to n do begin
readln(k);
a[k]:=a[k]+1;
end;
k:=0;
for i:=1 to 16 do
if a[i]>k then k:=a[i];
for j:=k downto 1 do
for i:=1 to 16 do
if j=a[i] then writeln(i,' ',a[i]);
end.
Пример решения задачи А на языке Паскаль.
vara: array[1..16] of integer; {исходные данные}
val: integer; {пара}
lenght: integer; {количество голосов за пару}
i, j, k: integer;
begin
for i := 1 to 15 do read(a[i]);
for i:=1 to 15-1 do
for j:=1 to 15-i do
if a[j] < a[j+1] then begin
k := a[j];
a[j] := a[j+1];
a[j+1] := k;
end;
lenght := 1;
for i := 1 to 15 do
if a[i]=a[i+1] then
lenght := lenght + 1
else begin
writeln(a[i], ' ', lenght);
lenght := 1;
end;
end.
| Критерии оценивания выполнения задания | Баллы |
|---|---|
| Программа работает для любых входных данных произвольного размера и находит ответ, не сохраняя входные данные в массиве, размер которого соответствует числу N (количеству запросов), а подсчитывая в массиве размером 12, сколько раз встретилась та или иная задача. Допускается наличие в тексте программы трёх синтаксических ошибок: пропущен или неверно указан знак пунктуации; неверно написано или пропущено зарезервированное слово языка программирования; не описана или неверно описана переменная; применяется операция, недопустимая для соответствующего типа данных (если одна и та же ошибка встречается несколько раз, то это считается за одну ошибку) | 4 |
| Программа работает верно, но входные данные сохраняются в массиве, размер которого соответствует числу N. Этот массив, возможно, потом сортируется. Или для увеличения числа встречаемости очередной пары используется цикл от 1 до 16, или оператор case, или 16 операторов if. Допускается наличие до пяти синтаксических ошибок, описанных выше. Возможно, в принципиально верно организованном вводе данных есть одна ошибка. 3 балла также выставляется, если в эффективной программе, удовлетворяющей критериям выставления 4 баллов, есть одна ошибка, в результате которой программа работает неверно на некоторых наборах нетипичных входных данных (например, все подали голоса за одну и ту же пару). Также 3 балла выставляется, если программа выводит на экран все пары с верным количеством поданных за них голосов, но среди них есть и те, за кого не было подано ни одного голоса | 3 |
| Программа работает в целом верно, эффективно или нет, но в реализации алгоритма содержится до двух ошибок (неверная инициализация счётчиков, хотя в предложенных выше решениях обнулять их не требуется; возможно, программа работает неверно, если в списке упомянуто меньше 16 пар, выход за границу массива, допущена ошибка в принципиально верно организованной сортировке, используется знак “<” вместо “<=”, “or” вместо “and” и т.п.). Возможно, некорректно организовано считывание входных данных. Допускается наличие до семи синтаксических ошибок, описанных выше | 2 |
| Программа, возможно, работает неверно при некоторых входных данных, но по приведённому тексту решения ясно, что экзаменуемый понимает, из каких этапов должно состоять решение задачи. При использовании сортировки она может быть реализована принципиально неверно (например, вместо двух циклов используется один). Всего допускается до четырёх различных ошибок в реализации алгоритма, в том числе описанных в критериях присвоения 2 баллов. Допускается наличие любого количества синтаксических ошибок, описанных выше | 1 |
| Задание не выполнено или выполнено неверно | 0 |
| Максимальный балл | 4 |
хочу предложить решение задачи 6436 для пункта б. На мой взгляд быстрее, чем Даниила Доценко
var
a, b: array [1..16] of integer;
x, n, i, max, max2: integer;
begin
read(n);
for i := 1 to n do
begin
read(x);
a[x] += 1;
if a[x] > max then
max := a[x];
end;
while max > 0 do
begin
for i := 1 to 16 do
begin
if a[i] = max then
writeln(i, ' ', a[i]);
if (a[i] > max2) and (a[i] < max) then
max2 := a[i];
end;
max := max2;
max2 := 0;
end;
end.