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.