TFC 2020

Para conferir a prova na íntegra, clique aqui.

Transporte

Comentário escrito por Vitor Veiga

Conhecimento prévio necessário:

Dadas duas capacidades, máxima e mínima, de um trem $L$ e $M$ , queremos achar uma nova capacidade máxima $N$ tal que esta vale 30% de $L$ , e dizer se ela é maior que $M$ . Além disso, devemos remover as casas decimais de $N$ para realizar a comparação.

Sendo assim, basta calcular $N = 0.3 * L$ e depois checar se $N < M$ . Se for, retornamos $0$ , se não, retornamos $M$ . Note que poderiamos declarar $N$ como uma variável do tipo double e depois retirar as casas decimais utilizando a função floor(), porém, se declararmos $N$ como um int, o C++ automaticamente realiza a aproximação para o maior inteiro menor que o número decimal resultante da operação.

Clique aqui para conferir o código

Diária

Comentário escrito por Arthur Lobo

Conhecimento prévio necessário:

Soma de Prefixo

Já que a soma de todos os $K$ é menor do que $10^5$ , podemos criar uma lista que guardará quanto custa a diária em cada um dos dias. Sendo Sk o a soma de todos os $K$ , vamos criar um array $D_1, D_2, ..., D_{Sk}$ , em que $D_i$ guardará quanto custa a diária do dia $i$ .

Para montar esse array, digamos que a soma dos $K$ até o blocos de dias $i-1$ é $Sk$ e já montamos a lista até esse bloco (até o dia $Sk$ ). Então se o bloco de dias $i$ tem tamanho $K$ e preço $P$ , então temos que fazer com que todos os valores de $Sk+1$ até $Sk+K$ sejam P, ou seja, $D_j = P$ , para $Sk+1 \le j \le Sk+K$ , e em seguida aumentamos a soma dos $K$ fazendo $Sk+= K$ .

Agora que já montamos a lista de quanto custa cada diária, sabemos que para responder uma consulta $X,Y$ , ou seja, que pergunta qual vai ser o valor total das diárias se ficar hospedado do dia $X$ até o dia $Y$ , devemos computar o valor de $D_X + D_{X+1} + ... + D_Y$ . Agora vamos para as parciais.

Vale ressaltar que se deve usar "long long" ao invés de "int" para computar a soma dos valores de $D$ . O único motivo pelo qual existem algumas parciais com $P \le 10^3$ é para caso alguém esqueça de usar long long.

Parcial 1 ( $Q \le 100$ )

Como nessa parcial nos temos poucas consultas, podemos responder cada uma delas em $O(N)$ .Para uma consulta $X,Y$ , primeiro inicializamos uma variável "int soma = 0", e então computamos a soma das diárias fazendo um for com $i$ indo de $X$ até $Y$ , e fazendo $soma+= D_i$ . No final, a variável soma guardará $D_X + D_{X+1} + ... + D_Y$ .

A complexidade ficará $O(Sk)$ por consulta, então no total é $O(Sk*Q)$ , que é o suficiente.

Parcial 2 ( $X = 1$ )

Nessa parcial, o $X$ da consulta é sempre $1$ , então só nos importamos com o $Y$ , já que o que vamos querer computar é $D_1 + D_2 + ... + D_Y$ , ou seja, a soma de um prefixo da lista.

Para responder qual a soma de cada prefixo, vamos criar outro array $P_1, P_2, ..., P_{Sk}$ , em que $P_i$ vai guardar a soma das diárias até $i$ , ou seja, $P_i = D_1 + D_2 + ... + D_i$ , mas como computar esse novo array?

Perceba que sempre temos que $P_i = P_{i-1} + D_i$ , pois $P_{i-1}$ guardá $D_1 + D_2 + ... + D_{i-1}$ e depois só adicionamos $D_i$ . Portanto, começamos com $P_0 = 0$ , e faremos um for com $i$ indo de $1$ até $Sk$ (nessa ordem), para cada $i$ , faremos $P_i = P_{i-1}+D_i$ , pois quando estamos em $i$ , já calculamos $P_{i-1}$ .

Agora, para responder uma consulta $1,Y$ (já que $X = 1$ ), basta imprimirmos $P_Y$ . A complexidade fica $O(Sk)$ de pré-processamento e $O(1)$ para cada consulta, portando no total fica $O(Sk+Q)$ .

Parcial 3 e 4 (Sem restrições adicionais)

Diferente da parcial anterior, agora cada consulta vai pedir qual é o valor de $D_X + D_{X+1} + ... + D_Y$ , mas como podemos usar o array $P$ para nos ajudar a computar esse valor de forma rápida? Tente imaginar como saber a soma de cada prefixo pode nos ajudar a descobrir a soma desejada.

$P_Y$ é $D_1 + D_{2} + ... + D_Y$ , o problema é que queremos apenas $D_X + D_{X+1} + ... + D_Y$ . Podemos dividir essa soma que forma $P_Y$ em 2 partes: $(D_1 + D_{2} + D_{X-1}) + (D_X + D_{X+1} + ... + D_Y)$ , mas nós queremos apenas essa segunda parte. Perceba que essa primeira parte é exatamente $P_{X-1}$ , então para conseguirmos a soma desejada, podemos fazer $P_Y-P_{X-1}$ , já que, como visto a cima, vai sobrar apenas a segunda parte da maneira que dividimos o $P_Y$ .

Agora, para responder uma consulta $X,Y$ , basta imprimirmos $P_Y-P_{X-1}$ . A complexidade fica $O(Sk)$ de pré-processamento e $O(1)$ para cada consulta, portando no total fica $O(Sk+Q)$ , que é o suficiente.

Clique aqui para conferir o código

Robô

Comentário escrito por Caique Paiva e Enzo Dantas

Conhecimento prévio necessário:

Primeiro, vamos fazer a subtask 3, ou seja, $N, M, L \le 100, K \le 10^4$ . Nesse caso, a ideia é simples! Basta fazer uma matriz $N \times M$ , e, supondo que estamos em $(X, Y)$ , que é inicializada com $(X_i, Y_i)$ , salvamos uma variável auxiliar $con = 0$ , que vai contar a quantidade de obstáculos que já batemos, e dependendo da direção atual, fazemos o seguinte:

Se estamos andando para a direita, então, se $(X+1, Y)$ for um obstáculo, então mudamos a direção para baixo, e fazemos $con++$ . Se não, faça $X++$ .
Se estamos andando para baixo, então, se $(X, Y+1)$ for um obstáculo, então mudamos a direção para esquerda, e fazemos $con++$ . Se não, faça $Y++$ .
Se estamos andando para a esquerda, então, se $(X-1, Y)$ for um obstáculo, então mudamos a direção para cima, e fazemos $con++$ . Se não, faça $X--$ .
Se estamos andando para cima, então, se $(X, Y-1)$ for um obstáculo, então mudamos a direção para direita, e fazemos $con++$ . Se não, faça $Y--$ .

Se $con == L$ , então pare de rodar o código, então, a resposta será $(X, Y)$ .

Perfeito! Agora, vamos melhorar essa solução. Primeiro, para o problema original, temos que $N, M \le 10^5$ , e então não conseguimos nem construir a matriz, pois se não vai dar MLE (Erro no Limite de Memória), então, vamos criar um vetor de set <int> linhas[ $N$ ] e um vetor de set <int> colunas [ $M$ ]. Então, se tem um obstáculo em $(i, j)$ , fazemos $linhas[i].insert(j)$ e $colunas[j].insert(i)$ , e então, a ideia é ver que, se estamos na casa $(X, Y)$ , então, nós vamos andar até chegamos na próxima parede, e aí viramos, ou seja, não precisamos andar as casa uma de cada vez. Logo, vamos mudar nossas condições que fizemos acima. Suponha que estamos em $(X, Y)$ , que é inicializada com $(X_i, Y_i)$ , temos que

Se estamos andando para a direita, então, procuramos no set linhas[ $X$ ] qual é o primeiro obstáculo depois da casa $(X, Y)$ e na mesma linha que $X$ , ou seja, qual é o primeiro $Z$ em linhas[ $X$ ] com $Z > Y$ , e paramos de andar em $(X, Z-1)$ , e então basta fazer $Y = Z-1$ , e $con++$ , pois batemos em uma parede, e então viramos para baixo (Para achar esse valor, basta olhar o ponteiro linhas[ $X$ ].upper_bound( $Y$ )).
As ideias são analogas para os outros casos. Se estamos andando para baixo, então, procuramos no set colunas[ $Y$ ] qual é o primeiro obstáculo depois de $(X, Y)$ , ou seja, qual é o primeiro $Z$ em colunas[ $Y$ ] tal que $Z > X$ , e paramos de andar em $(Z-1, Y)$ , e então basta fazer $X = Z-1, con++$ e virar para esquerda (Para achar esse valor, basta olhar o ponteiro colunas[ $Y$ ].upper_bound( $X$ )).
Se estamos andando para a esquerda, então, procuramos no set linhas[ $X$ ] qual é o primeiro obstáculo depois de $(X, Y)$ , ou seja, qual é o primeiro $Z$ em linhas[ $X$ ] tal que $Z < Y$ , e paramos de andar em $(Z+1, Y)$ , e então, faça $X = Z+1, con++$ e virar para cima (Para achar esse valor, basta olhar o ponteiro linhas[ $X$ ].upper_bound( $Y$ ) e voltar o ponteiro uma vez).
Se estamos andando para cima, então, procuramos no set colunas[ $Y$ ] qual é o primeiro obstáculo depois de $(X, Y)$ , ou seja, qual é o primeiro $Z$ em colunas[ $Y$ ] tal que $Z < X$ , e paramos de antar em $X, Z+1)$ , e então, faça $Y = Z+1, con++$ , e vire para a direita (Para achar esse valor, basta olhar o ponteiro colunas[ $Y$ ].upper_bound( $X$ ), e voltar o ponteiro uma vez).

Clique aqui para conferir o código

Sobrinhos

Comentário escrito por Enzo Dantas

Conhecimento prévio necessário:

Loops

Primeiramente vamos criar um array com os restos de cada pessoa. Mais especificamente, vamos criar um array $v$ e dizer que $v_i = X_i \mathbin{\%} Y_i$ , tal que % é a função que retorna o resto da divisão entre $X_i$ e $Y_i$ . Em seguida vamos ordenar esse array em ordem crescente usando a função $sort$ . Finalmente, a resposta será o k-ésimo elemento desse array.