https://www.thehuxley.com/problem/604
Esse é um problema que pode ser traiçoeiro de interpretar. Em uma primeira análise, você poderia tentar resolver usando o seu conhecimento de arcos.
Porém, veja que o problema pede para que cada azeitona fique em um pedaço da pizza. Ou seja, a azeitona não pode estar no local onde você irá cortar.
Além disso, veja também que C é múltiplo de N, ou seja, sempre as distâncias entre as azeitonas serão números inteiros.
No exemplo, ele mostra a pizza com C=12, N=3 e azeitonas nas posições 2, 8 e 11.
Neste caso, seria possível fazer um corte em 1, outro em 5, e outro em 9 de tal forma que a distância entre eles seja 4 e que cada pedaço tenha ficado com uma azeitona.
Mas aqui é que a gente começa a se perder, veja que o problema não pede para calcularmos exatamente onde é o ponto de corte. Ele só nos pede para dizer se é possível ou não.
No exemplo dado, o fato de ter ficado muito fácil de achar esses pontos, pode ter levado muita gente a tentar achar o local exato do corte.
Mas ainda nesse mesmo exemplo, se resolvermos fazer o corte em qualquer lugar entre a posição 0 e a posição 1, o próximo corte seria a posição do primeiro corte mais 4. Assim, o segundo corte cairia entre a posição 4 e 5 e o terceiro entre as posições 8 e 9.
Ainda assim é possível ver que cada fatia continua com uma azeitona e que respeitamos a distância de 4 entre elas.
Outra vantagem de pensar assim é que não teremos que nos preocupar em cortar a azeitona no meio, pois elas estarão sempre nas posições inteiras.
Veja o segundo exemplo, com a pizza da direita da imagem. Nesse caso, as azeitonas estão nas posições 1, 5 e 8. Essa pizza seria possível?
Vou deixar você pensar um pouco
...
...
...
...
...
...
...
...
...
...
...
Veja que se usarmos a estratégia, poderiamos cortar entre 2 e 3, entre 6 e 7 e entre 10 e 11.
E agora, dada uma configuração, como saber se é possível?
Uma primeira ideia seria olhar para os dois lados e contar se existem azeitonas à esquerda e a direita, por exemplo, na segunda pizza, existem 4 espacos vazios à direita, quadro à esquerda da azeitona 1, mas se olharmos para a azeitona 5, embora existam 4 vazios à esquerda, só existe 3 vazios à direita.
Parece que essa ideia não deu certo.
E se tentarmos todos os possíveis lugares à esquerda e à direita?
Nesse caso, se fizermos isso, para cada posição da pizza, iremos C/N para um lado e C/N para o outro, ou seja C * 2(C/N), ou C^2 / N. Considerando que C pode ser 10^5 e n pode ser tão pequeno quanto 3, essa nossa estratégia nos daria 10^10. Provavelmente superior ao tempo que teríamos para dar a resposta.
Precisamos de algo mais eficiente.
E se resolvermos em uma única passada na pizza O(C) ?
A gente só está indo para um lado e para o outro da pizza, porque precisamos saber se existem azeitonas. Então se a gente já soubesse quantas são as azeitonas para cada lado, não precisaríamos ir para um lado e para o outro.
Então fiz o seguinte, criei um array que guarda quantas azeitonas existem a partir da posição 0.
Por exemplo, para a primeira pizza, o array seria:
[0][0][1][1][1][1][1][1][2][2][2][3]
Cada posição i do array guarda quantas azeitonas existem antes do segmento entre i e i+1.
Por exemplo, a posição 8, indica que existem 2 azeitonas antes do segmento 8 a 9.
Com isso, para saber, por exemplo quantas azeitonas existem entre os segmentos 0 a 1, e o 4 a 5, basta subtrair array[4] - array[0], o que nesse caso dá 1. Vamos chamar esse array de azeitonas_acumuladas.
Em outras palavras
azeitonas[] <- ler do teclado
azeitonas_acumuladas[] <- preencher a partir do array de azeitonas ( O(C) )
deslocamento <- C / N
Para cada posicao pos do array até C
i <- pos
para k de 1 até N
lado_direito <- i + deslocamento
se (existe apenas uma azeitona entre i e o lado_direito)
i <- i + length
continua
senão
tenta a próxima pos
se chegar no final, você encontrou um segmento em que é possível fazer o corte, mantendo a distância e a propriedade de uma azeitona em cada fatia.