Задача на поиск по двумерному массиву + последовательности

[ershowwk]

Решал задачи
1) Дан массив двумерный n*m. Все строки имеют возрастающую последовательность. Существует как минимум одно число А, которое есть в каждой строке. Его вывести надо.

Решил следующим образом

int main()
{
	int n, m;
	cin >> n >> m;

	int **a = new int*[n]; 
	for (int count = 0; count < n; count++)
		a[count] = new int[m];

	int counter = 1, memory = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)	cin >> a[i][j];

	for (int j = 0; j < m; j++)
	{
		for (int i = 1; i < n; i++)
		{
			int l = 0;
			int r = m - 1;
			int mid = 0;
			while (l < r)
			{	mid = (l + r) / 2;
				if (a[i][mid] == a[0][j])
				{
					l = r = mid;
					memory = a[0][j];
				}
				else if (a[i][mid] < a[0][j]) l = mid + 1;
				
				else r = mid;
			}
			if (a[i][r] == a[0][j])	counter++;
			else i = n;
		}
		if (counter == n)
		{
			memory = a[0][j];
			j = m;
		}
	}
	cout << memory << endl;
}

сложность C*n*m*log(m) (C - const)
как сделать бы количество сравнений < C*m*n? Если просто брать элемент первой строки и по первым элементам первой строки сравнивать, брать второй и сравнивать с каждым вторым, это будет <Cmn?

И вторая проблема.
Нужно вывести в задаче для данных натуральных n,k (n>=k) все возрастающие элементы из k элементов в лексикографическом порядке.
Решил следующим образом.

int main()
{
	int n, k;
	cin >> n >> k;
	int *a = new int[k];
	for (int i = 0; i < k; i++) a[i] = i+1;
	bool b = true;
	while (b) {

		for (int i = 0; i < k; i++) cout << a[i] << ' ';
		cout << endl;
		int j = k - 1;
		while ((a[j] > (n - k + j)) && b)
			if (j < 0) b = false;
			else j--;
		if (j < 0) b = false;
		else {
			a[j]++;
			for (int i = j + 1; i < k; i++) a[i] =a[i-1]+1;
		}
	}

}

нашел в инете формулу, типа что увеличивать a[j] можно если a[j]=<n-k+j. Но не принимают у меня эту формулу. Говорят неверная. Решал строками - нельзя.

Строками, библиотеками и прочим пользоваться запрещено. Все ручками и в числах.
Буду рад любой идее.

[digitalis]

Все строки имеют возрастающую последовательность.

Строками, библиотеками и прочим пользоваться запрещено.

Это как? Сварить суп, водой и кастрюлей пользоваться запрещено ?

[ershowwk]

Сообщение от digitalis

Это как? Сварить суп, водой и кастрюлей пользоваться запрещено ?

ну да, препод говорит прогайте без всяких доп функций, руками.