TFC 2022 - Programação Nível 1

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

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

Potes

Escrito por Vitor Veiga

Conhecimento prévio necessário:

Resumindo o problema, ele nos dá $N$ itens em uma esteira e $M$ preços de montagem dos itens de diferentes cores, e quer que combinemos os itens da esteira com seus respectivos pares de mesma cor (inversos) gastando o mínimo possível para montar novos itens, sendo possível reservar os potes (itens de valor positivo) em uma pilha para processar depois. Só é possível acessar o primeiro item da esteira e o pote no topo da pilha em um mesmo tempo.

A chave para resolução desse problema será utilizar um algortimo guloso, sempre realizando a melhor ação possível no momento. Assim sendo, sempre que nos depararmos com um pote na frente da esteira, jogamos ele no topo da pilha para, posteriormente, tentar juntá-lo com uma tampa da esteira, e seguimos para o próximo item. Caso tenhamos uma tampa na frente da esteira, é necessário que achemos o seu par na pilha, portanto começamos a montar tampas reservas para os potes do topo da pilha até acharmos um pote de mesma cor da tampa. Caso não achemos esse pote, e tendo em vista que não é possível montar novos potes nem colocar a tampa na pilha, não podemos prosseguir, assim retornando -1.

Após o processamento de todos os items da esteira, basta contabilizar o preço das tampas dos potes que ainda estão na pilha, e, finalmente, retornar nossa respota.

Para melhor entendimento da estratégia, analisaremos o segundo caso teste:

valores = $1, 2, 3, 4, 5$
esteira = $1, 2, 2, 3, -2$

pilha = $1$
esteira = $2, 2, 3, -2$
valor total = $0$

pilha = $2, 1$
esteira = $2, 3, -2$
valor total = $0$

pilha = $2, 2, 1$
esteira = $3, -2$
valor total = $0$

pilha = $3, 2, 2, 1$
esteira = $-2$
valor total = $0$

pilha = $2, 1$
esteira = $\emptyset$
valor total = $3$

pilha = $\emptyset$
esteira = $\emptyset$
valor final = $6$

Clique aqui para conferir o código

Portas

Escrito por Enzo Dantas

Conhecimento prévio necessário:

Update em range (BIT ou Lazy update (Segment Tree))
Algorimo de Kadane

Ao ler o enunciado, percebe-se que o problema pode ser dividido em duas partes: 1) Construir o array e 2) Achar o subarray máximo desse array (o valor da posição $x$ do array é o valor das cartas que estão no baú de posição $x$ ). Tal estruturação é evidente pois todos os updates são realizados antes da query, ou seja, ele é estático. Problemas dinâmicos (que possuem updates intercalados com queries) geralmente têm uma solução bem mais complexa do que a versão estática.

Primeiramente, o problema de achar o maior subarray de um array é bastante conhecido: ele pode ser implementado em $O(N*log_n)$ (utilizando um $set$ ou uma $priority$ $queue$ ) ou em $O(N)$ utilizando o algoritmo de Kadane. Como é um problema clássico, não vou explicá-lo aqui - há uma infinidade de vídeos no YouTube e blogs explicando-o.

Secundariamente, a parte de construir o array pode ser feita de várias formas. Para os leitores que têm familiaridade com lazy update, adicionar um valor a um intervalo [l,r] deve ser uma etapa simples. Tal processo é clássico e é explicado na aula do NOIC citada acima, então também não será explicado aqui.

Bônus

Existe uma maneira de realizar esse update em range sem usar nenhuma das estruturas acima em tempo linear. Essa ideia é parecida com a ideia de update em range da BIT, mas usa o fato de que todos os updates são dados antes das queries, ou seja, é possível realizar esses updates offline. O código mencionado abaixo utiliza essa ideia.

[collapse]

Finalmente, o único detalhe restante é que a implementação deve ser feita com $scanf/printf$ ou com a linha

ios::sync_with_stdio(false); cin.tie(0);

para ler o input mais rapidamente, pois o input é muito grande $(N=10^6)$ . Caso contrário, seu código vai receber TLE.

Clique aqui para conferir o código