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.
| #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 $$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"; | |
| } |
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.
| #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.
