Solução Informática - Nível Iniciante - Semana 34

Solução escrita por Estela Baron

Conhecimento prévio necessário:

• Começando do zero
• Estruturas Condicionais
• Loops
• Vector
• Set

Primeiramente, devemos declarar as nossas variáveis como inteiros - $int \; N, \; X;$- e atribuir o valor da entrada a estas: $cin >> N >> X$ (para guardar o valor fornecido e para podermos utilizá-las). Precisamos também guardar todos os valores de $A_i$. Para isso, vamos declarar um vector $a$ com $N$ posições (indexadas de $0$ a $N-1$): $vector<int> a (N);$. Depois, por meio de um $for()$, vamos ler todos os $A_i$, atribuir ao valor de $a[i]$ e colocar em um $set$ - o qual vamos declarar como $set<int> s$. Com o $set$, conseguimos inserir um valor e também verificar se ele foi inserido.

Agora, a estratégia é: para cada $A_i$, vamos verificar se o valor $A_j$ $= A_i - X$ está em nosso set. Para isso, vamos percorrer os índices de $0$ até $N-1$ de $a$ por meio do $for()$ e verificar se $s.find(A_j)\; != s.end()$. Se for, quer dizer que achamos uma resposta e que é possível (podemos indicar isso por meio de uma variável, por exemplo um $bool$) , caso contrário, continuamos percorrendo as outras posições. No fim, basta verificar se há ou não uma resposta e imprimir "Sim" ou "Não".

A complexidade desse código é $O(N*log N)$.

Recomendamos que você tente implementar o problema antes de ver o código.Veja a implementação nesse link.