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