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

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

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

Пары на заданном расстоянии

Задание 1 #12277

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

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

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

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

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

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

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

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

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

10

100

45

55

10

35

25

10

10

10

26

Программа должна вывести одно число — описанное в условии произведение. Пример выходных данных для приведённого выше примера входных данных: 2600.

Задание А.

Приведем одно из возможных решений задания А на языке С++:

\[\begin{array}{l} \#include <iostream>\\ using\; namespace\; std;\\ int\; main()\\ \{ \\ \quad int\; N;\\ \quad cin >> N; // \text{вводим размер массива N, не превышающий 10000}\\ \quad int\; a[10000]; // \text{создаем массив на 10000 элементов (максимальное возможное количество элементов по условию)}\\ \quad int\; max = -1; // \text{создаем переменную для максимума}\\ \\ \quad for\; (int\; i = 0; i < N; i++) // \text{вводим массив}\\ \quad \quad cin >> a[i];\\ \\ \quad for\; (int\; i = 0; i < N; i++) \\ \quad \quad for\; (int\; j = i + 5; j < N; j++) // \text{запускаем вложенный цикл}\\ \quad \quad \quad if\; (a[i] * a[j] > max) // \text{ищем максимальное произведение}\\ \quad \quad \quad \quad max = a[i] * a[j];\\ \\ \quad cout << max;\\ \quad return\; 0;\\ \} \end{array}\]

Задание Б.

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

Приведем пример программы на языке С++:

\[\begin{array}{l} \#include <iostream>\\ using\; namespace\; std;\\ int\; main()\\ \{ \\ \quad int\; N;\\ \quad cin >> N;\\ \quad int\; const\; b = 5;\\ \quad int\; buf[b];\\ \\ \quad int\; x,\; max = -1,\; max\_p = -1;\\ \\ \quad for\; (int\; i = 0; i < b; i++)\{\\ \quad \quad cin >> x;\\ \quad \quad buf[i \% b] = x;\\ \quad \}\\ \\ \quad for\; (int\; i = b; i < N; i++)\\ \quad \{\\ \quad \quad cin >> x;\\ \quad \quad if\; (buf[i \% b] > max)\\ \quad \quad \quad max = buf[i \% b];\\ \quad \quad if\; (x * max > max\_p)\\ \quad \quad \quad max\_p = x * max;\\ \quad \quad buf[i \% b] = x;\\ \quad \}\\ \\ \quad cout << max\_p;\\ \quad return\; 0;\\ \} \end{array}\]

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

Задание 2 #12278

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

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

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

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

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

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

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

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

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

10

100

45

55

10

35

25

10

10

10

26

Программа должна вывести одно число — описанное в условии произведение. Пример выходных данных для приведённого выше примера входных данных: 2600.

Задание А.

Приведем одно из возможных решений задания А на языке С++:

\[\begin{array}{l} \#include <iostream>\\ using\; namespace\; std;\\ int\; main()\\ \{ \\ \quad int\; N;\\ \quad cin >> N; // \text{вводим размер массива N, не превышающий 10000}\\ \quad int\; a[10000]; // \text{создаем массив на 10000 элементов (максимальное возможное количество элементов по условию)}\\ \quad int\; max = -1; // \text{создаем переменную для максимума}\\ \\ \quad for\; (int\; i = 0; i < N; i++) // \text{вводим массив}\\ \quad \quad cin >> a[i];\\ \\ \quad for\; (int\; i = 0; i < N; i++) \\ \quad \quad for\; (int\; j = i + 9; j < N; j++) // \text{запускаем вложенный цикл}\\ \quad \quad \quad if\; (a[i] * a[j] > max) // \text{ищем максимальное произведение}\\ \quad \quad \quad \quad max = a[i] * a[j];\\ \\ \quad cout << max;\\ \quad return\; 0;\\ \} \end{array}\]

Задание Б.

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

Приведем пример программы на языке С++:

\[\begin{array}{l} \#include <iostream>\\ using\; namespace\; std;\\ int\; main()\\ \{ \\ \quad int\; N;\\ \quad cin >> N;\\ \quad int\; const\; b = 9;\\ \quad int\; buf[b];\\ \\ \quad int\; x,\; max = -1,\; max\_p = -1;\\ \\ \quad for\; (int\; i = 0; i < b; i++)\{\\ \quad \quad cin >> x;\\ \quad \quad buf[i \% b] = x;\\ \quad \}\\ \\ \quad for\; (int\; i = b; i < N; i++)\\ \quad \{\\ \quad \quad cin >> x;\\ \quad \quad if\; (buf[i \% b] > max)\\ \quad \quad \quad max = buf[i \% b];\\ \quad \quad if\; (x * max > max\_p)\\ \quad \quad \quad max\_p = x * max;\\ \quad \quad buf[i \% b] = x;\\ \quad \}\\ \\ \quad cout << max\_p;\\ \quad return\; 0;\\ \} \end{array}\]

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

Задание 3 #12279

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

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

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

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

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

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

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

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

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

10

100

45

55

10

35

25

10

10

10

26

Программа должна вывести одно число — описанное в условии произведение. Пример выходных данных для приведённого выше примера входных данных: 5500.

Задание А.

Приведем одно из возможных решений задания А на языке С++:

\[\begin{array}{l} \#include <iostream>\\ using\; namespace\; std;\\ int\; main()\\ \{ \\ \quad int\; N;\\ \quad cin >> N; // \text{вводим размер массива N, не превышающий 10000}\\ \quad int\; a[10000]; // \text{создаем массив на 10000 элементов (максимальное возможное количество элементов по условию)}\\ \quad int\; max = -1; // \text{создаем переменную для максимума}\\ \\ \quad for\; (int\; i = 0; i < N; i++) // \text{вводим массив}\\ \quad \quad cin >> a[i];\\ \\ \quad for\; (int\; i = 0; i < N; i++) \\ \quad \quad for\; (int\; j = i + 2; j < N; j++) // \text{запускаем вложенный цикл}\\ \quad \quad \quad if\; (a[i] * a[j] > max) // \text{ищем максимальное произведение}\\ \quad \quad \quad \quad max = a[i] * a[j];\\ \\ \quad cout << max;\\ \quad return\; 0;\\ \} \end{array}\]

Задание Б.

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

Приведем пример программы на языке С++:

\[\begin{array}{l} \#include <iostream>\\ using\; namespace\; std;\\ int\; main()\\ \{ \\ \quad int\; N;\\ \quad cin >> N;\\ \quad int\; const\; b = 2;\\ \quad int\; buf[b];\\ \\ \quad int\; x,\; max = -1,\; max\_p = -1;\\ \\ \quad for\; (int\; i = 0; i < b; i++)\{\\ \quad \quad cin >> x;\\ \quad \quad buf[i \% b] = x;\\ \quad \}\\ \\ \quad for\; (int\; i = b; i < N; i++)\\ \quad \{\\ \quad \quad cin >> x;\\ \quad \quad if\; (buf[i \% b] > max)\\ \quad \quad \quad max = buf[i \% b];\\ \quad \quad if\; (x * max > max\_p)\\ \quad \quad \quad max\_p = x * max;\\ \quad \quad buf[i \% b] = x;\\ \quad \}\\ \\ \quad cout << max\_p;\\ \quad return\; 0;\\ \} \end{array}\]

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

Задание 4 #12280

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

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

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

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

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

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

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

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

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

10

100

45

55

10

35

25

10

10

10

26

Программа должна вывести одно число — описанное в условии произведение. Пример выходных данных для приведённого выше примера входных данных: 55.

Задание А.

Приведем одно из возможных решений задания А на языке С++:

\[\begin{array}{l} \#include <iostream>\\ using\; namespace\; std;\\ int\; main()\\ \{ \\ \quad int\; N;\\ \quad cin >> N; // \text{вводим размер массива N, не превышающий 10000}\\ \quad int\; a[10000]; // \text{создаем массив на 10000 элементов (максимальное возможное количество элементов по условию)}\\ \quad int\; min = 2001; // \text{создаем переменную для минимума}\\ \\ \quad for\; (int\; i = 0; i < N; i++) // \text{вводим массив}\\ \quad \quad cin >> a[i];\\ \\ \quad for\; (int\; i = 0; i < N; i++) \\ \quad \quad for\; (int\; j = i + 7; j < N; j++) // \text{запускаем вложенный цикл}\\ \quad \quad \quad if\; (a[i] + a[j] < min) // \text{ищем минимальную сумму}\\ \quad \quad \quad \quad min = a[i] + a[j];\\ \\ \quad cout << min;\\ \quad return\; 0;\\ \} \end{array}\]

Задание Б.

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

Приведем пример программы на языке С++:

\[\begin{array}{l} \#include <iostream>\\ using\; namespace\; std;\\ int\; main()\\ \{ \\ \quad int\; N;\\ \quad cin >> N;\\ \quad int\; const\; b = 7;\\ \quad int\; buf[b];\\ \\ \quad int\; x,\; min = 1001,\; min\_s = 2001;\\ \\ \quad for\; (int\; i = 0; i < b; i++)\{\\ \quad \quad cin >> x;\\ \quad \quad buf[i \% b] = x;\\ \quad \}\\ \\ \quad for\; (int\; i = b; i < N; i++)\\ \quad \{\\ \quad \quad cin >> x;\\ \quad \quad if\; (buf[i \% b] < min)\\ \quad \quad \quad min = buf[i \% b];\\ \quad \quad if\; (x + min < min\_s)\\ \quad \quad \quad min\_s = x + min;\\ \quad \quad buf[i \% b] = x;\\ \quad \}\\ \\ \quad cout << min\_s;\\ \quad return\; 0;\\ \} \end{array}\]

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

Задание 5 #12281

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

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

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

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

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

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

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

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

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

10

100

45

55

10

35

25

10

10

10

26

Программа должна вывести одно число — описанное в условии произведение. Пример выходных данных для приведённого выше примера входных данных: 20.

Задание А.

Приведем одно из возможных решений задания А на языке С++:

\[\begin{array}{l} \#include <iostream>\\ using\; namespace\; std;\\ int\; main()\\ \{ \\ \quad int\; N;\\ \quad cin >> N; // \text{вводим размер массива N, не превышающий 10000}\\ \quad int\; a[10000]; // \text{создаем массив на 10000 элементов (максимальное возможное количество элементов по условию)}\\ \quad int\; min = 2001; // \text{создаем переменную для минимума}\\ \\ \quad for\; (int\; i = 0; i < N; i++) // \text{вводим массив}\\ \quad \quad cin >> a[i];\\ \\ \quad for\; (int\; i = 0; i < N; i++) \\ \quad \quad for\; (int\; j = i + 3; j < N; j++) // \text{запускаем вложенный цикл}\\ \quad \quad \quad if\; (a[i] + a[j] < min) // \text{ищем минимальную сумму}\\ \quad \quad \quad \quad min = a[i] + a[j];\\ \\ \quad cout << min;\\ \quad return\; 0;\\ \} \end{array}\]

Задание Б.

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

Приведем пример программы на языке С++:

\[\begin{array}{l} \#include <iostream>\\ using\; namespace\; std;\\ int\; main()\\ \{ \\ \quad int\; N;\\ \quad cin >> N;\\ \quad int\; const\; b = 3;\\ \quad int\; buf[b];\\ \\ \quad int\; x,\; min = 1001,\; min\_s = 2001;\\ \\ \quad for\; (int\; i = 0; i < b; i++)\{\\ \quad \quad cin >> x;\\ \quad \quad buf[i \% b] = x;\\ \quad \}\\ \\ \quad for\; (int\; i = b; i < N; i++)\\ \quad \{\\ \quad \quad cin >> x;\\ \quad \quad if\; (buf[i \% b] < min)\\ \quad \quad \quad min = buf[i \% b];\\ \quad \quad if\; (x + min < min\_s)\\ \quad \quad \quad min\_s = x + min;\\ \quad \quad buf[i \% b] = x;\\ \quad \}\\ \\ \quad cout << min\_s;\\ \quad return\; 0;\\ \} \end{array}\]

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

Задание 6 #12282

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

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

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

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

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

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

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

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

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

10

100

45

55

10

35

25

10

10

10

26

Программа должна вывести одно число — описанное в условии произведение. Пример выходных данных для приведённого выше примера входных данных: 71.

Задание А.

Приведем одно из возможных решений задания А на языке С++:

\[\begin{array}{l} \#include <iostream>\\ using\; namespace\; std;\\ int\; main()\\ \{ \\ \quad int\; N;\\ \quad cin >> N; // \text{вводим размер массива N, не превышающий 10000}\\ \quad int\; a[10000]; // \text{создаем массив на 10000 элементов (максимальное возможное количество элементов по условию)}\\ \quad int\; min = 2001; // \text{создаем переменную для минимума}\\ \\ \quad for\; (int\; i = 0; i < N; i++) // \text{вводим массив}\\ \quad \quad cin >> a[i];\\ \\ \quad for\; (int\; i = 0; i < N; i++) \\ \quad \quad for\; (int\; j = i + 8; j < N; j++) // \text{запускаем вложенный цикл}\\ \quad \quad \quad if\; (a[i] + a[j] < min) // \text{ищем минимальную сумму}\\ \quad \quad \quad \quad min = a[i] + a[j];\\ \\ \quad cout << min;\\ \quad return\; 0;\\ \} \end{array}\]

Задание Б.

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

Приведем пример программы на языке С++:

\[\begin{array}{l} \#include <iostream>\\ using\; namespace\; std;\\ int\; main()\\ \{ \\ \quad int\; N;\\ \quad cin >> N;\\ \quad int\; const\; b = 8;\\ \quad int\; buf[b];\\ \\ \quad int\; x,\; min = 1001,\; min\_s = 2001;\\ \\ \quad for\; (int\; i = 0; i < b; i++)\{\\ \quad \quad cin >> x;\\ \quad \quad buf[i \% b] = x;\\ \quad \}\\ \\ \quad for\; (int\; i = b; i < N; i++)\\ \quad \{\\ \quad \quad cin >> x;\\ \quad \quad if\; (buf[i \% b] < min)\\ \quad \quad \quad min = buf[i \% b];\\ \quad \quad if\; (x + min < min\_s)\\ \quad \quad \quad min\_s = x + min;\\ \quad \quad buf[i \% b] = x;\\ \quad \}\\ \\ \quad cout << min\_s;\\ \quad return\; 0;\\ \} \end{array}\]

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

Задание 7 #12283

Муравьед не знает, что такое среднее арифметическое, но ему срочно необходимо найти в заданной последовательности неотрицательных чисел минимальное среднее арифметическое двух ее элементов, номера которых различаются не менее, чем на 6. Известно, что значение каждого элемента последовательности не превышает 1000. Количество элементов последовательности не превышает 10000. Напишите такую программу для Муравьеда, чтобы он смог справиться со своей задачей.

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

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

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

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

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

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

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

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

10

100

45

55

10

35

25

10

10

10

26

Программа должна вывести одно число — описанное в условии среднее арифметическое. Пример выходных данных для приведённого выше примера входных данных: 18.

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

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

Задание А.

Приведем одно из возможных решений задания А на языке С++:

\[\begin{array}{l} \#include <iostream>\\ using\; namespace\; std;\\ int\; main()\\ \{ \\ \quad int\; N;\\ \quad cin >> N; // \text{вводим размер массива N, не превышающий 10000}\\ \quad int\; a[10000]; // \text{создаем массив на 10000 элементов (максимальное возможное количество элементов по условию)}\\ \quad float\; min = 2001; // \text{создаем переменную для минимума}\\ \\ \quad for\; (int\; i = 0; i < N; i++) // \text{вводим массив}\\ \quad \quad cin >> a[i];\\ \\ \quad for\; (int\; i = 0; i < N; i++) \\ \quad \quad for\; (int\; j = i + 6; j < N; j++) // \text{запускаем вложенный цикл}\\ \quad \quad \quad if\; (a[i] + a[j] < min) // \text{ищем минимальную сумму}\\ \quad \quad \quad \quad min = a[i] + a[j];\\ \\ \quad cout << min/2.0;\\ \quad return\; 0;\\ \} \end{array}\]

Задание Б.

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

Приведем пример программы на языке С++:

\[\begin{array}{l} \#include <iostream>\\ using\; namespace\; std;\\ int\; main()\\ \{ \\ \quad int\; N;\\ \quad cin >> N;\\ \quad int\; const\; b = 6;\\ \quad int\; buf[b];\\ \\ \quad float\; x,\; min = 1001,\; min\_s = 2001;\\ \\ \quad for\; (int\; i = 0; i < b; i++)\{\\ \quad \quad cin >> x;\\ \quad \quad buf[i \% b] = x;\\ \quad \}\\ \\ \quad for\; (int\; i = b; i < N; i++)\\ \quad \{\\ \quad \quad cin >> x;\\ \quad \quad if\; (buf[i \% b] < min)\\ \quad \quad \quad min = buf[i \% b];\\ \quad \quad if\; (x + min < min\_s)\\ \quad \quad \quad min\_s = x + min;\\ \quad \quad buf[i \% b] = x;\\ \quad \}\\ \\ \quad cout << min\_s/2.0;\\ \quad return\; 0;\\ \} \end{array}\]

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