Tabelas de preços de impressão são interessantes. É muito comum que quanto mais você imprima mais baratas as impressões fiquem, fazendo com que o gráfico de preço por impressões não seja monótono (isso é, você não necessariamente pague mais por um número maior de impressões).

Isso torna as gráficas boas candidatas de lugares para pensar em gráficos de funções de primeiro grau, assim como a busca binária é uma boa candidata de aplicação para pensar sobre logaritmos.

Hoje fui imprimir uma partitura e me deparei com a seguinte tabela:

Cópias	Preço
De 01 a 03 unidades	R$ 0,70 cada
De 04 a 10 unidades	R$ 0,50 cada
De 11 a 20 unidades	R$ 0,40 cada
De 21 a 50 unidades	R$ 0,30 cada
De 51 a 100 unidades	R$ 0,25 cada
Acima de 100 unidades	R$ 0,20 cada

(registrada em uma foto de um bilhão de dólares)

Se desenharmos um gráfico de preço (eixo y — vertical) por número de impressões (eixo x — horizontal), temos:

Observando esse gráfico (feio), percebemos que há alguns números de impressões que economicamente não faz sentido fazer. Por exemplo, 3 impressões custam R$ 2,10 enquanto 4 impressões custam R$ 2,00. 20 impressões custam R$ 8,00 enquanto 21 impressões custam R$ 6,30. 100 impressões custam R$ 25,00 enquanto 101 impressões custam R$ 20,20.

Mas não só esses. Os valores que não faz sentido imprimir no gráfico são todos aqueles cujo existe algum ponto a direita na mesma altura ou mais baixo, ou seja, todos os que pintei de amarelo:

Um problema econômico interessante para quando se está numa gráfica imprimindo é, portanto, descobrir quando estamos nos pontos amarelos. É interessante porque, se estivermos nos pontos amarelos, podemos aproveitar para imprimir mais cópias ou pedir ao dono da gráfica um desconto. Afinal, é razoável esperar que o preço que a gente pague seja limitado por este gráfico:

Descobrir se estamos numa região amarela é simples. Basta calcular o preço que pagaríamos a princípio (multiplicar o número de cópias pelo preço por cópias da região em que estamos) e comparar com o preço que pagaríamos se pedíssemos o menor número de cópias da região imediatamente mais barata. Por exemplo, faz sentido imprimir 15 cópias porque $15 \times 0.40=6.00$ é menor do que $21 \times 0.30 = 6.30$, mas não faz sentido imprimir 85 cópias porque $85 \times 0.25 = 21.25$ é maior do que $101 \times 0.20 = 20.20$.

---

Agora vamos inverter o problema. Vamos supôr que você é a gráfica e quer evitar esse tipo de cliente insuportável, fazendo o preço ir ficando mais barato proporcionalmente com o número de impressões, mas mantendo a função monótona (crescendo).

Poderíamos pensar em funções que crescem cada vez mais devagar…

… mas parece complicado achar uma função que não nos dê prejuízo quando o cliente quiser muitas cópias e parece especialmente complicado explicar para o cliente que o preço de x cópias é um monte de constantes multiplicadas pelo logaritmo de x.

Então talvez seja melhor pensar em funções de primeiro grau mesmo.

Se você separar todas as funções que encontramos na tabela de preços do problema anterior e colocá-las num gráfico, você vai ver que a interseção delas só acontece num ponto: o ponto x = 0.

(esse gráfico foi um oferecimento Wolfram Alpha)

Uma forma de resolver o problema é fazer com que as interseções sejam nos pontos onde o preço das impressões muda. Isso se faz movendo cada uma das funções um pouquinho pra cima, isso é, adicionando constantes às funções de primeiro grau.

Por exemplo: 3 cópias custam R$ 2,10. Se a partir de 4 cópias quisermos que as cópias custem R$ 0,50 em vez de R$ 0,70, podemos forçar que 4 cópias custem R$ 2,10 + R$ 0,50 = R$ 2,60. R$ 2,60 é R$ 2,00 + R$ 0,60. Logo, em vez de usarmos a função de preço $f(x) = 0.5x$ para $x$ entre 4 e 10, podemos usar a função $f(x) = 0.5x + 0.6$.

Se repetirmos o mesmo raciocínio para as outras interseções, a tabela de preços final fica assim:

Cópias	Preço
De 01 a 03 unidades	R$ 0,70 cada
De 04 a 10 unidades	R$ 0,60 fixo + R$ 0,50 cada
De 11 a 20 unidades	R$ 1,60 fixo + R$ 0,40 cada
De 21 a 50 unidades	R$ 3,60 fixo + R$ 0,30 cada
De 51 a 100 unidades	R$ 6,10 fixo + R$ 0,25 cada
Acima de 100 unidades	R$ 11,10 fixo + R$ 0,20 cada

(Isso aqui é só um exercício. Por favor, não façam isso, donos de gráficas!)

Agora note que as coisas passam a fazer mais sentido (embora muito mais caras):

• 3 cópias custam R$ 2,10 e 4 cópias custam R$ 2,60;
• 10 cópias custam R$ 5,60 e 11 cópias custam R$ 6,00;
• 20 cópias custam R$ 9,60 e 21 cópias custam R$ 9,90;
• 50 cópias custam R$ 18,60 e 51 cópias custam R$ 18,85;
• 100 cópias custam R$ 31,10 e 101 cópias custam R$ 31,30.

O gráfico monótono (e bonito) comprova:

Ontem, no período da tarde, foi aplicada a prova da primeira fase da OBI2006, modalidade Programação Nível 2. Já que nem todos os colégios submeteram as soluções de seus alunos, ainda não vou publicar os meus códigos nem o enunciado dos problemas, mas apenas escrever sobre o que achei da prova (assuntos separados em tópicos).

Tempo de Prova

O caderno foi composto por cinco questões, para serem resolvidas em cinco horas. Na minha opinião, foi tempo até demais para o nível dos problemas. Acabei a prova em pouco mais de três horas (depois de criar outros casos de teste, ver a complexidade dos algoritmos e tudo…).

Dificuldade da Prova

Embora no começo eu sempre leve um susto, no fim achei a prova fácil. Fiz as cinco questões, acho que acertei todas e a complexidade de nenhum dos meus algoritmos ficou muito pesada (mas também nunca se sabe…). Espero tirar uma nota superior a 400 (de 500) e acho que é possível até eu ter gabaritado.

Complexidade

Neste ano, o pessoal deixou a parte de tempo bem fácil. Ao invés de ser um conjunto de teste em cada entrada, foi apenas um teste por entrada. A conseqüência é que, além da questão de tempo ficar mais fácil, também não precisamos nos preocupar em zerar as variáveis a cada loop.

Problema mais difícil

O melhor problema da prova foi, na minha opinião, o Escada Perfeita. Infelizmente, não posso comentar muito a respeito dele até todos submeterem suas soluções, mas esse problema foi muito bom.

No meio de um problema de grafos (Museu), dois de coisas básicas tipo entrada/saída (Truco e Jogo de Cartas) e um problema para mostrar que sabemos mexer com matrizes (Colheita de Caju); o sistema de equações que dava pra montar neste problema (Escada Perfeita) baseado na fórmula de soma de PAs (aquela lenda do Gauss quando tinha cinco anos…) e depois um algoritmo guloso, fizeram com que eu ficasse mais de uma hora tentando encontrar a solução (que ficou com complexidade O(n)). Depois crio um post para comentar mais a respeito!

---

Enfim… Não posso entrar em muitos detalhes por enquanto e nem tenho certeza de como fui. A fase pós-prova/pré-nota é sempre complicada… Mas, se não cometi erros que [se existirem] devo perceber e comentar nos próximos artigos, rumo a segunda fase!

Pessoal que participou também, comentem aí dizendo como foram!