uCoder | 1229 | Nível: 5 | Tempo Limite: 2
Pizza do Vô Pepe
Adaptado por Erich Rodrigues
Competição: SBC - ACM/ICPC - Maratona de Programação de 2014
Vovô Pepe é famoso por suas pizzas. Elas são deliciosas, e têm o formato de um círculo perfeito. Vovô preparou uma pizza especial para o jantar de hoje à noite, e colocou um certo número de azeitonas distribuídas aleatoriamente, mas colocadas exatamente na borda da pizza.
Sua tarefa é determinar, conhecendo a circunferência da pizza, a quantidade de azeitonas e a posição de cada azeitona, se é possível dividir a pizza em setores circulares de mesmo tamanho, de tal forma que cada pedaço de pizza contenha exatamente uma azeitona.
A figura abaixo mostra (a) uma pizza de circunferência 12 com 3 azeitonas e uma possível divisão em pedaços iguais; e (b) uma pizza de circunferência 12 com 4 azeitonas que não pode ser dividida em pedaços iguais como descrito acima. Apesar de deliciosas, as azeitonas são muito pequenas, e suas dimensões podem ser desconsideradas no cálculo da divisão.
Entrada
A primeira linha contém dois inteiros C (3 ≤ C ≤ 105 ) e N (3 ≤ N ≤ 104 , N ≤ C) representando respectivamente a circunferência da pizza e o número de azeitonas. O inteiro C é múltiplo de N . A segunda linha contém N inteiros distintos Xi (0 ≤ X1 < X2 < . . . < XN < C), em ordem crescente, descrevendo as posições das azeitonas, dadas pelo comprimento do arco circular no sentido horário, a partir de um ponto fixo da circunferência.
Saída
Seu programa deve produzir apenas uma linha, com apenas uma letra, que deve ser S se é possível dividir a pizza como descrito acima, ou N caso contrário.
| Exemplo de Entrada | Exemplo de Saída |
|---|---|
|
12 4 |
N |
|
12 3 |
S |