Avançado Informática - Semana 12

0 Flares Facebook 0 0 Flares ×

Doces do Dia das Bruxas

 

Todos os anos há o mesmo problema no Halloween: Cada vizinho só está disposto a dar certo número total de doces neste dia, não importa quantas crianças peçam, por isso pode acontecer que uma criança fique sem nada, se for tarde demais. Para evitar conflitos, as crianças decidiram que vão colocar todos os doces juntos e depois dividi-los igualmente entre si. A partir da experiência do Halloween do ano passado, elas sabem quantos doces recebem de cada vizinho. Visto que elas se preocupam mais com a justiça do que o número de doces que recebem, elas querem selecionar um subconjunto de vizinhos para visitar, para que na partilha cada criança receba o mesmo número de doces. Elas não vão ficar satisfeitas se sobrar doces que não possam ser divididos.

Seu trabalho é ajudar as crianças e apresentar uma solução.

Entrada

A entrada contém vários casos de teste.

A primeira linha de cada caso de teste contém dois inteiros c e n (1 ≤ c ≤ n ≤ 100000), sendo o número de crianças e o número de vizinhos, respectivamente. A próxima linha contém n inteiros separados por espaço a1,...,an (1 ≤ ai ≤ 100000), onde ai representa o número de doces que as crianças recebem se visitarem vizinho i.

O último caso de teste é seguido por dois zeros.

Saída

Para cada caso de teste, imprima uma linha com os índices dos vizinhos que as crianças devem selecionar (aqui, o índice i corresponde ao vizinho i que dá um total de doces ai). Se não houver solução, onde cada criança recebe pelo menos um doce, imprima "no sweets". Observe que, se existir várias soluções onde cada criança recebe pelo menos um doce, você pode imprimir qualquer uma delas.

Exemplo de Entrada Exemplo de Saída
4 5

1 2 3 7 5

3 6

7 11 2 5 13 17

0 0

3 5

2 3 4

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: