Документ: Задания 2012 (ДЕМО), страницы 16-18

Демонстрационный вариант ЕГЭ 2012 г. ИНФОРМАТИКА и ИКТ, 11 класс.																	(2012 - 31 / 36)

1	3		6	9	12	15		18		21	24		27	30	31
1	2		3	5	7	9		12		15	18		23	28	28
								Указания по оцениванию										Баллы
Правильное указание количества возможных программ со																		3
строгим доказательством правильности (одним из приведенных
выше способов или любым другим).
Два балла ставятся в одном из двух случаев:																		2
	1. Правильное						указание				количества				возможных программ,
			основанное на верных рассуждениях, но доказательство
			правильности неполно. В частности, оценка в 2 балла
			выставляется					в	случае,				если просто перечислены все
			правильные программы									и не доказано отсутствие других
			программ, кроме приведенных.
	2.	Приведены правильные и строгие рассуждения,
			доведенные до конца, но в вычислениях допущена
			арифметическая ошибка, в результате чего получен
			неверный ответ.
Представленное решение обладает одним из свойств																		1
	1. Указано,					что нужно рассматривать значения n, меньшие,
			чем 29, и приведены правильные рекуррентные
			соотношения (см. выше), возможно, неполные.
	2.	Правильно выписаны и обоснованы значения R(n) для
			небольших n.
	3. Правильно написан ответ, но нет его обоснования.
Не выполнено ни одно из перечисленных выше условий																		0
																Максимальный балл		3

C4 В командных олимпиадах по программированию для решения предлагается не больше 11 задач. Команда может решать предложенные задачи в любом порядке. Подготовленные решения команда посылает в единую проверяющую систему соревнований. Вам предлагается написать эффективную, в том числе по используемой памяти, программу, которая будет статистически обрабатывать пришедшие запросы, чтобы определить наиболее популярные задачи. Следует учитывать, что количество запросов в списке может быть очень велико, так как многие соревнования проходят с использованием Интернет.

Перед текстом программы кратко опишите используемый вами алгоритм решения задачи.

На вход программе в первой строке подаётся количество пришедших запросов N. В каждой из последующих N строк записано название задачи в виде текстовой строки. Длина строки не превосходит 100 символов, название может содержать буквы, цифры, пробелы и знаки препинания.

Пример входных данных:

6

Демонстрационный вариант ЕГЭ 2012 г. ИНФОРМАТИКА и ИКТ, 11 класс.

(2012 - 32 / 36)

А+B

Крестики-Нолики Прямоугольник Простой делитель А+В Простой делитель

Программа должна вывести список из трёх наиболее популярных задач с указанием количества запросов по ним. Если в запросах упоминаются менее трех задач, то выведите информацию об имеющихся задачах. Если несколько задач имеют ту же частоту встречаемости, что и третья по частоте встречаемости задача, их тоже нужно вывести.

Пример выходных данных для приведённого выше примера входных данных:

А+В 2 Простой делитель 2

Крестики-Нолики 1 Прямоугольник 1

Содержание верного ответа и указания по оцениванию

(допускаются иные формулировки ответа, не искажающие его смысла)

Программа читает все входные данные один раз, не запоминая их в массиве, размер которого равен N, а составляя только список встретившихся задач и количества запросов по каждой из них. Во время чтения данных об очередной задаче просматривается список ранее сохраненных задач; если она уже есть в списке, то количество запросов по ней увеличивается на 1, иначе задача добавляется в массив упомянутых в запросах задач (при корректных данных он не может быть больше 11). После окончания ввода производится сортировка массивов задач и количества запросов, отданных за них, в порядке убывания количества запросов, затем выводится список из трёх первых задач с указанием частоты встречаемости (или весь список, если его длина меньше трёх). Вместо сортировки можно применить и алгоритм поиска трёх максимальных элементов в массиве. Затем выводятся задачи, частота встречаемости которых не ниже, чем у третьей задачи. Баллы начисляются только за программу, которая решает задачу хотя бы для одного частного случая. Ниже приведены примеры решения задания на Алгоритмическом языке, а также на языках Паскаль и Бейсик. Допускаются решения, записанные на других языках программирования. При оценивании решений на других языках программирования необходимо учитывать особенности этих языков программирования. Так, на языке C++ при считывании строковой переменной будет считано не все название задачи, а только его первое слово, поэтому следует использовать функцию getline(cin,s), аналогичная проблема возникает и в языке Си.

Демонстрационный вариант ЕГЭ 2012 г. ИНФОРМАТИКА и ИКТ, 11 класс.

(2012 - 33 / 36)

Пример правильной и эффективной программы на языке Паскаль:

Var N, Num, i, j, t: integer; Count: array[1..11] of integer; s: string;

Names: array[1..11] of string;

Begin

Num:=0; {Число различных задач в списке запросов} ReadLn(N); {Считываем количество запросов}

for i:=1 to N do begin

ReadLn(s); {считали очередную задачу} {Осуществляем ее поиск в списке уже встретившихся}

j:=1;

while (j<=Num) and (s<>Names[j]) do j:=j+1; {Если она найдена}

if j<=Num then {Увеличиваем счетчик числа запросов} Count[j]:=Count[j]+1

else begin {Иначе добавляем задачу в конец списка} Names[j]:=s;

Count[j]:=1;

end;

Num:=Num+1 end

{Сортируем массивы Names и Count в порядке убывания значений массива Count}

for i:=Num 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; s:=Names[j]; Names[j]:=Names[j-1]; Names[j-1]:=s;

end;

if Num >= 3 then j := 3 else j := Num; i := 1;

while (i <= Num) and (Count[i] >= Count[j]) do begin

WriteLn(Names[i], ' ', Count[i]); i := i + 1;

end end.

Демонстрационный вариант ЕГЭ 2012 г. ИНФОРМАТИКА и ИКТ, 11 класс.

(2012 - 34 / 36)


	Пример правильной и эффективной программы на Алгоритмическом языке:
	литтаб Names[1:11] \| названия задач
	целтаб Count[1:11] \| счетчики числа запросов по каждой задаче
	цел i, j, t
	лит s
	\|			1.	Чтение списка запросов
\|			1.1. Инициализация количества запросов и счетчика задач
	Num:=0			\|Число различных задач в списке запросов
	ввод N			\|Считываем количество запросов
\|			1.2. Цикл чтения
	нц для i от 1 до N
		ввод s		\|Считали очередную задачу
		j:=1		\|Осуществляем ее поиск в списке уже встретившихся
		j:=1
		нц пока(j<=Num) и (s<>Names[j])
		кцj:=j+1		\|	Обрабатываем очередную задачу
		если j<=Num \| Если задача найдена в списке
		то		\|	Увеличиваем счетчик числа запросов
			Count[j]:=Count[j]+1
		иначе		\|	Добавляем задачу в конец списка
			Names[j]:=s
			Count[j]:=1
	кц	все Num:=Num+1
	кц			2. Совместно сортируем массивы Names и Count
\|				2. Совместно сортируем массивы Names и Count
\|				в порядке убывания значений массива Count
	нц для i от Num до 2 шаг -1
		нц для j от 2 до i
		если Count[j-1]<Count[j] то
			t:=Count[j]; Count[j]:=Count[j-1]; Count[j-1]:=t
		все s:=Names[j]; Names[j]:=Names[j-1]; Names[j-1]:=s
	кц	кц
	кц
	\|			3. Вывод задач-"призеров"
\|			3.1. Определение порога для количества запросов по задаче
\|				Порог равен Count[j]
	если Num >= 3
		то j := 3
		иначе j := Num
	все		3.2.	Цикл вывода
\|			3.2.	Цикл вывода

i := 1;

нц пока (i <= Num) и (Count[i] >= Count[j]) вывод нс, Names[i], ' ', Count[i]

кцi := i+ 1

кон

Демонстрационный вариант ЕГЭ 2012 г. ИНФОРМАТИКА и ИКТ, 11 класс.								(2012 - 35 / 36)

Пример правильной и эффективной программы на языке Бейсик:
DIM N, Num, i, j, t AS INTEGER
DIM Count(11) AS INTEGER
DIM s			AS STRING
DIM Names(11) AS STRING
REM		Число различных задач в списке запросов
Num		=	0
REM		Считываем количество запросов
INPUT			N
FOR i			= 1 TO N
REM		Считываем очередную задачу
	INPUT s
REM		Осуществляем ее поиск в списке уже встретившихся
	j =		1			Num AND s <> Names(j)
	WHILE j <=					Num AND s <> Names(j)
		j	= j + 1
	WEND
	IF j <= Num THEN
REM		Если она найдена, увеличиваем счетчик числа запросов
		Count(j) = Count(j)+1
	ELSE
REM		Иначе добавляем задачу в конец списка
		Names(j) = s: Count(j) = 1
		Num = Num + 1
	ENDIF
NEXT i
REM		Сортируем массивы Names и Count
REM		в	порядке убывания значений массива Count
FOR i			= Num 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
			s = Names(j)
			Names(j) = Names(j-1)
			Names(j - 1)=s
		END			IF
	NEXT j
NEXT i
REM		определение порога для количества появлений
REM		задач из списка вывода; порог равен Count(j)
IF	Num			>= 3 THEN
	j =		3
ELSE			Num
	j =		Num
END IF
i = 1			Вывод наиболее популярных задач
REM			Вывод наиболее популярных задач
WHILE			i <= Num AND Count(i) >= Count(j)
	PRINT Names(i), Count(i)
	i =		i + 1
WEND

Демонстрационный вариант ЕГЭ 2012 г. ИНФОРМАТИКА и ИКТ, 11 класс.						(2012 - 36 / 36)

	Указания по оцениванию						Баллы
Программа работает для любых входных данных произвольного
размера и находит ответ, не сохраняя входные данные в массиве,
размер которого соответствует числу N (количеству запросов).
Программа	просматривает входные данные один				раз, сохраняя
в массиве размером 11 данные о количестве решений, поданных
для каждой из встретившихся в списке задач (и учитывает, что							4
в списке их	может быть и	меньше 11). Допускается наличие
в тексте программы одной синтаксической ошибки: пропущен или
неверно указан знак пунктуации, неверно написано или пропущено
зарезервированное слово языка программирования, не описана или
неверно описана переменная, применяется операция, недопустимая
для соответствующего типа данных (если одна и та же ошибка
встречается несколько раз, то это считается за одну ошибку).
Программа	работает верно,	но входные данные			запоминаются
в массиве, размер которого соответствует числу N. Этот массив,
возможно, потом сортируется. Допускается наличие от одной до
трех синтаксических ошибок. Возможно, в принципиально верно
организованном вводе данных есть одна ошибка (например,							3
использование read вместо readln в Паскале или неверное
считывание строки в C++). Три балла также выставляется, если
в эффективной программе, удовлетворяющей критериям выстав-
ления 4 баллов, есть одна ошибка, в результате которой программа
работает неверно на некоторых наборах нетипичных входных
данных (например, все запросы относятся к одной и той же задаче).
Программа	работает в целом верно,		эффективно		или нет, но
в реализации алгоритма содержится до двух ошибок (неверная
инициализация счётчиков – хотя в предложенных выше решениях
обнулять их не требуется; возможно, программа неверно работает,
если в списке упомянуто меньше 11 задач, выход за границу							2
массива, допущена ошибка в принципиально верно организованной
сортировке или алгоритме поиска минимальных элементов,
используется знак “<” вместо “<=”, “or” вместо “and” и т. п.).
Возможно, некорректно организовано считывание входных
данных. Допускается наличие от одной до пяти синтаксических
ошибок, описанных выше.
Программа, возможно, неверно работает при некоторых входных
данных, но по приведённому тексту решения ясно, что
экзаменуемый понимает, из каких этапов должно состоять решение
задачи. При использовании сортировки она					может быть
реализована	принципиально	неверно	(например,		вместо	двух	1
циклов используется один), или допущена принципиальная ошибка

в поиске трёх максимальных элементов. Всего допускается до 4
различных ошибок в реализации алгоритма, в том числе описанных
в критериях присвоения двух баллов. Допускается наличие от
одной до семи синтаксических ошибок, описанных выше.
Задание не выполнено или выполнено неверно.							0
				Максимальный балл			4

Материал: Задания 2012 (ДЕМО)

Смотрите также: