TFC 2022 - Programação Nível Júnior

Para conferir a prova na íntegra, clique aqui.

Dia do Bolo

Escrito por Estela Baron

Conhecimento prévio necessário:

Como cada convidado precisa de ao menos uma fatia de bolo, sabemos que a quantidade necessária, em gramas, será de $C * F$ . Porém, a quantidade de bolo que temos é $B$ quilos, então, para transformar em gramas, é preciso multiplicar por $1000$ ( 1 quilo = 1000 gramas).

Por fim, só precisamos ver se $B * 1000$ é maior ou igual a $C * F$ , se for, imprimimos 'S', caso contrário, imprimimos 'N'.

Observações: na hora de ler a entrada, tome cuidado com o tipo das variáveis, pois $B$ não é um inteiro. Quando for imprimir, lembre de pular linha.

Clique aqui para conferir o código

Laserzinho

Escrito por Enzo Dantas

Conhecimento prévio necessário:

If e For

A ideia mais simples para esse problema, que é simular cada ação, é rápida o suficiente, então a maior dificuldade é implementar.

Para adicionar um laser qualquer, iremos percorrer todas as colunas da linha na qual o laser está contido e adicionar um ao contador de lasers da posição (uma operação análoga deve ser aplicada a coluna na qual o laser está contido). A operação de remover um laser é a mesma, apenas subtraindo em vez de somar. Tal operação percorre uma linha inteira e uma coluna inteira, o que implica uma complexidade de $O(M+N)$ . Lembre-se de subtrair o laser do meio, pois ele é contado duas vezes.

Para responder a pergunta em si, iremos percorrer toda a matriz definida pelos pontos dados e checar se todas as casas estão ligadas. Tal operação pode percorrer a matriz inteira, o que implica uma complexidade de $O(N*M)$ .

A complexidade final é $O(Q*($ complexidade das queries $))$ . Como a query mais lenta possui complexidade de $O(N*M)$ , a complexidade final é $O(Q*N*M)$ = $O(10^6)$ .

Clique aqui para conferir o código

Tesouro

Escrito por Estela Baron

Conhecimento prévio necessário:

Estruturas Condicionais

Toda vez em que há um comando, ou a linha muda, ou a coluna muda. Portanto, não precisamos criar uma matriz para ver o que está acontecendo. Quando há o comando 'C', passamos a ter $X - 1$ , no comando 'B', passamos a ter $X + 1$ , no comando 'E', passamos a ter $Y - 1$ e , no comando 'D', passamos a ter $Y + 1$ .

Observe que, se mudamos o $X$ , o $Y$ não sofre alteração, mesma coisa para quando mudamos o $Y$ .

No fim, só precisamos percorrer os caracteres de $S$ e ir mudando o que precisa ser mudado de acordo com os comandos ( + 1 ou -1 em X ou Y). Ao final, imprimimos $X$ e $Y$ .

Clique aqui para conferir o código

Estante

Escrito por Arthur Lobo

Conhecimento prévio necessário:

Busca em Grafos

O enunciado nos diz que podemos colocar até $K$ livros do mesmo gênero em uma caixa. Portanto, se tivermos $L$ livros de um determinado gênero, o número mínimo de caixas necessárias será $\lceil \frac{L}{K} \rceil$ , onde $\lceil \rceil$ significa teto, ou seja, $\frac{L}{K}$ arredondado para cima. Por exemplo, se tivermos $8$ livros do gênero fantasia e podemos colocar no máximo $3$ livros por caixa, teremos que colocar $3$ livros na primeira caixa, $3$ na segunda e $2$ na terceira, usando um total de $\lceil \frac{8}{3} \rceil = 3$ .

Mas como fazemos para descobrir quantos livros existem de cada gênero?

Vamos representar as relações de livros do mesmo gênero como um grafo, em que se existe uma relação entre dois livros $A$ e $B$ dizendo que eles são do mesmo gênero, então vamos adicionar uma aresta entre os vértices $A$ e $B$ .

Agora esse grafo vai ter uma propriedade especial: Todos os vértices de um mesmo gênero vão estar na mesma componente conexa. Então podemos fazer uma $dfs$ no nosso grafo para descobrir o tamanho de cada componente, se uma componente tem $L$ vértices (e portando, $L$ livros), então somamos $\lceil \frac{L}{K} \rceil$ na resposta.

Clique aqui para conferir o código