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:

Soma de Prefixos

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$ .

Clique aqui para conferir o código