Математика ЕГЭ
Русский язык ЕГЭ
Математика 5-7
Математика ОГЭ
Информатика
Физика
Обществознание
Кликните, чтобы открыть меню

27. Программирование – оптимизация по времени и по памяти

1. Вспоминай формулы по каждой теме
2. Решай новые задачи каждый день
3. Вдумчиво разбирай решения

Нестандартные задачи

Задание 1 #12582

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

Помогите Жукодаву и напишите программу, эффективную по времени и используемой памяти для решения этой задачи. Если такого треугольника не существует, необходимо вывести ”NO“. Перед текстом программы кратко опишите алгоритм решения и укажите язык программирования и его версию.

Входные данные

В первой строке задаётся \(N\) — количество точек в заданном множестве. Каждая из следующих строк содержит два целых числа — координаты очередной точки.

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

3

6 0

0 8

9 7

Выходные данные

Если искомый треугольник существует, программа должна напечатать одно число: максимально возможную площадь треугольника, удовлетворяющего условиям. Если искомый треугольник не существует, программа должна напечатать ”NO“.

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

24

Эффективная программа

Поскольку по условию просят найти максимальную площадь треугольника, очевидно, что две вершины лежат на разных осях, а их коориднаты имеют вид \((x, 0)\) и \((0, y)\). Любой такой треугольник является прямоугольным, а, следовательно, его площадь легко можно вычислить по формуле \(|x| \cdot |y| \cdot \frac {1}{2}\). Тогда найдем координаты вида \((x, 0)\) и \((0, y)\) с максимальными \(x\) и \(y\).

Приведем пример решения на языке \(C++\):

\[\begin{array}{l} \#include \; <iostream>\\ using \; namespace \; std; \\ \\ int \; main \; ()\\ \{ \\ \quad int \; N;\\ \quad cin >> N;\\ \quad float \; x, y, x\_max=0, y\_max=0, ans=0; \\ \quad for \; (int \; i=0; \; i<N; \; i++) \; \{ \\ \quad\quad cin>>x>>y; \\ \quad\quad if \; (x==0 \; \&\& \; abs(y)>y\_max)\\ \quad\quad\quad y\_max=abs(y); \\ \quad\quad if \; (y==0 \; \&\& \; abs(x)>x\_max) \\ \quad\quad\quad x\_max=abs(x); \\ \quad \} \\ \quad ans=x\_max*y\_max/2; \\ \quad if (ans==0) \\ \quad \quad cout << ''NO''; \\ \quad else \\ \quad \quad cout << ans; \\ \quad return \; 0; \\ \} \\ \end{array}\]

Неэффективная программа

В данном случае программа будет считаться неэффиктивной, если при ее решении вы использовали двумерный массив размером \(N \times 2\), в который сначала записываете значения всех данных координат. Такая программа является неэффективной по памяти.

Ответ: См. решение

Задание 2 #12583

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

Помогите Жукодаву и напишите программу, эффективную по времени и используемой памяти для решения этой задачи. Если такого треугольника не существует, необходимо вывести ”NO“. Перед текстом программы кратко опишите алгоритм решения и укажите язык программирования и его версию.

Входные данные

В первой строке задаётся \(N\) — количество точек в заданном множестве. Каждая из следующих строк содержит два целых числа — координаты очередной точки.

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

3

6 6

\(-8\) 8

9 7

Выходные данные

Если искомый треугольник существует, программа должна напечатать одно число: максимально возможную площадь треугольника, удовлетворяющего условиям. Если искомый треугольник не существует, программа должна напечатать ”NO“.

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

48

Эффективная программа

Поскольку по условию просят найти минимальную площадь невырожденного треугольника, очевидно, что две вершины лежат на разных биссектрисах, а их коориднаты имеют вид \((a, a)\) и \((b, -b)\). Любой такой треугольник является прямоугольным, а, следовательно, его площадь легко можно вычислить по формуле \(|a| \cdot |b|\). Тогда найдем координаты вида \((a, a)\) и \((b, -b)\) с минимальными \(a\) и \(b\).

Приведем пример решения на языке \(C++\):

\[\begin{array}{l} \#include \; <iostream>\\ using \; namespace \; std; \\ \\ int \; main \; ()\\ \{ \\ \quad int \; N;\\ \quad cin >> N;\\ \quad int \; x, y, a\_min=0, b\_min=0, ans=0; \\ \quad for \; (int \; i=0; \; i<N; \; i++) \; \{ \\ \quad\quad cin>>x>>y; \\ \quad\quad if \; (x==y \; \&\& \; x!=0 \; \&\& \; ( a\_min=0 \; || \; abs(x)<a\_min))\\ \quad\quad\quad a\_min=abs(x); \\ \quad\quad if \; (x==-y \; \&\& \; x!=0 \; \&\& \; ( b\_min=0 \; || \; abs(x)<b\_min)) \\ \quad\quad\quad b\_min=abs(x); \\ \quad \} \\ \quad ans=a\_min*b\_min; \\ \quad if (ans==0) \\ \quad \quad cout << ''NO''; \\ \quad else \\ \quad \quad cout << ans; \\ \quad return \; 0; \\ \} \\ \end{array}\]

Неэффективная программа

В данном случае программа будет считаться неэффиктивной, если при ее решении вы использовали двумерный массив размером \(N \times 2\), в который сначала записываете значения всех данных координат, а затем проходите еще раз по массиву и проверяете каждую пару. Такая программа является неэффективной по памяти.

Ответ: См. решение

Задание 3 #12584

Крабодел составил список точек плоскости с целочисленными координатами, среди которых имеется хотя бы одна, не лежащая на осях координат. Крабоеду необходимо определить:

1) номер координатной четверти \(K\), в которой находится больше всего точек;

2) количество точек в этой четверти \(M\);

3) точку \(A\) в этой четверти, наименее удалённую от осей координат;

4) расстояние \(R\) от этой точки до ближайшей оси.

Если в нескольких четвертях расположено одинаковое количество точек, Крабоеду следует выбрать ту четверть, в которой величина \(R\) меньше. При равенстве и количества точек, и величины \(R\) необходимо выбрать четверть с меньшим номером \(K\). Если в выбранной четверти несколько точек находятся на одинаковом минимальном расстоянии от осей координат, нужно выбрать первую по списку. Точки, хотя бы одна из координат которых равна нулю, считаются не принадлежащими ни одной четверти и не рассматриваются.

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

Описание входных данных

В первой строке вводится одно целое положительное число — количество точек \(N\).

Каждая из следующих \(N\) строк содержит координаты очередной точки — два целых числа (первое — координата \(x\), второе — координата \(у\)).

Описание выходных данных

Программа должна вывести номер выбранной четверти \(K\), количество точек в ней \(M\), координаты выбранной точки \(A\) и минимальное расстояние \(R\) по образцу, приведённому ниже в примере.

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

7

\(-3\) 4

1 2

1 1

0 4

\(-2\) \(-3\)

\(-6\) 8

\(-12\) 1

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

\(K = 2\)

\(M = 3\)

\(A = (-12, 1)\)

\(R = 1\)

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

Приведем решение на языке \(Pascal\):

\[\begin{array}{l} var \; count, R, xR, yR: \; array[1..4] \; of \; integer;\\ \quad i, k, N, x, y: \; integer;\\ begin\\ \quad for \; i:=1 \; to \; 4 do \; count[i]:=0;\\ \quad readln(N);\\ \quad for \; i:=1 \; to \; N \; do \; begin\\ \quad\quad readln(x,y); \quad\quad if \; x*y <>0 \; then \; begin\\ \quad\quad\quad if \; (x>0) \; and \; (y>0) \; then \; k:=1 \; else \\ \quad\quad\quad if \; (x<0) \; and \; (y>0) \; then \; k:=2 \; else \\ \quad\quad\quad if \; (x<0) \; and \; (y>0) \; then \; k:=3 \; else \; k:=4; \\ \quad\quad\quad count[k]:=count[k]+1; \\ \quad\quad\quad if \; (count[k]=1) \; or \; (abs(x)<R[k]) \; or \; (abs(y)<R[k]) \; then \; begin \\ \quad\quad\quad\quad if \; (abs(x)<abs(y)) \; then \\ \quad\quad\quad\quad\quad R[k]:=abs(x) \\ \quad\quad\quad\quad else R[k]:=abs(y); \\ \quad\quad\quad\quad xR[k]:=x; \; yR[k]:=y; \\ \quad\quad\quad end;\\ \quad\quad end;\\ \quad end;\\ \quad k:=1; \\ \quad for \; i:=2 \; to \; 4 \; do \\ \quad\quad if \; (count[i]>count[k]) \; or \; (count[i]=count[k]) \; and \; (R[i]<R[k]) \; then \\ \quad\quad\quad k:=i; \\ \quad writeln\;('K = ', k); \\ \quad writeln\;('M = ', count[k]); \\ \quad writeln\;('A = (', xR[k], ',', yR[k], ')'); \\ \quad writeln\;('R = ', R[k]);\\ end.\\ \end{array}\]

Ответ: См. решение

Задание 4 #12585

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

1) оба конца отрезка принадлежат заданному множеству;

2) ни один конец отрезка не лежит на осях координат;

3) отрезок пересекается с обеими осями координат.

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

Описание входных данных

В первой строке задаётся \(N\) — количество точек в заданном множестве. Каждая из следующих строк содержит два целых числа \(x\) и \(y\) — координаты очередной точки. Гарантируется, что \(1 \leq N \leq 10000; -1000 \leq x, y \leq 1000\).

Описание выходных данных

Необходимо вывести единственное число: количество удовлетворяющих требованиям отрезков..

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

4

6 6

\(-8\) 8

\(-9\) \(-9\)

7 \(-5\)

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

2

Эффективная программа

Для того, чтобы отрезок, концы которого не лежат на осях координат, пересекался и с \(Oy\), и с \(Ox\), необходимо, чтобы его концы лежали в противоположных четвертях. Тогда подсчитаем количество точек в каждой четверти, а затем перемножим \(k_1k_3+k_2k_4\), где индексы при \(k\) — номера четвертей.

Приведем возможный вариант решения на языке \(Pascal\):

\[\begin{array}{l} \quad var\\ \quad\quad N: \; integer; \\ \quad\quad x,y: \; integer; \\ \quad\quad k1, \; k2, \; k3, \; k4: integer; \\ \quad\quad s: \; integer; \\ \quad\quad i: \; integer; \\ begin\\ \quad readln(N);\\ \quad k1:=0; k2:=0; k3:=0; k4:=0; \\ \quad for \; i:=1 \; to \; N \; do \; begin\\ \quad\quad readln(x,y);\\ \quad\quad if \; (x>0) \; and \; (y>0) \; then \; k1:=k1+1; \\ \quad\quad if \; (x<0) \; and \; (y>0) \; then \; k2:=k2+1; \\ \quad\quad if \; (x<0) \; and \; (y<0) \; then \; k3:=k3+1; \\ \quad\quad if \; (x>0) \; and \; (y<0) \; then \; k4:=k4+1; \\ \quad end; \\ \quad s:=k1*k3+k2*k4;\\ writeln(s);\\ end.\\ \end{array}\]

Неэффективная программа

В данном случае программа будет считаться неэффиктивной, если при ее решении вы использовали двумерный массив размером \(N \times 2\), в который сначала записываете значения всех данных координат, а затем проходите еще раз по массиву и проверяете каждую пару. Такая программа является неэффективной по памяти.

Ответ: См. решение

Задание 5 #12586

Жукоед выбрал на плоскости множество точек с целочисленными координатами и попросил найти Жукодава максимально возможную площадь четырехугольника, две вершины которого расположены на оси \(Oy\), а две другие лежат по разные стороны от \(Oy\).

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

Входные данные

В первой строке задаётся \(N\) — количество точек в заданном множестве. Каждая из следующих строк содержит два целых числа — координаты очередной точки.

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

6

0 0

2 0

0 2

3 \(-3\)

\(-5\) \(-5\)

6 6

Выходные данные

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

11

Сведем задачу к нахождению конкретных координат. Как можно заметить, четырехугольник состоит из двух треугольников, у которых общее основание, принажлежащее оси \(Oy\), чем оно больше – тем больше площадь четырехугольника. Так как по условию требуется, чтобы две другие вершины лежали по разные стороны от \(Oy\), для нахождения максимальной площади четырехугольника необходимо, чтобы эти вершины были максимально удалены от оси.

Таким образом, задача свелась к нахождению следующих координат: двух максимально удаленных друг от друга точек, принадлежащих \(Oy\) и точек, имеющих максимальную положительную и минимальную отрицательную координату по \(x\).

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

Приведем пример решения на языке \(Pascal\):

\[\begin{array}{l} var\\ \quad n:\;integer;\\ \quad x, y:\; integer;\\ \quad ymin, ymax: \; integer;\\ \quad ysearch: \; boolean;\\ \quad xmin, \; xmax: \; integer;\\ \quad i: \; integer;\\ \quad s: \; real;\\ begin\\ \quad ysearch := true;\\ \quad ymin:=0; ymax:=0;\\ \quad xmin:=0; xmax:=0;\\ \quad readln(n);\\ \quad for\;i:=1\;to\;n\;do\;begin\\ \quad\quad readln(x,y);\\ \quad\quad if\;x=0\;then\;begin\\ \quad\quad\quad if\;(ysearch = true) \; or \; (y<ymin) then\; ymin:=y;\\ \quad\quad\quad if\;(ysearch = true) \; or \; (y>ymax) then\; ymax:=y;\\ \quad\quad\quad ysearch:=false;\\ \quad\quad end\\ \quad\quad else \; if \; x<xmin \; then \; xmin:=x\\ \quad\quad else \; if \; x>xmax \; then \; xmax:=x\\ \quad end;\\ \quad if \; (ymax>ymin) \; and \; (xmin<0) \; and \; (xmax>0)\\ \quad\quad then\; s:=(xmax-xmin)*(ymax-ymin)/2\\ \quad else \; s:=0;\\ \quad writeln(s);\\ end.\\ \end{array}\]

Ответ: См. решение

Задание 6 #12587

Жукоед выбрал на плоскости множество точек с целочисленными координатами и попросил найти Жукодава минимально возможную площадь четырехугольника, две вершины которого расположены на оси \(Ox\), а две другие лежат по разные стороны от \(Ox\).

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

Входные данные

В первой строке задаётся \(N\) — количество точек в заданном множестве. Каждая из следующих строк содержит два целых числа — координаты очередной точки.

Выходные данные

На экран необходимо вывести только значение искомой площади.

Сведем задачу к нахождению конкретных координат. Как можно заметить, четырехугольник состоит из двух треугольников, у которых общее основание, принажлежащее оси \(Ox\), чем оно меньше – тем меньше площадь четырехугольника. Так как по условию требуется, чтобы две другие вершины лежали по разные стороны от \(Ox\), для нахождения минимальной площади четырехугольника необходимо, чтобы эти вершины были минимально удалены от оси, но не принадлежали ей, так как тогда получится вырожденный четырехугольник, площадь которого равна 0.

Таким образом, задача свелась к нахождению следующих координат: двух минимально удаленных друг от друга точек, принадлежащих \(Ox\) и точек, имеющих минимальную положительную и максимальную отрицательную координату по \(y\).

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

Приведем пример решения на языке \(Pascal\):

\[\begin{array}{l} var\\ \quad n:\;integer;\\ \quad x, y:\; integer;\\ \quad xmin, xpredmin: \; integer;\\ \quad xsearch: \; boolean;\\ \quad ymin, \; ymax: \; integer;\\ \quad i: \; integer;\\ \quad s: \; real;\\ begin\\ \quad xsearch := true;\\ \quad xmin:=0; xpredmin:=0;\\ \quad ymin:=0; ymax:=0;\\ \quad readln(n);\\ \quad for\;i:=1\;to\;n\;do\;begin\\ \quad\quad readln(x,y);\\ \quad\quad if\;y=0\;then\;begin\\ \quad\quad\quad if\;(xsearch = true) \; or \; (x<xmin) \; then\; begin\\ \quad\quad\quad\quad xpredmin:=xmin;\\ \quad\quad\quad\quad xmin:=x;\\ \quad\quad\quad end;\\ \quad\quad\quad if\;(xsearch = true) \; or \; ((x>xmin) \; and \; (x<xpredmin))\; then\; xpredmin:=x;\\ \quad\quad\quad xsearch:=false;\\ \quad\quad end\\ \quad\quad else \; if \; (y<ymin) and (y>0) \; then \; ymin:=y\\ \quad\quad else \; if \; (y>ymax) and (y<0) \; then \; ymax:=y\\ \quad end;\\ \quad if \; (xpredmin>xmin) \; and \; (ymin>0) \; and \; (ymax<0)\\ \quad\quad then\; s:=(ymin-ymax)*(xpredmin-xmin)/2\\ \quad else \; s:=0;\\ \quad writeln(s);\\ end.\\ \end{array}\]

Ответ: См. решение

Задание 7 #12588

ОАО ”Крабодельня“ выбрала на плоскости множество точек с целочисленными координатами и отправила запрос в офис Крабоедов на поиск максимально возможной площади невырожденного треугольника (т.е. имеющего ненулевую площадь), не имеющего общих точек с \(Ox\), но одна сторона которого принадлежит \(Oy\).

Помогите Крабоедам сохранить работу и напишите программу, эффективную по времени и используемой памяти для решения этой задачи. Если такого треугольника не существует, необходимо вывести ”NO“. Перед текстом программы кратко опишите алгоритм решения и укажите язык программирования и его версию.

Входные данные

В первой строке задаётся \(N\) — количество точек в заданном множестве. Каждая из следующих строк содержит два целых числа — координаты очередной точки.

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

8

0 \(-10\)

0 2

4 0

3 3

0 7

0 4

5 5

\(-9\) 9

Выходные данные

Если искомый треугольник существует, программа должна напечатать одно число: максимально возможную площадь треугольника, удовлетворяющего условиям. Если искомый треугольник не существует, программа должна напечатать ”NO“.

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

22.5

Так как треугольник не должен иметь общих точек с \(Ox\), имеет смысл рассматривать только такие треугольники, все вершины которого одновременно лежат выше или ниже оси. Найдем треугольник с максимальной площадью в верхней полуплоскости, затем аналогично в нижней и сравним их.

Поскольку одна сторона треугольника будет принадлежать \(Oy\), проще всего вычислять площадь как полупроизведение основания (сторона, принадлежащая \(Oy\)) и высоты (расстояние от основания до точки, не принадлежащей \(Oy\)).

Таким образом задача сводится к нахождению точки, координата \(x\) которой равна нулю, а координата \(y\) минимальна; точки, координата \(x\) которой равна нулю, а координата \(y\) максимальна; точки, максимально удаленной от оси \(Oy\).

Приведем пример решения задачи на языке \(Pascal\):

\[\begin{array}{l} var \; n,i,x,y,maxPosY,minPosY,maxNegY,maxNegAbsX,maxPosAbsX,s: \; longint;\\ \\ function\;max(a,b:\;longint):\;longint;\\ \quad begin\\ \quad if \; a>b\;then\; max:=a \; else \; max:=b;\\ \quad end;\\ \\ function\;min(a,b:\;longint):\;longint;\\ \quad begin\\ \quad if \; a>b\;then\; min:=b \; else \; max:=a;\\ \quad end;\\ \\ begin\\ readln(n);\\ for\;i:=1\;to\;n\;do\\ \quad begin\\ \quad readln(x);\\ \quad readln(y);\\ \quad if\;y>0\;then\\ \quad\quad begin\\ \quad\quad if\;x=0\;then\\ \quad\quad\quad begin\\ \quad\quad\quad if\; minPosY=0 \; then\\ \quad\quad\quad\quad minPosY:=y;\\ \quad\quad\quad maxPosY:=max(maxPosY, y);\\ \quad\quad\quad minPosY:=min(minPosY, y);\\ \quad\quad\quad end\;else\\ \quad\quad\quad\quad maxPosAbsX:=max(maxPosAbsX, abs(x));\\ \quad\quad end;\\ \quad if\;y<0\;then\\ \quad\quad begin\\ \quad\quad if\;x=0\;then\\ \quad\quad\quad begin\\ \quad\quad\quad if\; maxNegY=0 \; then\\ \quad\quad\quad\quad maxNegY:=y;\\ \quad\quad\quad maxNegY:=max(maxNegY, y);\\ \quad\quad\quad minNegY:=min(minNegY, y);\\ \quad\quad\quad end\;else\\ \quad\quad\quad\quad maxNegAbsX:=max(maxNegAbsX, abs(x));\\ \quad\quad end;\\ \quad end;\\ s := max((maxPosY - minPosY) * maxPosAbsX, (maxNegY - minNegY) * maxNegAbsX);\\ writeln(s / 2 :1:1);\\ end.\\ \end{array}\]

Ответ: См. решение