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 do piso da diretora, há pisos do tipo que estão centralizados em coordenadas fracionadas, ao mesmo tempo que também há pisos que estão em coordenadas inteiras, somando os dois temos pisos do tipo 1 no total.
Para os pisos de tipo 2 devemos observar que para um lado de comprimento , há 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 . Segue o código para melhor entendimento.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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"; | |
} |
Figurinhas da Copa
Conhecimento prévio necessário
- Vetores (Aula 3)
Para resolver esse problema devemos marcar entre as figurinhas e quais são carimbadas, usando um vetor para todo entre e , onde , caso a figurinha seja carimbada, e , 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 para todo entre e , em que indica, que a figurinha foi comprada pelo menos uma vez, e , indicando que não foi comprada nem uma vez.
A partir disso podemos manter um contador , que conta quantas figurinhas carimbadas ainda não foram compradas, e passar por todos os valores entre e , checando se tanto a figurinha foi comprada, mas também se foi carimbada. Caso os dois sejam verdade diminuimos por .
No final a resposta será .
Segue o código.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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"; | |
} |
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 para todos os entre e , e conforme vamos processando os cheques, , subtraimos de , e somamos a , obtendo no final quanto cada pessoa ficaria devendo, caso ; recebendo, caso ; 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 onde deve para e deve para , então na verdade poderia pagar diretamente, e reduzir o montante que pagaria a pelo valor de quanto deve a , reduzindo a soma total das transações.
A motivo dessa ideia poder ser extendida para situações em que hajam mais de pessoas, é por que depois de computarmos o vetor , poderíamos montar um algoritmo que monte um grafo, da seguinte forma:
- Selecione a pessoa , em que
- Ache uma pessoa w, em que
- Crie um cheque entre e que tem custo,
- Some o custo do cheque a e subtraia em , pois deu esse dinheiro e recebeu
- Repita 1-5 até todo
É 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 , pois esse é o total transferido, porém contado duas vezes.
Então para chegar à resposta devemos computar o vetor , e durante o processamento guardar quanto seria a resposta pela situção inicial. Após isso computamos , 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 , a resposta mínima. Segue o código.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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"; | |
} |
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.