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 data-recalc-dims=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.


#include <cstdio>
#include <cstring>
#define MAXN 100100
int c, n, s[MAXN], resto[MAXN];
int main(){
// para cada caso
while(scanf("%d %d", &c, &n)and n and c){
// defino todos os valores de resto para -1, ou seja, não encontrados
memset(resto, -1, sizeof resto);
// caso especial de n=c, e todos os s_i serem distintos
resto[0]=0;
// leio a entrada e salvo em s
for(int i=1; i<=n; i++) scanf("%d", &s[i]);
// para cada vizinho
for(int i=1; i<=n; i++){
// descubro o valor real de seu s, acumulando o s anterior
s[i]+=s[i-1];
// e guardando módulo c
s[i]%=c;
// se esse resto já foi encontrado no vetor, na posição k
if(resto[s[i]]>=0){
// imprimo os índices de k+1 a i
// com o cuidado de não imprimir um espaço a mais no final
printf("%d", resto[s[i]]+1);
for(int j=resto[s[i]]+2; j<=i; j++) printf(" %d", j);
printf("\n");
// e paro de percorrer o vetor
break;
}
// caso contrário, guardo o novo resto encontrado
resto[s[i]]=i;
}
}
return 0;
}

view raw

doces.cpp

hosted with ❤ by GitHub