Файл: Критерии оценивания заданий с развёрнутым ответом.pdf

Информатика. 11 класс. Вариант ИН10104 11
© СтатГрад 2018−2019 уч. г. Публикация в Интернете или печатных изданиях без письменного согласия СтатГрад запрещена
Задание 2 выполнено, если верно указана выигрышная для Пети позиция (любая из двух возможных) и описана соответствующая стратегия.
Задание 3 выполнено, если правильно указана выигрышная для
Вани позиция и построено дерево всех возможных при выигрышной стратегии партий (и только их).
Во всех случаях стратегии могут быть описаны так, как это сделано в примере решения, или другим способом.
Выполнены все три задания.
3
Не выполнены условия, позволяющие поставить 3 балла, и выполнено хотя бы одно из следующих условий.
−
Выполнено задание 3.
−
Выполнены задания 1 и 2.
2
Не выполнены условия, позволяющие поставить 2 или 3 балла, и выполнено хотя бы одно из заданий 1 и 2.
1
Не выполнено ни одно из условий, позволяющих поставить 1, 2 или 3 балла
0
Максимальный балл
3
Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, находящихся на расстоянии не меньше 8 друг от друга (разница в индексах элементов должна быть 8 или более). Необходимо определить максимальную сумму такой пары.
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (9 ≤ N ≤ 1000).
В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.
Пример входных данных:
10 1
3 5
4 6
7 9
10 12 11
Пример выходных данных для приведённого выше примера входных данных:
14
27

Информатика. 11 класс. Вариант ИН10104 12
© СтатГрад 2018−2019 уч. г. Публикация в Интернете или печатных изданиях без письменного согласия СтатГрад запрещена
Пояснение. Из 10 чисел можно составить 3 пары, удовлетворяющие условию.
Это будут элементы с индексами 1 и 9, 1 и 10, 2 и 10. Для заданного набора чисел получаем пары (1, 12), (1, 11), (3, 11). Максимальная сумма чисел в этих парах равна 14.
Напишите эффективную по времени и по памяти программу для решения этой задачи.
Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.
Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 килобайта и не увеличивается с ростом N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти, – 4 балла.
Максимальная оценка за правильную программу, эффективную только по времени или только по памяти, – 3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, – 2 балла.
Вы можете сдать
одну или две программы решения задачи. Если Вы сдадите две программы, каждая из них будет оцениваться независимо от другой, итоговой станет
бо́льшая из двух оценок.
Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Содержание верного ответа
(допускаются иные формулировки ответа, не искажающие его смысла)
Будем рассматривать каждое введённое число как правый элемент возможной пары (первые 8 чисел не могут быть такими элементами). Для получения максимальной суммы нужно сложить это число с максимальным из всех элементов, расположенных от начала последовательности до элемента, расположенного на 8 позиций раньше текущего. Будем хранить этот максимум и корректировать его при вводе каждого нового элемента.
Для этого понадобится хранить последние 8 элементов. Остальные элементы последовательности можно не хранить, это обеспечивает эффективность по памяти. Для хранения 8 элементов можно использовать циклический массив, как показано в следующем решении.

Информатика. 11 класс. Вариант ИН10104 13
© СтатГрад 2018−2019 уч. г. Публикация в Интернете или печатных изданиях без письменного согласия СтатГрад запрещена
Решение 1. Правильная и эффективная программы на языке Паскаль
(использован циклический массив)
const s
=8; {требуемое расстояние между элементами} var
N: integer; {количество чисел} x: integer; {
очередное число} a: array[0..s-1] of integer; m: integer
; {максимальное число} sm: integer
; {максимальная сумма пары} i: integer
; {счётчик для ввода} ia: integer
; {текущий индекс в массиве a} begin readln(N);
{
ввод первых s чисел} for i:=0 to s-1 do readln(a[i]);
{ввод и обработка остальных значений} m:=0; sm:=0; ia:=0; for i:=s to N-1 do begin readln(x); if a[ia] > m then m := a[ia]; if m+x > sm then sm := m+x; a[ia] := x; ia := (ia+1) mod s end; writeln(sm) end.
Вместо циклического массива можно использовать сдвиги. В этом случае для вычисления максимума всегда используется первый элемент массива, а новое число записывается в последний. Хотя этот алгоритм работает медленнее, чем алгоритм с циклическим массивом (для каждого элемента требуется 7 дополнительных присваиваний при сдвигах), основное требование эффективности здесь выполнено: при увеличении размера массива в k раз количество действий растёт не более чем в k раз. Ниже приводится пример такой программы.

Информатика. 11 класс. Вариант ИН10104 14
© СтатГрад 2018−2019 уч. г. Публикация в Интернете или печатных изданиях без письменного согласия СтатГрад запрещена
Решение 2. Правильная и эффективная программы на языке Паскаль
(использован сдвиг массива)
const s
=8; {требуемое расстояние между элементами} var
N: integer; {количество чисел} x: integer; {
очередное число} a: array[1..s] of integer; m: integer
; {максимальное число} sm: integer
; {максимальная сумма пары} i: integer
; {счётчик для ввода} ia: integer
; {счётчик для сдвига } begin readln(N);
{
ввод первых s чисел} for i:=1 to s do readln(a[i]);
{ввод и обработка остальных значений} m:=0; sm:=0; for i:=s+1 to N do begin readln(x); if a[1] > m then m := a[1]; if m+x > sm then sm := m+x; for ia:=1 to s-1 do a[ia]:=a[ia+1]; a[s] := x end; writeln(sm) end.
Возможно также «лобовое» решение: запишем все исходные числа в массив, переберём все возможные пары и выберем из них требуемую.
Такое решение не является эффективным ни по памяти (требуемая память зависит от размера исходных данных), ни по времени (количество возможных пар, а значит, количество действий и время счёта с ростом количества исходных элементов растёт квадратично). Такая программа оценивается не выше двух баллов.
Ниже приведена реализующая описанный выше алгоритм программа на языке Паскаль (использована версия PascalABC).

Информатика. 11 класс. Вариант ИН10104 15
© СтатГрад 2018−2019 уч. г. Публикация в Интернете или печатных изданиях без письменного согласия СтатГрад запрещена
Решение 3. Правильная, но неэффективная программы на языке Паскаль
const s
=8; {требуемое расстояние между элементами} var
N: integer; {количество чисел} a: array [1..1000] of integer; {
исходные данные} sm: integer
; {максимальная сумма пары} i,j: integer; begin readln(N); for i:=1 to N do readln(a[i]); sm :=0; for i := 1 to N-s do begin for j := i+s to N do begin if a[i]+a[j] > sm then sm := a[i]+a[j] end end; writeln(sm) end.
Указания по оцениванию
Баллы
Если в работе представлены две программы решения задачи, то каждая из них независимо оценивается по указанным ниже критериям, итоговой считается бόльшая из двух оценок. Описание алгоритма решения без программы оценивается в 0 баллов.
Программа правильно работает для любых входных данных произвольного размера. Используемая память не зависит от количества прочитанных чисел, а время работы пропорционально этому количеству.
Допускается наличие в тексте программы до трёх синтаксических ошибок одного из следующих видов:
1) поставлен лишний, пропущен или неверно указан знак пунктуации;
2) написано лишнее, пропущено или неверно написано служебное слово языка программирования;
3) не описана или неверно описана переменная;
4) применяется операция, недопустимая для соответствующего типа данных.
Если одна и та же ошибка встречается несколько раз, это считается за одну ошибку.
4
Не выполнены условия, позволяющие поставить 4 балла.
Программа в целом работает правильно для любых входных данных произвольного размера. Время работы пропорционально количеству введённых чисел, правильно указано, какие величины должны вычисляться по ходу чтения элементов последователь- ности чисел.
3

Информатика. 11 класс. Вариант ИН10104 16
© СтатГрад 2018−2019 уч. г. Публикация в Интернете или печатных изданиях без письменного согласия СтатГрад запрещена
Используемая память, возможно, зависит от количества прочитанных чисел (например, входные данные запоминаются в массиве, контейнере STL в C++ или другой аналогичной структуре данных).
Количество синтаксических ошибок («описок»), указанных в критериях на 4 балла, – не более пяти.
Допускается наличие не более одной ошибки следующих видов:
1) ошибка при вводе данных (не считывается значение N или неверно организован ввод последовательности);
2) ошибка при инициализации или отсутствие инициализации там, где она необходима;
3) используется неверный тип данных;
4) использована одна переменная (константа) вместо другой;
5) используется один знак операции вместо другого;
6) отсутствует вывод ответа или выводится не то значение (хотя правильный ответ в программе найден);
7) неверная работа с массивом, в том числе выход за границы массива;
8) пропущены или неверно расставлены операторные скобки
(при использовании языков с операторными скобками).
Не выполнены условия, позволяющие поставить 3 или 4 балла, при этом программа работает в целом верно и эффективно по времени. Допускается наличие до трёх содержательных ошибок, описанных в критериях на 3 балла, и до девяти синтаксических ошибок, описанных в критериях на 4 балла.
2 балла также ставится за корректные переборные решения, в которых все исходные данные сохраняются в массиве (или другой аналогичной структуре) и рассматриваются все возможные пары. При этом не допускаются содержательные логические ошибки, например выход индексов за границы массива, неверный учёт расстояния между элементами и т. д.
2
Не выполнены условия, позволяющие поставить 2, 3 или 4 балла.
При этом программа представлена и содержит как минимум два обязательных элемента, возможно, реализованных с ошибками:
1) рассматриваются только пары, находящиеся на расстоянии не меньше заданного в условии;
2) сумма элементов пары сравнивается с максимумом.
1
Не выполнены условия, позволяющие поставить 1, 2, 3 или 4 балла.
0
Максимальный балл
4