Solução Informática Iniciante - Semana 50 - Problema 1

Solução por Lúcio Cardoso

Vamos descobrir o primeiro capítulo que não foi lido totalmente, ou seja, o capítulo que contém a página $k$ . Se o capítulo $i$ contém a página $k$ , então $l_i \leq k$ e $k \leq r_i$ , ou seja, $k$ está entre $l_i$ e $r_i$ . Assim, para encontrar o primeiro capítulo não lido, basta testar a condição acima em cada um dos capítulos e quando for verdadeira, guardamos o índice do capítulo em uma variável $ind$ . Assim, a resposta será $N-ind+1$ (quantidade de capítulos desde $ind$ até $N$ ). A complexidade será então $O(n)$ .

Confira o código abaixo para melhor entendimento:

	// Noic - Iniciante - Semana 50 - Problema 1
	// O(n)

	#include <bits/stdc++.h>

	using namespace std;

	const int maxn = 110;

	int l[maxn], r[maxn];

	int main(void)
	{
	int n, k;
	cin >> n;

	for (int i = 1; i <= n; i++)
	cin >> l[i] >> r[i];

	cin >> k;

	int ind; // capítulo que contém k
	for (int i = 1; i <= n; i++)
	if (l[i] <= k && k <= r[i])
	ind = i;

	cout << n-ind+1 << "\n";
	}

view raw

noic-iniciante-s50-p1.cpp

hosted with ❤ by GitHub