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. Why YouTube movies are shared everywhere? I think one reason is that these are trouble-free to take embed script and paste that script anyplace you wish for.

  2. Hi friends, how is everything, and what you wish for to say concerning this piece of writing, in my view its genuinely amazing designed for me.

  3. For the reason that the YouTube video clips are posted here same like I also embed YouTube video code at my own website, as it is trouble-free to obtain embedded code.

  4. I must convey my affection for your kind-heartedness for men and women that really want help with this one topic. Your real dedication to getting the message all-around came to be astonishingly functional and has really enabled ladies just like me to reach their aims. Your amazing useful instruction indicates a lot a person like me and far more to my mates. Regards; from all of us.

  5. Hello, of course this article is actually good and I have learned lot of things from it regarding blogging. thanks.

  6. Hello, I also desire to share my opinion at this place, when i don’t know even about a effortless thing related to Personal home pages, I always go to look for that from net.

  7. Quality posts is the secret to invite the visitors to visit the web page, that’s what this website is providing.

  8. Link exchange is nothing else but it is simply placing the other person’s web site link on your page at appropriate place and other person will also do similar for you.

  9. Thank you for every one of your effort on this blog. My mom takes pleasure in conducting internet research and it’s easy to understand why. Many of us learn all relating to the lively manner you provide insightful guidance through your blog and therefore inspire response from website visitors on the point then our own daughter is undoubtedly discovering a whole lot. Take pleasure in the rest of the year. You’re doing a powerful job.

  10. continuously i used to read smaller content that as well clear their motive, and that is also happening with this article which I am reading at this place.

  11. If you are going away to watch funny videos on the net then I suggest you to go to see this web site, it carries truly so comical not only videos but also extra material.

  12. Zune and iPod: Most people compare the Zune to the Touch, but after seeing how slim and surprisingly small and light it is, I consider it to be a rather unique hybrid that combines qualities of both the Touch and the Nano. It’s very colorful and lovely OLED screen is slightly smaller than the touch screen, but the player itself feels quite a bit smaller and lighter. It weighs about 2/3 as much, and is noticeably smaller in width and height, while being just a hair thicker.

  13. Because the admin of this web site is working, no uncertainty very quickly it will be well-known, due to its feature contents.

  14. Paykasa yüzbinlerce platformda alışverişlerde kullanabileceğiniz ön ödemeli bir karttır.
    Paykasa kart kullanıcıları basit işlem yapmak ve güvenli alışveriş için online alışverişlerde paykasa kartı tercih etmektedirler. paykasa al firması olarak bizlerden güvenli bir şekilde satın alanilirsiniz.

  15. I wish to show thanks to you just for rescuing me from such a predicament. Because of scouting throughout the search engines and finding ideas which are not productive, I figured my life was gone. Existing without the presence of approaches to the issues you have resolved all through your short post is a crucial case, and the kind that could have in a wrong way affected my entire career if I hadn’t noticed your web page. Your actual knowledge and kindness in maneuvering all the pieces was priceless. I am not sure what I would have done if I hadn’t encountered such a solution like this. I can at this point look ahead to my future. Thanks a lot so much for the high quality and effective help. I won’t be reluctant to propose your web site to any individual who would like guidance on this issue.

  16. Sofia CapelsÃ¥här lägger du upp video: kopiera videons url och posta den i inlägget, se till att den fÃ¥r stÃ¥ ensam pÃ¥ en rad. Under inlägget klickar du för “Show the Redirect URL below in the link instead of this page URL. NOTE: You may have to use the FULL URL below!”xx

  17. My husband and i ended up being really contented that Chris could complete his basic research because of the precious recommendations he had while using the site. It is now and again perplexing just to happen to be handing out techniques that many some people might have been trying to sell. We fully grasp we have you to appreciate because of that. The main explanations you made, the straightforward site navigation, the relationships you can aid to foster – it’s got all superb, and it’s leading our son in addition to the family reason why this topic is pleasurable, which is certainly extremely mandatory. Thank you for everything!

  18. Hi there, its understandable article along with this YouTube video; I can’t believe that one can not understand this easy piece of writing having with video demo.

  19. I also like Flash, however I am not a good designer to design a Flash, however I have software program by witch a Flash is automatically produced and no more to hard working.

  20. Asking questions are really good thing if you are not understanding anything entirely, except this piece of writing presents fastidious understanding yet.

  21. I as well as my pals were taking note of the nice procedures from your web blog then all of the sudden developed an awful suspicion I never expressed respect to the blog owner for those techniques. The young men became certainly glad to study them and have actually been having fun with them. I appreciate you for indeed being very helpful as well as for considering these kinds of cool topics most people are really eager to understand about. Our own sincere regret for not saying thanks to you earlier.

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>