Comentário por Frederico Ribeiro
Piso da Escola
Conhecimento prévio necessário
- Leitura e saída (Aula 1)
Para obter o número de lajotas do tipo 1 devemos observar que para um um piso de dimensões $$L\times C$$ do piso da diretora, há $$L\cdot C$$ pisos do tipo que estão centralizados em coordenadas fracionadas, ao mesmo tempo que também há $$(L-1)\cdot (C-1)$$ pisos que estão em coordenadas inteiras, somando os dois temos $$L\cdot C + (L-1)\cdot (C-1)$$ pisos do tipo 1 no total.
Para os pisos de tipo 2 devemos observar que para um lado de comprimento $$L$$, há $$L-1$$ pisos tipo 2, levando em conta que pisos do tipo 2 só existem em lados, e que não há pisos que coincidem, podemos computar o número total de pisos do tipo 2 como $$2\cdot (L+C-2)$$. Segue o código para melhor entendimento.
https://gist.github.com/fredbr/e2784deefd9f5b9413b3783648b5e756
Figurinhas da Copa
Conhecimento prévio necessário
- Vetores (Aula 3)
Para resolver esse problema devemos marcar entre as figurinhas $$1$$ e $$N$$ quais são carimbadas, usando um vetor $$car[i]$$ para todo $$i$$ entre $$1$$ e $$N$$, onde $$car[i] = 1$$, caso a figurinha $$i$$ seja carimbada, e $$car[i] = 0$$, caso contrario.
Para as figurinhas já compradas, devemos ignorar as figurinhas repetidas, de forma a não contar duas vezes uma figurinha que só pode ser colada uma vez no album. Para fazer isso vamos fazer um vetor $$compra[i]$$ para todo $$i$$ entre $$1$$ e $$N$$, em que $$compra[i] = 1$$ indica, que a figurinha foi comprada pelo menos uma vez, e $$compra[i] = 0$$, indicando que não foi comprada nem uma vez.
A partir disso podemos manter um contador $$cnt$$, que conta quantas figurinhas carimbadas ainda não foram compradas, e passar por todos os valores $$i$$ entre $$1$$ e $$N$$, checando se tanto a figurinha $$i$$ foi comprada, mas também se foi carimbada. Caso os dois sejam verdade diminuimos $$cnt$$ por $$1$$.
No final a resposta será $$cnt$$.
Segue o código.
https://gist.github.com/fredbr/a5741fa1510fa5787412f5691a57d3f3
Câmara de Compensação
Conhecimento prévio necessário
Para resolver esse problema devemos pensar em uma maneira de reduzir esse grafo para o grafo final pela descrição do problema, e a partir daí computar a o custo nesse grafo comprarado ao inicial.
Uma maneira simples de fazer isso é mantendo um vetor $$d[i]$$ para todos os $$i$$ entre $$1$$ e $$N$$, e conforme vamos processando os cheques, $$a\ v\ b$$, subtraimos $$v$$ de $$d[a]$$, e somamos $$v$$ a $$d[b]$$, obtendo no final quanto cada pessoa ficaria devendo, caso $$d[i] < 0$$; recebendo, caso $$d[i] > 0$$; ou nada. A solução ótima seria para cada pessoa que tem saldo negativo somente sairem cheques, e para cada pessoa que tem saldo positivo somente chegarem cheques, pois caso tenhamos as pessoas $$a,b,c$$ onde $$a$$ deve para $$b$$ e $$b$$ deve para $$c$$, então na verdade $$a$$ poderia pagar $$c$$ diretamente, e reduzir o montante que $$b$$ pagaria a $$c$$ pelo valor de quanto $$a$$ deve a $$b$$, reduzindo a soma total das transações.
A motivo dessa ideia poder ser extendida para situações em que hajam mais de $$3$$ pessoas, é por que depois de computarmos o vetor $$d$$, poderíamos montar um algoritmo que monte um grafo, da seguinte forma:
- Selecione a pessoa $$u$$, em que $$d[u] < 0$$
- Ache uma pessoa w, em que $$d[w] > 0$$
- Crie um cheque entre $$u$$ e $$w$$ que tem custo, $$min(-d[u], d[w])$$
- Some o custo do cheque a $$d[u]$$ e subtraia em $$d[w]$$, pois $$u$$ deu esse dinheiro e $$w$$ recebeu
- Repita 1-5 até todo $$d[i] = 0$$
É facil ver que esse algoritmo para de rodar, pois após cada iteração a quantidade de dinheiro total que falta ser paga estritamente diminui. Apoś rodarmos esse algoritmo criamos um grafo mínimo, que no final leva a mesma situação final que a descrita na entrada.
Usando esse algoritmo podemos ver que a soma do total transferido no grafo mínimo seria $$\displaystyle{\frac{(\sum_{i=0}^N|d[i]|)}{2}}$$, pois esse é o total transferido, porém contado duas vezes.
Então para chegar à resposta devemos computar o vetor $$d$$, e durante o processamento guardar quanto seria a resposta pela situção inicial. Após isso computamos $$\displaystyle{\frac{(\sum_{i=0}^N|d[i]|)}{2}}$$, e vemos se esse valor é menor que o da situação incial. Caso seja a resposta é SIM, caso contrário NÃO, e no final imprimimos $$\displaystyle{\frac{(\sum_{i=0}^N|d[i]|)}{2}}$$, a resposta mínima. Segue o código.
https://gist.github.com/fredbr/c2a1e7f99c2c1c0ce2fb8891ef58c61f
Casos de Teste
ESSES CASOS DE TESTE NÃO SÃO OFICIAIS E NÃO REPRESENTAM A CORREÇÃO FINAL DA OBI.
CASO SEU PROGRAMA PASSE NOS CASOS DE TESTE DISPONIBILIZADOS NÃO SIGNIFICA QUE PASSARÁ PELOS DA OBI, E VICE-VERSA.
DISPONIBILIZAMOS APENAS COMO PARÂMETRO PARA O COMPETIDOR DA PROVA TER IDEIA DE COMO FEZ OS PROBLEMAS ANTES DOS CASOS OFICIAS DA OBI, MAS NÃO INDICA A CERTEZA DA SOLUÇÃO.