Comentário NOIC OBI 2018 - Fase 1 - Programação Nível 2

Comentário por Frederico Ribeiro

Piso da Escola

Conhecimento prévio necessário

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

Figurinhas da Copa

Conhecimento prévio necessário

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

Câmara de Compensação

Conhecimento prévio necessário

1. Vetores (Aula 3)
2. Conceito de grafos (Aula 8)

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:

1. Selecione a pessoa $u$, em que $d[u] < 0$
2. Ache uma pessoa w, em que $d[w] > 0$
3. Crie um cheque entre $u$ e $w$ que tem custo, $min(-d[u], d[w])$
4. Some o custo do cheque a $d[u]$ e subtraia em $d[w]$, pois $u$ deu esse dinheiro e $w$ recebeu
5. 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.

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.