РЕШУ ЕГЭ — информатика

Задания

По каналу связи передаётся последовательность положительных целых чисел Х₁, Х₂, ... все числа не превышают 1000, их количество заранее неизвестно. Каждое число передаётся в виде отдельной текстовой строки, содержащей десятичную запись числа. Признаком конца передаваемой последовательности является число 0.

Участок последовательности от элемента Х_T до элемента X_T+N называется подъёмом, если на этом участке каждое следующее число больше или равно предыдущему, причем участок нельзя расширить, т. е.

1)  Т = 1 или Х_T-1 > Х_T

2)  X_T+N  — последний элемент последовательности или X_T+N > X_T+N+1. Высотой подъёма называется разность X_T+N − Х_T. Подъём считается значительным, если высота подъёма больше величины минимального элемента этого подъема.

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

Программа должна вывести результаты в следующей форме:

Получено чисел: ...

Найдено значительных подъемов: ...

Вам предлагаются два задания, связанные с этой задачей: задание А и задание Б. Вы можете решать оба задания А и Б или одно из них по своему выбору.

Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание составляет 0 баллов.

Задание Б является усложненным вариантом задания А, оно содержит дополнительные требования к программе. Перед программой укажите версию языка программирования.

А. Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве, после чего будут проверены все возможные пары элементов.

Обязательно укажите, что программа является решением задания А.

Максимальная оценка за выполнение задания А – 2 балла.

Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).

Программа считается эффективной по времени, если время работы программы пропорционально количеству элементов последовательности N, т. е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Обязательно укажите, что программа является решением задания Б.

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

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

144

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

Получено чисел: 9

Найдено значительных подъемов: 1

Решение. Ниже приведены примеры решения задания на языке Паскаль, на алгоритмическом языке и на языке Бейсик. Допускаются решения, записанные на других языках программирования.

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

program с4_1;

var

n, up, х, start, last : integer;

begin

n: =0;

up:=0;

start:=1001;

last:=1001;

repeat

readln(x);

n: =n+1;

if x < last then begin

if last > 2*start then up:=up+1;

start:=x;

end;

last:=x;

until x = 0;

writeln('Получено чисел: ', n-1);

writeln('Найдено значительных подъемов: ', up);

end.

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

алг С4_1

нач

цел n, up, х, start, last

n: =0

up: =0

start:=1001

last:=1001

нц

ввод x

n: =n+1

если x < last to

если last > 2*start to up:=up+1 все

start:=x;

все

last:=x;

кц при x=0

вывод "Получено чисел: ", n-1, не

вывод "Найдено значительных подъемов: ", up, не кон

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

DIM n, up, х, start, last AS INTEGER

n=0

up=0

start=1001

last=1001

INPUT x

n = n + 1

IF x < last THEN

IF last > 2 * start THEN up = up + 1

start = x;

END IF

last = x

LOOP UNTIL x = 0

PRINT "Получено чисел: "; n-1

PRINT "Найдено значительных подъемов: up

Приводим решение Игоря Кудашева на Python 3. Программа эффективна только по времени.

a = []

count = 0

up = 0

m = 0

while True:

    x = int(input())

    if x == 0: break

    else: a.append(x)

for i in range(len(a) - 1):

    if a[i] <= a[i + 1] and up == 0:

        up = 1

        m = a[i]

    if a[i] > a[i + 1]:

        up = 0

        if a[i] - m > m:

            count += 1

print('Получено чисел:', len(a))

print('Найдено значительных подъемов:', count)

Критерии проверки:

Пояснения для проверяющих.

1. Задание Б является усложнением задания А. Если в качестве решения задания Б представлено решение задания А, то согласно приведённым ниже критериям, его оценка будет такой же, как если бы это решение было представлено в качестве решения задания А.

2. Два задания и, соответственно, возможность для экзаменуемого представить две программы дают ученику возможность (при его желании) сначала написать менее сложное и менее эффективное решение (задание А), которое даёт ему право получить два балла, а затем приступить к поиску более эффективного решения.

3. Каждая из программ, представленных экзаменуемым (но не более двух), оценивается по нижеследующим критериям. В качестве итоговой оценки берётся наибольшая из двух оценок.

Критерии оценивания выполнения задания	Баллы
Программа правильно работает для любых входных данных произвольного размера. Используемая память не зависит от количества прочитанных чисел, а время работы пропорционально этому количеству. Допускается наличие в тексте программы до трех синтаксических ошибок одного из следующих видов: 1) пропущен или неверно указан знак пунктуации; 2) неверно написано или пропущено зарезервированное слово языка программирования; 3) не описана или неверно описана переменная; 4) применяется операция, недопустимая для соответствующего типа данных. Если одна и та же ошибка встречается несколько раз, это считается за одну ошибку.	4
Не выполнены условия, позволяющие поставить 4 балла. Программа в целом работает правильно для любых входных данных произвольного размера. Время работы пропорционально количеству введённых чисел, правильно указано, какие величины должны вычисляться по ходу чтения элементов последовательности чисел. Количество синтаксических ошибок (описок) указанных выше видов — не более пяти. Используемая память, возможно, зависит от количества прочитанных чисел (например, входные данные запоминаются в массиве или другой структуре данных (контейнер priority_queue, vector, set или map в С++)). Допускается ошибка при вводе данных, неверный или неполный вывод результатов или неверная работа программы в «экзотических» ситуациях. Кроме того, допускается наличие одной ошибки, принадлежащей к одному из следующих видов ошибок: 1) ошибка при инициализации минимумов; 2) неверно обрабатывается ситуация, когда один или несколько миниимумов не определены; 3) допущен выход за границу массива; 4) используется знак < вместо <=, or вместо and и т. п.	3
Не выполнены условия, позволяющие поставить 3 или 4 балла. Программа работает в целом верно, эффективно или нет, но, в реализации алгоритма есть до двух содержательных ошибок, допустимые виды ошибок перечислены в критериях на 3 балла. Количество синтаксических описок не должно быть более девяти. Программа может быть неэффективна по времени. Например, все числа запоминаются в массиве и перебираются все возможные пары элементов последовательности: min := 2001; for i := 1 to N - 1 do begin for j := i + 1 to N do begin if ((a[i]+a[j]) mod 2 = 1) and (a[i]+a[j] < min) then min := a[i]+a[j]; end end;	2
Не выполнены условия, позволяющие поставить 2, 3 или 4 балла. Из описания алгоритма или общей структуры программы видно, что экзаменуемый в целом правильно представляет путь решения задачи независимо от эффективности. При этом программа может отсутствовать или быть представленной отдельными фрагментами, без ограничений на количество ошибок.	1
Не выполнены критерии, позволяющие поставить 1, 2, 3 или 4 балла	0
Максимальный балл	4

Ключ