Por OBI-Olimpíada Brasileira de Informatica Angola
Uma fábrica instalou um elevador composto de duas cabines ligadas por uma roldana, como na figura. Quando uma cabine sobe, a outra desce. No primeiro andar da fábrica existem algumas caixas de pesos diversos e precisamos levar todas as caixas para o segundo andar, usando o elevador. Apenas uma caixa pode ser colocada por vez dentro de uma cabine. Além disso, existe uma restrição de segurança importante: durante uma viagem do elevador, a diferença de peso entre as cabines pode ser no máximo de 8 unidades. De forma mais rigorosa, P − Q ≤ 8, onde P é o peso da cabine mais pesada e Q, o peso da cabine mais leve. O gerente da fábrica não está preocupado com o número de viagens que o elevador vai fazer. Ele apenas precisa saber se é possível ou não levar todas as caixas para o segundo andar. No exemplo da figura, podemos levar todas as três caixas usando a seguinte sequência de seis viagens do elevador:
Dados os pesos de N caixas no primeiro andar, seu programa deve dizer se é possível ou não levar todas as N caixas para o segundo andar.
A primeira linha da entrada contém um inteiro N (1 ≤ N ≤ 104) indicando o número de caixas. A segunda linha da entrada contém N inteiros representando os pesos das caixas. O peso das caixas está entre 1 e 105 , inclusive.
Imprima uma linha na saída. A linha deve conter o caracter S caso seja possível, ou N caso não seja possível levar todas as caixas até o segundo andar da fábrica.
Exemplos de Entrada | Exemplos de Saída |
3 15 4 10 |
S |
8 25 2 6 15 40 35 35 20 |
N |
4 14 10 23 20 |
N |
1 8 |
S |