Escada perfeita (OBI2006)

Depois de meses sem postar, resolvi que a partir de agora darei mais atenção pra este blog. Muita gente me manda e-mail e comentários com dúvidas e gostaria de deixar bem claro que eu não faço trabalhos de faculdade pra ninguém, mas que se você tiver uma dúvida real onde eu possa ajudar eu ajudarei de bom grado.

Pensei muito sobre o que postar aqui, tenho rascunhos sobre buscas em grafos e sobre resoluções de problemas de grafos, mas resolvi quebrar toda a ordem e, a partir de um scrap de orkut, acabei me lembrando do problema Escada perfeita, da OBI 2006, e me deu vontade de resolvê-lo aqui.

Por que o problema Escada Perfeita?

A programação deste problema é extremamente simples, mas a sua lógica (matemática pura) é muito inteligente. Tente resolver o problema antes de ver minha solução e, caso não consiga, depois veja como a solução é bonita.

Vamos ao enunciado…

Uma construtora, durante a criação de um parque temático, encontrou no terreno um conjunto de várias pilhas de cubos de pedra. Ao invés de pagar pela remoção dos cubos de pedras, um dos arquitetos da empresa achou interessante utilizar as pedras para decoração do parque, determinando que as pedras fossem rearranjadas no formato de “escada”. para isso, os funcionários deveriam mover alguns cubos para formar os degraus das escadas. Só que o arquiteto decidiu que, entre uma pilha e outra de pedras deveria haver exatamente uma pedra de diferença, formando o que ele chamou de escada perfeita. O exemplo abaixo mostra um conjunto de cinco pilhas de pedras encontradas e as cinco pilhas como ficaram após a arrumação em escada perfeita.

Escada perfeita

Tarefa

Dada uma seqüência de pilhas de cubos de pedras com suas respectivas alturas, você deve determinar o número mínimo de pedras que precisam ser movidas para formar uma escada perfeita com exatamente o mesmo número de pilhas de pedras encontrado inicialmente (ou seja, não devem ser criadas ou eliminadas pilhas de pedras). O degrau mais baixo da escada deve sempre estar do lado esquerdo.

Entrada

A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha contém um inteiro n que indica o número de pilhas de pedras. A segunda linha contém N números inteiros que indicam a quantidade de cubos de pedras em cada uma das pilhas, da esquerda para a direita.

Saída

Seu programa deve imprimir, na saída padrão, uma única linha, contendo um inteiro: o número mínimo de cubos de pedras que devem ser movidos para transformar o conjunto de pilhas em uma escada perfeita, conforme calculado pelo seu programa. Caso não seja possível efetuar a transformação em escada perfeita, imprima como resultado o valor -1.

Exemplos

Exemplo 1

Entrada
5
5 4 5 4 2

Saída
5

Exemplo 2

Entrada
6
9 8 7 6 5 4

Saída
9

Exemplo 3

Entrada
2
1 5

Saída
-1

OK. Estão prontos?

Depois de pensar um pouco, conclui-se que:

  1. A escada perfeita é uma PA de razão 1 (aumenta de um em um). Você lembra disso do seu primeiro ano do Ensino Médio? Senão, é bom dar uma relembrada. As fórmulas (simples e facilmente deduzíveis) da PA são:

    Termo geral da PA

    [tex]a_{n} = a_{1} + (n-1).r[/tex]

    Soma de PA

    [tex]\displaystyle S_{n} = (a_{1}+a_{n}).\frac{n}{2}[/tex]

  2. Sabemos quanto vale n (o número de pilhas, número de elementos da PA) e conseguimos calcular a soma de todos os elementos (podemos fazer isso até durante o loop da entrada, certo?)
  3. Sabemos quanto vale a razão (r=1).
  4. Substituindo o que sabemos nas fórmulas conseguimos formar um sistema de equações básico e desta forma torna-se fácil descobrir o valor do primeiro e do último termo da PA ([tex]a_{1}[/tex] e [tex]a_{n}[/tex]). Resumindo um pouco os cálculos, depois de alguma manipulação algébrica você chega a:

    [tex]\displaystyle a_{n} = \frac{\frac{2.S_{n}}{n}+n-1}{2}[/tex]

    [tex]\displaystyle a_{1} = 1 + a_{n} – n[/tex]

  5. Agora que já sabemos onde começa e onde termina a escada basta fazer um loop em cada fila de blocos e adicionar à uma variável movimentos a quantidade de quadradinhos que estão sobrando nesta fileira (por exemplo, na primeira fileira da figura do enunciado está sobrando três quadradinhos para chegar ao [tex]a_{1}=2[/tex]). Ao mesmo tempo, adicionamos à outra variável (moves) a quantidade de quadradinhos que devem ser retirados ou colocados na fileira (porque depois se esta variável não for igual a 0 imprimimos -1). Ficou claro?

Implementação

Variáveis

  • n: número de degraus (fileiras de blocos)
  • a: [tex]a_{1}[/tex], número de blocos do primeiro degrau.
  • b: [tex]a_{n}[/tex], número de blocos do último degrau.
  • soma: [tex]S_{n}[/tex], soma da PA.
  • pilha[]: vetor de degraus.
  • movimentos e moves: explicados no quinto passo da solução.
  • i e j: variáveis auxiliares para fazer os loops.

Codeado em C

#include
#define PMAX 10001

int main() {
int i, j;
int n;
int soma=0;
int a, b;
int pilha[PMAX];
int moves=0;
int movimentos=0;

scanf("%d", &n);
for (i=0; i scanf("%d", &pilha[i]);
soma+=pilha[i];
}

b=(((2*soma)/n)+(n-1))/2;
a=1+b-n;

for (i=0; i moves+=(pilha[i]-(i+a));
if (pilha[i]>i+a) {
movimentos+=(pilha[i]-(i+a));
}
}

if (moves!=0) {
printf("-1\n");
} else {
printf("%d\n", movimentos);
}

return 0;
}

Prontinho! :) Qualquer dúvida escrevam seus comentários.

3,562 thoughts on “Escada perfeita (OBI2006)

  1. Muito bom seu blog. Muito bem explicado e as demonstrações são ótimas.
    Pena que o pessoal não sabe fazer bom uso…

    Vou mostrar a um amigo meu, que estuda programação.
    Eu só vim relembrar o que são algoritmos computacionais.

    Sds,

    Rafael

    P.S. Você devia ensinar!

  2. Boa dedução do problema, principalmente sobre a parte de dedução do número de movimentos necessários. Mas eu nao me conformei muito com essa variável ‘moves’ pra verificar se é uma escada perfeita.
    De qualquer forma, uma boa solução.

    (obs.: você não é tão rigoroso quanto eu, esse código pode ter erros, segundo minha deduções, nos scanf()’s. imagine um EOF num scanf(), qual é o valor atribuido à variável? bem, de qualquer forma isso não vem ao caso, mas talvez em uma olimpíada fosse necessário, junto das restrições de valores.
    estou querendo fazer a OBI ano que vem (2008), te enviei um e-mail e até agora não obtive resposta, estou aguardando a resposta dele ainda.)

  3. Muito legal seu blog….gostaria que voce manda-se um blog sobre “ALGORITMOS APLICADOS EM ENGENHARIA I “….um abraço…falow..

  4. I would like to thank you for the efforts you have put in writing this web site. I’m hoping the same high-grade website post from you in the upcoming as well. Actually your creative writing abilities has inspired me to get my own site now. Actually the blogging is spreading its wings rapidly. Your write up is a good example of it.

  5. Aw, it was quite a good post. In notion I have to place in writing similar to this additionally – taking time and actual effort to generate a really good article… but what can I say… I procrastinate alot and also by no indicates appear to go completed.

  6. I discovered your blog site website on google and appearance some of your early posts. Preserve up the great operate. I just extra increase Feed to my MSN News Reader. Looking for toward reading far more by you later on!…

  7. Pingback: Generic for viagra

  8. Generally I try and get my mix of Vitamin E from pills. While I’d really like to through a fantastic meal plan it can be rather hard to at times.

  9. certainly like your web site but you need to check the spelling on several of your posts. Several of them are rife with spelling problems and I find it very troublesome to tell the truth nevertheless I will definitely come back again.

  10. I don’t even know how I ended up here, but I thought this post was good. I do not know who you are but certainly you are going to a famous blogger if you aren’t already Cheers!

  11. Wow! This could be one particular of the most helpful blogs We’ve ever arrive across on this subject. Basically Excellent. I’m also an expert in this topic therefore I can understand your effort.

  12. I am just commenting to let you know of the perfect experience my wife’s princess encountered studying your web site. She picked up numerous details, most notably what it’s like to have an ideal helping character to have many more very easily gain knowledge of selected advanced subject matter. You undoubtedly exceeded our own expectations. Thanks for offering such effective, healthy, explanatory and in addition fun thoughts on this topic to Gloria.

  13. Hey, you used to write wonderful, but the last few posts have been kinda boring… I miss your tremendous writings. Past few posts are just a little out of track! come on!

  14. Hello! I just now would like to supply a massive thumbs up for any wonderful information you could have here within this post. We are coming back to your blog post for further soon.

  15. I ran into this page accidentally, surprisingly, this is a great website. The site owner has done a great job writing/collecting articles to post, the info here is really insightful. You just secured yourself a guarenteed reader.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>