Solução Doces de Dia das Bruxas

0 Flares Facebook 0 0 Flares ×

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.

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