Подготовка к ЕГЭ. Решение заданий С4.

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

Описание входных данных В первой строке вводится одно целое положительное число – количество точек N. Каждая из следующих N строк содержит два целых числа: сначала координата x, затем координата y очередной точки. Описание выходных данных Программа должна вывести одно число – максимальную площадь четырёхугольника, удовлетворяющего условиям задачи. Если такого четырёхугольника не существует, программа должна вывести ноль. Пример входных данных: Пример выходных данных для приведённого выше примера входных данных: 11

6,6 0,2 2,0 0,0 3,-3 -5,-5

6,6 0,2 2,0 0,0 3,-3 -5,-5

6,6 0,2 2,0 0,0 3,-3 -5,-5

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

Не выполнены условия, позволяющие поставить 4 балла. Программа работает верно, но размер используемой памяти зависит от количества исходных данных. Например, входные данные (координаты точек) запоминаются в массиве или другой структуре данных, размер которой соответствует количеству точек. При этом обработка данных происходит с использованием эффективного по времени алгоритма, аналогичного приведённым выше. Допускается одна из следующих ошибок. 1. Поиск минимума или максимума не учитывает, что первый подходящий элемент может оказаться на любом месте в исходных данных или вообще отсутствовать. 2. Перепутаны координаты x и y, например, ищутся максимальное и минимальное значения x при y=0. 3. При вычислении площади нижнего треугольника не используется модуль, в результате его площадь учитывается со знаком «минус». 3 балла

4. Все вершины определены правильно, но площадь треугольника определена неверно, например, использована неверная формула. 5. Не учитывается, что вычисленное значение площади может быть нецелым. Например, значение площади присваивается переменной целого типа, при вычислении площади используется операция целочисленного деления (div в Паскале, деление целых величин без приведения типов в Си), при форматном выводе используется формат целого числа, или имеются другие подобные ошибки, приводящие к неверному результату при дробном ответе. 6. Неверно обрабатывается ситуация, когда искомый четырёхугольник отсутствует. Допускается наличие от одной до трёх синтаксических ошибок, описанных выше.

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

1 балл Не выполнены условия, позволяющие поставить 2, 3 или 4 балла. Программа работает в отдельных частных случаях. Один балл также ставится, если программа написана неверно, но из описания алгоритма и общей структуры программы видно, что экзаменуемый в целом правильно представляет путь решения задачи.

Статград По каналу связи передаётся последовательность положительных целых чисел. Все числа не превышают 1000, их количество известно, но может быть очень велико. Затем передаётся контрольное значение – наибольшее число R, удовлетворяющее следующим условиям: 1) R – произведение двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел, произведения различных, но равных по величине элементов допускаются); 2) R не делится на 15. В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены. Напишите эффективную, в том числе по используемой памяти, программу, которая будет проверять правильность контрольного значения. Программа должна напечатать отчёт по следующей форме: Получено чисел: … Принятое контрольное значение: … Вычисленное контрольное значение: … Контроль пройден (или Контроль не пройден)

Если удовлетворяющее условию контрольное значение определить невозможно, вычисленное контрольное значение не выводится, но выводится фраза «Контроль не пройден». Перед текстом программы кратко опишите алгоритм решения и укажите язык программирования и его версию. Входные данные В первой строке указывается количество чисел N. В каждой из последующих N строк записано одно натуральное число, не превышающее В последней строке записано контрольное значение. Пример входных данных: Выходные данные Программа должна напечатать отчёт по образцу, приведённому в условии. Пример выходных данных для приведённого выше примера входных данных: Получено чисел: 5 Принятое контрольное значение: 800 Вычисленное контрольное значение: 800 Контроль пройден

Вариант С Сибирь На ускорителе для большого числа частиц производятся замеры скорости каждой из них. Чтобы в документации качественно отличать одну серию эксперимента от другой, каждую серию решили характеризовать числом, равным максимальному произведению, которое можно получить, перемножая скорости некоторых частиц, данной серии. То есть требуется выбрать такое непустое подмножество частиц (в него может войти как одна частица, так и все частицы серии), произведение значений скоростей у которого будет максимальным. Если таких подмножеств несколько, то выбрать можно любое из них. Напишите эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет обрабатывать результаты эксперимента, находя искомое подмножество. В нашей модели скорость частицы – это вещественное неотрицательное число, записанное с точностью один знак после десятичной точки. Частиц, скорость которых измерена, может быть очень много, но не может быть меньше трех. Скорости всех частиц различны. Перед текстом программы кратко опишите используемый вами алгоритм решения задачи.

На вход программе в первой строке подается количество частиц N. В каждой из последующих N строк записано одно вещественное число с точностью до 1 знака после десятичной точки. Все числа различны. Пример входных данных: Программа должна вывести в порядке возрастания номера частиц, произведение скоростей которых будет характеризовать данную серию. Нумерация частиц ведется с единицы. Пример выходных данных для приведенного выше примера входных данных: 1 3 5

Содержание верного ответа и указания по оцениванию (допускаются иные формулировки ответа, не искажающие его смысла) Характеристикой серии является произведение всех значений скоростей, кроме тех, которые меньше единицы. Если же все скорости меньше единицы, то ответом является максимальная из них. Программа читает все входные данные один раз, не запоминая все входные данные в массиве, размер которого равен N. Во время чтения данных в массиве с индексами от 0 до

* *

Пример правильной и эффективной программы на языке Паскаль: var n,i,j,k,b,c: longint; a, max: real; d: array[0..9] of integer; begin readln(n); k := 0; c := 0; max := 0; for i := 0 to 9 do d[i] := 0; for i := 1 to n do begin readln(a); b := round(a*10); if b < 10 then begin d[b] := i; if a > max then begin max := a; k := i; end else c := c + 1; end; if c = 0 then writeln(k) else if c = n then for i := 1 to n do write(i,' ') else for i := 1 to n do begin c := 0; for j := 0 to 9 do if d[j] = i then begin c := 1; break end; if c = 0 then write(i,' '); end; readln; end.

Задание С4 единого банка заданий ФИПИ 2014 стр.53 На ускорителе для большого числа частиц производятся замеры скорости каждой из них. Скорость частицы – это целое число (положительное, отрицательное или 0). Частиц, скорость которых измерена, может быть очень много, но не может быть меньше трёх. Скорости всех частиц различны. При обработке результатов в каждой серии эксперимента отбирается основное множество скоростей. Это такое непустое множество скоростей частиц (в него могут войти как скорость одной частицы, так и скорости всех частиц серии), для которого произведение скоростей является максимальным среди всех возможных множеств. При нахождении произведения знак числа учитывается. Если есть несколько таких множеств, то основным считается то, которое содержит наибольшее количество элементов. Вам предлагается написать эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет обрабатывать результаты эксперимента, находя основное множество. Перед текстом программы кратко опишите используемый Вами алгоритм решения задачи. На вход программе в первой строке подаётся количество частиц N. В каждой из последующих Nстрок записано одно целое число, по абсолютной величине не превышающее 109. Пример входных данных: Программа должна вывести в порядке возрастания номера частиц, скорости которых принадлежат основному множеству данной серии. Нумерация частиц ведётся с единицы. Пример выходных данных для приведённого выше примера входных данных: 1 2 5