28a Olimpíada Brasileira de Informática
Subsequência
Você foi contratado pela Agência Extra-Espacial Brasileira, que procura indícios de vida extra-terrestre. Um dos telescópios da Agência, para o espectro ultravioleta, gera uma sequência de valores inteiros positivos que devem ser analisados continuamente. Dadas duas sequências SA e SB, sua primeira missão é determinar se SB é uma subsequência de SA. Uma subsequência de uma dada sequência S é um conjunto de elementos de S que não são necessariamente adjacentes mas que mantêm a mesma ordem em que aparecem em S. Por exemplo, [2], [1,4], [1,2,4] e [1,2,3,4] são subsequências de [1,2,3,4], mas [4,3], [3,4,1] e [1,3,5] não são.Entrada
A primeira linha contém dois inteiros A e B, o número de elementos das sequências. A segunda linha contém A inteiros Xi, os números da sequência SA. A seguir a entrada contém B inteiros Yi, os números da sequência SB.Saída
Seu programa deve produzir uma única linha, contendo um único caractere, que deve ser a letra maiúscula `S' se SB é uma subsequência da SA ou a letra maiúscula `N' caso contrário.Restrições
- 1 ≤ A ≤ 105
- 1 ≤ B ≤ A
- -109 ≤ Xi ≤ 109 para 1 ≤ i ≤ A
- -109 ≤ Yi ≤ 109 para 1 ≤ i ≤ B
Informações sobre a pontuação
- A tarefa vale 100 pontos.
- Para um conjunto de casos de testes valendo 11 pontos, A = B = 2.
- Para um conjunto de casos de testes valendo outros 33 pontos, os números aparecem no máximo uma vez em cada sequência, A ≤ 100, 1 ≤ Xi ≤ 100 e 1 ≤ Yi ≤ 100.
- Para um conjunto de casos de testes valendo outros 56 pontos, nenhuma restrição adicional.
Exemplos
Entrada
5 3 1 2 3 4 5 2 3 5 |
Saída
S |
Entrada
5 4 8 17 8 21 23 8 8 21 22 |
Saída
N |