OBI 2018 – Fase 3 – Programação Nível Junior
Para conferir a prova na íntegra, clique aqui.
Troca
Comentário escrito por Estela Baron
Conhecimento prévio necessário:
A primeira ideia que temos é guardar dois vetores – um para os valores de cima e outro para os outros de baixo – e, para cada $$L R$$, percorremos o intervalo invertendo os valores. No entanto, no pior caso, temos $$10^5$$ posições para percorrer $$10^5$$ vezes – com esse caso, o nosso código estouraria o limite de tempo (complexidade).
Como vimos que a ideia anterior não funciona, vamos tentar encontrar uma outra forma mais eficiente. Observe que o problema só quer saber quais são os valores na face de cima. Além do mais, se uma carta é virada uma quantidade par de vezes no total, quer dizer que o valor mostrado na parte de cima não vai mudar. Agora, se essa carta é virada uma quantidade ímpar no total, o valor na parte de cima tem que ser trocado. Com isso, concluímos que só precisamos saber a quantidade total que cada carta vai ser trocada.
Não podemos simplesmente adicionar $$+1$$ em todas as posições do intervalo $$[L,R]$$, pois daria o mesmo problema da ideia inicial. Para resolver esse impasse, vamos utilizar a técnica de soma de prefixo – o novo valor atual é igual ao valor anterior mais o atual. Mais especificamente, vamos adicionar $$+1$$ na posição $$L$$ e $$-1$$ na posição $$R + 1$$, pois, com a soma acumulada, adicionamos $$+1$$ em todas as posições de $$L$$ até o final e subtraímos $$1$$ de todas as posições a partir de $$R+1$$ – o que zera $$1 – 1 = 0$$ todas as posições fora do intervalo.
Com isso, para cada um dos $$T$$ intervalos, adicionamos $$+1$$ na posição $$L$$ e $$-1$$ na posição $$R+1$$. Depois disso, percorremos todas as posições e mudamos o valor delas para o valor da posição anterior mais o valor atual.
A partir disso, temos a quantidade exata de vezes que cada carta foi virada. Veja que a complexidade fica boa, pois, em cada operação de $$T$$, temos $$O(1)$$. E só percorremos as $$N$$ posições uma vez, no fim.
Por fim, para definir qual é o valor da face de cima de cada carta, é necessário ver a paridade da quantidade de vezes que a carta foi virada, se for par, o valor é o mesmo do estado original, caso contrário, é o outro.
Clique aqui para conferir o código
Pulo do Gato (PJ)
Comentário escrito por Estela Baron
Conhecimento prévio necessário:
Podemos pensar a linha como um vetor, em que cada posição representa se há uma lajota ou não. Além disso, no início, o gato só consegue a primeira casa. Portanto, vamos começar da primeira posição e marcar como 0 a quantidade de pulos mínimos para alcançar ela. Em seguida, analisamos cada uma das próximas duas casas, se ela for uma lajota e não tiver sido alcançada, salvamos a quantidade mínima de pulos (a quantidade atual + 1). Depois, passamos para a próxima casa, só iremos efetuar o que fizemos com a primeira se a posição for alcançável (tem uma quantidade de pulos diferente de -1). Iremos analisar cada posição em ordem por meio do loop da função $$for()$$
Ao final, basta imprimir o valor armazenado na quantidade mínima de pulos da posição $$C$$.