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.


#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int x, y;
cin >> x >> y;
// numero de pisos do tipo 1
int ar = x*y + (x-1)*(y-1);
// numero de pisos do tipo 2
int per = 2*(x + y - 2);
cout << ar << "\n";
cout << per << "\n";
}

view raw

piso.cpp

hosted with ❤ by GitHub

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.


#include <bits/stdc++.h>
using namespace std;
const int maxn = 110;
int compra[maxn];
int car[maxn];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, c, m;
cin >> n >> c >> m;
for (int i = 0; i < c; i++) {
int a;
cin >> a;
car[a] = 1;
}
for (int i = 0; i < m; i++) {
int a;
cin >> a;
compra[a] = 1;
}
int ans = c;
for (int i = 1; i <= n; i++) {
if (car[i] and compra[i]) ans--;
}
cout << ans << "\n";
}

view raw

fugurinhas.cpp

hosted with ❤ by GitHub

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.


#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
int d[maxn];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int m, n;
cin >> m >> n;
int tot = 0;
for (int i = 0; i < m; i++) {
int a, b, v;
cin >> a >> v >> b;
tot += v;
d[a] -= v;
d[b] += v;
}
int ans = 0;
for (int i = 1; i <= n; i++) ans += abs(d[i]);
ans /= 2;
if (ans != tot) cout << "S" << "\n";
else cout << "N" << "\n";
cout << ans << "\n";
}

view raw

compensacao.cpp

hosted with ❤ by GitHub

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.