Pizza

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.