OBI2012
Caderno de soluções
Modalidade Programação • Nível 2, Fase 2
12 de maio de 2012
Promoção:
Patrocínio:
Olimpíada Brasileira de Informática – OBI2012
1
Álbum de fotos
Descrição
Dado um retângulo X × Y e dois retângulos X1 × Y1 e X2 × Y2 , decida se é possível colocar estes dois retângulos
no interior do primeiro retângulo, sem sobreposição, possivelmente rotacionados, mas com lados paralelos aos
do primeiro retângulo.
Limites
• 1 ≤ X, Xi ≤ 1000
• 1 ≤ Y, Yi ≤ 1000
Solução
É fácil ver que se existir uma solução, então existe uma solução onde um retângulo contém um canto do
retângulo maior e o outro contém o canto oposto. Logo basta testar cada uma das 22 = 4 orientações possíveis
por sobreposições/pedaços para fora.
Olimpíada Brasileira de Informática – OBI2012
2
Soma das casas
Descrição
Dados N inteiros em ordem crescente, determinar quais os dois inteiros A e B cuja soma é K.
Limites
• 2 ≤ N ≤ 105
• 0 ≤ ai ≤ 109
• Para todos i e j, ai < aj se i < j
Solução
A solução mais simples e que ganhava uma pontuação parcial na questão tem complexidade O(N 2 ) e funciona
assim: para cada inteiro da sequência busca linearmente no resto da sequência se existe o outro elemento para
que a soma dos dois seja K.
Mas essa solução é muito lenta para N = 105 , pois (105 )2 = 1010 , o que é muito. A solução esperada era com
complexidade O(N ) ou O(N lgN ).
A solução com complexidade linear é da seguinte forma: um apontador é criado para o começo da sequência e
outro para o final. Comparações vão então sendo feitas, chamando o índice do elemento indicado pelo primeiro
apontador de i e o do segundo de j temos 3 possibilidades:
• ai + aj < K
• ai + aj > K
• ai + aj = K
No terceiro caso temos a solução então podemos parar de buscar. No primeiro caso a soma é menor do que K,
então precisamos aumentá-la, para isso devemos avançar i, fazendo i = i + 1, pois ai+1 > ai , não faria sentido
mexer j já que ele vai no sentido de reduzir a soma. Agora, quando temos o segundo caso devemos mover j,
fazendo j = j − 1, pois aj−1 < aj .
Como cada posição da sequência não é visitada mais do que uma vez, a complexidade dessa solução é O(N ).
A solução de complexidade O(N lgN ) envolve ideia similar à solução quadrática, com uma pequena alteração,
ao invés de uma busca linear no vetor é feita uma busca binária, que possui complexidade O(lgN ), dessa forma
são feitas N buscas binárias, uma para cada posição da sequência e a complexidade final fica O(N lgN ).
Olimpíada Brasileira de Informática – OBI2012
3
Bomba
Descrição
Dado um grafo orientado G e um conjunto M de arestas de G, devemos nos restringir a passeios orientados em
que a 3a , 6a , · · · , arestas devem pertencer a M , ao passo que as demais não podem pertencer a M . O problema
é calcular distâncias usando esses passeios.
Limites
O grafo G pode ter até 500 vértices e 2000 arestas.
Solução
Busca em largura no grafo em 3 camadas, ou, de forma equivalente, 3 rótulos por vértice, em que no primeiro
e no segundo se espera uma aresta fora de M e no terceiro uma aresta em M .
Olimpíada Brasileira de Informática – OBI2012
4
Banco
Descrição
Um banco possui C caixas que atendem em esquema de fila única, quem chega primeiro é atendido antes. N
clientes chegam em sequencia, o i-ésimo cliente chega ti minutos depois da agência abrir e demora ai minutos
para ser atendido pelo caixa. Cada caixa só pode atender um cliente por vez.
Pede-se quantos clientes demoram mais de 20 minutos para ser atendidos após entrarem na agência.
Limites
• 1 ≤ C ≤ 10
• 1 ≤ N ≤ 1000
• 1 ≤ ti ≤ 300
• 1 ≤ ai ≤ 10
Solução
Para resolver este problema, note que o tempo máximo para alguém ser atendido é de 10300 minutos desde o
tempo inicial. Isto acontece quando se tem apenas C = 1 caixas, N = 1000 clientes a serem atendidos, todos
chegam com ti = 300 minutos e todos necessitam de ai = 10 minutos para serem atendidos.
Sabendo disto, podemos, basicamente, simular todas as ações que ocorrem no banco, minuto a minuto, até que
não haja mais clientes no banco. Para resolver isto, usamos uma fila como estrutura de dados para armazenarmos
quais os clientes que já estão no banco, mas ainda faltam ser atendidos, a partir do minuto 1. Por fim, também
adicionamos vetores para dizer quantos caixas estão livres para, caso estejam livres, peguem o próximo da fila
e, do contrário, informe quanto tempo é necessário para terminar de atender ao cliente atual.
A complexidade disto é de O(T empoT otal ∗ C), onde T empoT otal é o tempo que você imprimirá como resposta,
que será pequeno.