Язык программирования

Примеры

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n, m;
	vector < vector<int> > up1(n, vector <int>(m));
	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		vector <int> L(m + 1, 1), R(m + 1, m);
		stack <int> q;
		for (int j = 1; j <= m; j++)
		{
			while (!q.empty() && up1[i][j] < up1[i][q.top()])
			{
				R[q.top()] = j - 1;
				q.pop();
			}
			q.push(j);
		}
		while (!q.empty())
			q.pop();
		for (int j = m; j >= 1; j--)
		{
			while (!q.empty() && up1[i][j] < up1[i][q.top()])
			{
				L[q.top()] = j + 1;
				q.pop();
			}
			q.push(j);
		}
		for (int j = 1; j <= m; j++)
			ans = max(ans, up1[i][j] * (R[j] - L[j] + 1));
	}
	cout << ans;
	return 0;
}

Примеры

Пример

Примеры

На спутнике «Восход» установлен прибор, предназначенный для измерения солнечной активности. Каждую минуту прибор передаёт по каналу связи натуральное число – количество энергии солнечного излучения, полученной за последнюю минуту, измеренное в условных единицах. Временем, в течение которого происходит передача, можно пренебречь. Необходимо найти в заданной серии количество пар таких показаний прибора, произведение которых кратно 6 и между моментами передачи которых прошло не менее трех минут. Количество энергии, получаемое прибором за минуту, не превышает 1000 условных единиц. Общее количество показаний прибора в серии не превышает 10 000.

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

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

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

Дан набор из N натуральных чисел. Необходимо определить количество пар элементов (ai, aj) этого набора, в которых \(1 < i < j < N\) и сумма элементов кратна 12. 

Напишите эффективную по времени и памяти программу для решения этой задачи. 

Входные данные
В первой строке входных данных задаётся количество чисел N (\(1 < N <= 10000\)). В каждой из последующих N строк записано одно натуральное число, не превышающее 1000.

Выходные данные
Выведите ответ на задачу

Дан набор из N натуральных чисел. Необходимо определить количество пар элементов (ai, aj) этого набора, в которых 1 <= i < j <= N и произведение элементов кратно 6. 

Напишите эффективную по времени и памяти программу для решения этой задачи. 

Входные данные
В первой строке входных данных задаётся количество чисел N (\(1 < N <= 100000\)). В каждой из последующих N строк записано одно натуральное число, не превышающее 1000.

Выходные данные
Выведите ответ на задачу.

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

Напишите эффективную программу, решающую поставленную задачу.

Входные данные
На вход программе в первой строке подаётся количество троек N (\(1 <= N <= 100000\)). Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000. 

Выходные данные
Выведите ответ на задачу

Имеется набор данных, состоящий из пар положительных целых чисел. Для каждой пары чисел находится значение А – наибольший общий делитель. 

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

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

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

Входные данные
На вход программе в первой строке подаётся количество пар N (\(1 <= N <= 100000\)). Каждая из следующих N строк содержит два натуральных числа, не превышающих 1000.