Solução Doces de Dia das Bruxas

Solução por Rogério Júnior

Para ver o problema original, clique aqui.

Seja $$s_k = (\sum\limits_{i=1}^k a_i) \ mod \ c$$. O enunciado nos diz que $$n\leq c$$.

Suponha $$n>c$$. Como só há $$c$$ valores possíveis para um $$s_i$$ qualquer $$(0, 1, 2, 3, …, c-1)$$ mas há $$n$$ vizinhos e cada um deles com o seu valor de $$s_i$$, pelo Princípio da Casa dos Pombos, há pelo menos dois vizinhos $$i$$ e $$j$$ ($$i < j$$ em que $$s_i=s_j$$. Logo, $$s_j-s_i \equiv 0 \ mod \ c \Rightarrow \sum\limits_{k=i+1}^j a_k \equiv 0 \ mod \ c$$. Logo, os índices entre $$i+1$$ e $$j$$ são solução.

Suponha agora $$n=c$$. Se houver pelo menos dois vizinhos com mesmo $$s_i$$, aplicamos a mesma solução acima. Se não existirem tais vizinhos, então todos eles têm valores distintos. Mas só existem $$c$$ possíveis valores e $$n=c$$ vizinhos, logo, todos os possíveis valores aparecem, logo, existe $$i$$, tal que $$s_i=0\Rightarrow\sum\limits_{i=1}^k a_i \equiv 0 \ mod \ c$$, logo os índices de $$1$$ a $$i$$ são solução.

Acabamos de provar que sempre conseguimos encontrar uma resposta apenas com uma sequência contígua de índices, o que facilita muito o problema. Para cada caso, vamos criar um vetor $$s$$ em que $$s[i]=s_i \forall 1 \leq i \leq n$$. Basta salvarmos o valor de cada $$a_i$$ em $$s[i]$$ e depois percorrermos o vetor acumulando, em cada casa, o valor da casa anterior (que já teria acumulado o de todas as outras anteriores), e guardarmos módulo $$c$$. Feito isso, vamos percorrer o vetor, guardando todos os valores que já apareceram em um vetor $$resto$$, de modo que, quando estamos analisando a casa $$j$$ do vetor $$s$$, $$resto[i]=p \Rightarrow p<j e s[p]=i$$. Logo, se $$resto[s[j]]=true$$, então encontramos vizinhos com mesmo $$s_i$$ e basta imprimirmos os índices entre eles. Caso contrário (não existe $$p$$, o que podemos representar com $$p=-1$$, marco $$resto[s[j]]=j$$ e continuo a percorrer. Note que, se marcarmos que $$resto[0]=0$$, então, mesmo quando $$n=c$$ e todos os $$s_i$$ forem distintos, o programa encontrará solução pois, ao chegar em $$k$$, tal que $$s_k=0$$, ele verá que $$s_0=s_k=0$$, e imprimirá os índices de $$1$$ a $$k$$. Segue o código para melhor entendimento.