Главная | Информатика и информационно-коммуникационные технологии | Подготовка к ЕГЭ | Контрольные тренировочные задания

Контрольные тренировочные задания
(решения)

Часть 2

Задание 27

Решение примера 1

Задание А (более легкое, чем Б)
Имеется набор данных, состоящий из 5 пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма квадратов всех выбранных чисел была нечетной и при этом максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

Напишите программу для решения этой задачи. В этом варианте задания оценивается только правильность программы, время работы и размер использованной памяти не имеет значения.
Максимальная оценка за правильную программу - 2 балла.

Задание Б (более сложное, чем А)
Имеется набор данных, состоящих из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма квадратов всех выбранных чисел была нечетной и при этом максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

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

Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.

Максимальная оценка за правильную программу, эффективную по времени и по памяти, - 4 балла.

Как в варианте А, так и в варианте Б программа должна напечатать одно число - максимально возможную сумму, соответствующую условиям задачи (или 0, если такую сумму получить нельзя).

Например:
2  6
4  1
7  3
2  9
7  4
sum=231

Решение.

Задание Б (алгоритм):

поскольку в задании указано, что "имеется набор данных, состоящих из пар...", то введем в программу переменную n для количества пар, значение которой будет считываться со стандартного входного потока:

n:longint; {количество пар чисел};

объявим сами числа типа integer, переменную цикла - i - типа integer и дополнительные переменные, смысл которых будет объяснен ниже. Объявление сделаем в отдельных строках (так можно не делать), чтобы можно было ввести удобно комментарии:

 x,y: integer; {пара чисел}
 max: integer; {максимальное из пары}
 min: integer; {минимальное из пары}
 sum:longint; {сумма квадратов отобранных чисел}
 min_kvadr:longint; {мин. нечетная разница квадратов max и min}
 i:integer;

так как в задании не оговаривается, что пары чисел считывается из файла, значит их необходимо считать со стандартного входного потока оператором readln(); т.е. организуем цикл:

for i:=1 to n do begin
  readln(x,y);
  ...

Допустим имеем пары:

Чтобы получить в итоге максимальную сумму, то необходимо суммировать те числа из пар чисел, которые максимальны в паре, т.е. в нашем случае будем суммировать квадраты выделенных чисел из пар:

но сначала определим максимальное и минимальное число из каждой пары:

if x>y then 
begin 
   max:=x; min:=y 
end
else 
begin 
    max:=y;min:=x 
end;

далее суммируем квадраты максимальных чисел:

sum:=sum+sqr(max);

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

2 6 - разница 4
4 1 - разница 3
7 3 - разница 4
2 9 - разница 7
7 4 - разница 3

Поиск минимальной и нечетной разницы между квадратами чисел в паре:

if((max-min) mod 2 > 0) and ((sqr(max)-sqr(min)) < min_kvadr) then
    min_kvadr:=sqr(max) - sqr(min)

при этом для переменной, обозначающей разницу, до цикла необходимо назначить максимально возможное значение:

min_kvadr:=1073676289;  {32 767 * 32 767 (самое большое в типе integer) }

таким образом, в цикле у нас происходит: 1. поиск максимального и минимального числа из пары; 2. вычисляется сумма максимальных чисел из каждой пары; 3. находится минимальная разница квадратов максимального и минимального числа в парах.
после цикла необходимо проверить сумму на нечетность. Если сумма четная (чего НЕ должно быть по условию), то отнимем от суммы вычисленную минимальную разницу. Но при этом учтем, что если не нашлось нечетной минимальной разницы, то выводим 0 (по условию):

if sum mod 2 = 0 then begin
  if min_kvadr > 10000 then sum := 0
  else sum:=sum - min_kvadr
end;

Задание Б (эффективная программа):

var
 n:longint; {количество пар чисел}
 x,y: integer; {пара чисел}
 max: integer; {максимальное из пары}
 min: integer; {минимальное из пары}
 sum:longint; {сумма квадратов отобранных чисел}
 min_kvadr:longint; {мин. нечетная разница квадратов max и min}
 i:integer;
begin
sum:=0;
readln(n);
min_kvadr:=1073676289;  {32 767 * 32 767, самое большое integer}
for i:=1 to n do begin
  readln(x,y);
  if x>y then begin max:=x; min:=y end
  else begin max:=y;min:=x end;
  sum:=sum+sqr(max);
  if((max-min) mod 2 > 0) and ((sqr(max)-sqr(min)) < min_kvadr) then
    min_kvadr:=sqr(max) - sqr(min)
end;
if sum mod 2 = 0 then begin
  if min_kvadr > 10000 then sum := 0
  else sum:=sum - min_kvadr
end;
writeln('sum=',sum)
end.

Пример работы программы:

Возврат на страницу Решение примеров части 2 задание 27

Контрольные тренировочные задания(решения)

Часть 2

Задание 27

Контрольные тренировочные задания
(решения)