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.

10,003 thoughts on “Escada perfeita (OBI2006)

  1. I am commenting to make you know what a nice discovery our child experienced checking your web page. She came to understand so many issues, with the inclusion of what it’s like to have an awesome coaching style to have folks just master a variety of extremely tough topics. You actually did more than her desires. Many thanks for showing such practical, dependable, educational and as well as fun tips about that topic to Kate.

  2. palagay ko nga napakaasim nyan kasi madami ang suka sa, ako kasi konti lang maglagay ng suka parang sweet and sour lang sya tas may oyster sauce para lumasa ng maayos instead na soy sauce lang ang gamitin..

  3. I and also my buddies came reviewing the good helpful tips on your web blog while then got a terrible suspicion I never thanked the blog owner for those strategies. Those guys appeared to be absolutely passionate to see all of them and now have very much been loving them. Appreciation for being so helpful as well as for finding this sort of superb themes most people are really desperate to be aware of. My personal honest regret for not saying thanks to sooner.

  4. فایل هایی که برای دانلود در پوشه dlc گذاشتین خیلی کمتر اون چیزی هست که در عکس مشاهده میشه اگر میشه بقیش رو برای دانلود بزارید ( البته اگر به Time out شدن هنگام وصل شدن به سرور ربط داره) ممنون.

  5. I definitely wanted to write down a quick remark in order to express gratitude to you for all the superb hints you are giving on this website. My extensive internet lookup has at the end of the day been recognized with excellent insight to go over with my friends and classmates. I ‘d admit that most of us visitors actually are rather blessed to dwell in a superb website with very many brilliant individuals with interesting opinions. I feel truly lucky to have come across your website and look forward to so many more thrilling moments reading here. Thanks a lot once more for a lot of things.

  6. Try swapping the 12AX7 tubes with 12AU7 tubes. This will mellow it down and help fight feedback. You will get a smoother sound with less distortion, which may sound better with harp.Keith

  7. Wydaje mi się, że tablet jest lepszy dla osób, które często podróżują i nie muszą zbyt często korzystać w pracy z Worda, czy Excela. Ja siebie jako użytkowniczki tabletu nie widze, bo musze właśnie dość często koryzstać z pakitu biurowego. Nie wyobrażam sobie pracy z Excelem czy Wordem na ekranie dotykowym.

  8. I have to express some thanks to you just for rescuing me from this situation. Because of looking out through the the net and seeing strategies which were not productive, I believed my life was gone. Existing minus the solutions to the problems you’ve resolved by way of your entire guideline is a critical case, as well as ones which may have badly affected my entire career if I hadn’t noticed the website. Your actual ability and kindness in controlling all the stuff was important. I don’t know what I would have done if I hadn’t come upon such a point like this. I’m able to at this point relish my future. Thanks very much for your expert and result oriented help. I will not be reluctant to suggest your site to anyone who should receive guidelines about this subject matter.

  9. hi cora ! my youtube name is ciindiizzlei just wanted to say that i really like the fact that your little giveaways arent titled that like some other gurus and are really for your true subscribers just proves to me you truly are honest and genuine person oh and also you are GORGEOUS !

  10. Thanks for each of your work on this site. Kim loves doing investigation and it’s obvious why. All of us notice all about the compelling form you present useful guidance on this blog and therefore cause response from some other people on this point while our simple princess is really being taught a lot. Enjoy the remaining portion of the new year. You’re conducting a dazzling job.

  11. Thank you, I’ve just been searching for information about this topic for a while and yours is the best I’ve found out till now. But, what concerning the conclusion? Are you positive in regards to the supply?

  12. I definitely wanted to jot down a comment to appreciate you for all the nice secrets you are placing on this site. My extended internet search has at the end been paid with wonderful tips to go over with my friends and classmates. I would assume that most of us readers actually are rather lucky to be in a very good website with very many brilliant individuals with beneficial concepts. I feel somewhat happy to have used the website and look forward to some more thrilling minutes reading here. Thank you once again for everything.

  13. Hi Mynette, missed visiting your blog the last couple of weeks. I am with you in respect of going towards brown when I hear the words vintage and you have done your card in your own remarkable style. Super Petal! Suzanne :)

  14. Other harbours include Agaete and Amfi del Mar. The Count’s tower, the Church Of The presumption, where the members of the expedition were sanctified, together with the Well Of Aguada – where the water that baptized America was drawn, have survived to this very day.

  15. My husband and i ended up being so happy when Emmanuel could round up his research through the ideas he came across in your web pages. It’s not at all simplistic to simply continually be giving for free key points the others could have been trying to sell. And we do understand we need you to be grateful to for that. The most important illustrations you made, the simple web site menu, the friendships you can make it easier to foster – it’s got most wonderful, and it is aiding our son in addition to us believe that that content is fun, which is extremely important. Thank you for all the pieces!

  16. We’ve already seen the response to the citizens grand jury, it’s the same as the right to petition for redress of grievances. Just words on an old piece of paper. The robed thieves have you perplexed but not out manned. Soon the time to decend on these institutions with demands will be the last resort.

  17. I precisely wished to appreciate you once again. I do not know the things that I might have made to happen in the absence of the tips and hints shown by you over my situation. It has been the frustrating condition in my opinion, but viewing a specialised way you resolved the issue made me to cry for delight. I’m just happy for your work as well as pray you know what a great job you’re doing training men and women thru your website. I’m certain you have never come across any of us.

  18. If you want that, download Go Keyboard and download CNHandwriting for GO Keyboard (both are free) if you want touch input in Chinese. Android, by default, will only change typed and read words. You have to use a third-party method like I put above to get touch input in Chinese.

  19. June, I'm sorry you have to go through this at the school. It is frustrating that we have to work so hard to get things done when we're already dealing with "extra" stuff. I will definitely post before and after pics. I can't wait to get to the decorating phase. He loves blue so that will be a major theme. :-)

  20. Reklamní systémy na web ? | Reklama na net Very nice post. I just stumbled upon your weblog and wanted to say that I have really enjoyed surfing around your blog posts. In any case I will be subscribing to your rss feed and I hope you write again very soon!

  21. Buenas tardes Victor,Te recomiendo que para informarte mejor de todos los detalles y requisitos de este curso, te pases por Emotion Sports Club, nuestro comercial te recibirá amablemente respondiendo a tus dudas y facilitándote la inscripción. ¡Gracias!

  22. I am glad for commenting to make you understand of the fabulous discovery my cousin’s girl encountered visiting yuor web blog. She realized a lot of pieces, including what it’s like to possess an ideal teaching nature to let the mediocre ones without difficulty fully grasp certain grueling subject matter. You actually exceeded our own desires. Thanks for churning out these beneficial, safe, informative not to mention fun thoughts on the topic to Ethel.

  23. I have not taste tested them yet! I’m looking forward to it. Two recipes were submitted… and a big thank you to you and Paul for submitting. I am not going to be able to judge so that it’s fair! Best of luck to both of you!

  24. I intended to write you one very little word to give many thanks as before for your personal breathtaking secrets you’ve contributed in this case. It’s certainly surprisingly open-handed of people like you in giving freely all most of us could possibly have advertised as an electronic book to help with making some dough for themselves, and in particular considering that you could possibly have tried it if you considered necessary. Those concepts also acted to become easy way to be certain that many people have similar dream just as mine to know somewhat more with respect to this issue. Certainly there are numerous more fun moments ahead for people who looked at your blog post.

  25. Rodrigo disse:Leo disse:29 de agosto de 2010 às 17:53O M2000 é um contexto antigo ? Os problemas do MIII, continuam com o 2000.Colocar requisito de ToT acima do operacional não faz sentido, já que o aparelho vai ter que operar dia a dia.ToT é prioritária em projeto não operacional, por exemplo: O programa espacial.

  26. I simply wanted to post a quick message so as to express gratitude to you for all of the remarkable guidelines you are placing at this site. My long internet investigation has now been honored with brilliant content to write about with my neighbours. I ‘d believe that most of us site visitors are definitely lucky to dwell in a very good site with so many outstanding professionals with valuable methods. I feel really fortunate to have come across the webpage and look forward to many more brilliant minutes reading here. Thanks once more for everything.

  27. I have to voice my respect for your kindness in support of men who really need help with this particular study. Your personal commitment to passing the solution up and down had become really interesting and has in every case made individuals just like me to attain their objectives. Your amazing insightful guideline means so much a person like me and substantially more to my office workers. Warm regards; from all of us.

  28. Soy Evelyn que sono con el enorme pez negro caer sobre el mar provocando un maremoto veia que el mar alcanzaba a cubrir la cuidad y creo que el pais completo era algo frustrante parecia real cuandio desperte le pedi gracias a Dios por ser solo un mal sueno porfavor expliqueme que significa , gracias de antemano.Evelyn como se me lo envia a mi correo electronico?

  29. I have to convey my admiration for your kind-heartedness supporting visitors who need help on that concern. Your real dedication to getting the solution up and down appeared to be especially good and has always made somebody much like me to achieve their pursuits. Your new insightful information entails so much a person like me and especially to my mates. Thank you; from each one of us.

  30. trust,I would observe that almost universally when women complain that “my man won’t talk about his feelings” they are really saying “my man doesn’t tell me what I want to hear.”My wife has long learned to not ask if she’s not prepared to hear what I’m really thinking. (Though she also often asks, “What are thinking besides that.” meaning, besides sex. Of course, that doesn’t stop me from saying something like, “My boss is pissing me off and I’m horny.”

  31. A lot of thanks for all of the hard work on this blog. Kate take interest in going through investigation and it’s really obvious why. A lot of people know all about the powerful method you present worthwhile tips and hints on this web blog and as well encourage participation from visitors about this issue plus our own princess is always studying a lot. Take advantage of the remaining portion of the year. You have been performing a great job.

  32. Very flattering blouse and pants! Until you mentioned your problems with the pants, I had no idea they were not to your liking because the photos are awesome. It’s probably better that your little one was asleep in the candy shop. She probably would have been rather busy if she was awake!

  33. " Sper insa din tot sufletul, sa descoperiti intr-o zi bucuria si lumina pe care le aduce credinta in Dumnezeu."Prefer soarele, e real. Ironic, basmele cu zeul tau au radacina tot in iubirea pentru soare, doar ca nu mintea slaba a credinciosului nu intelege etimologia aceasta. p.s. lol – am captcha: "rejoy"

  34. hi, public transport means are a lot in nigeria, but being a foreigner u can hardly can use any of those okadas or damfos. its my 4th visit to nigeria but i havent used them ever.. i m in love with this country because it gives me unbelievable good business, but when it comes to settle down in nigeria, it needs a second thought..

  35. My husband and i felt quite happy that Peter managed to conclude his analysis using the ideas he got while using the web page. It’s not at all simplistic to simply continually be freely giving methods which often men and women might have been making money from. We really fully understand we’ve got the writer to give thanks to because of that. Most of the explanations you’ve made, the easy blog menu, the relationships you help to instill – it’s got most overwhelming, and it is assisting our son in addition to us believe that the matter is thrilling, which is certainly truly important. Thank you for the whole lot!

  36. Good post. I be taught one thing more challenging on different blogs everyday. It’ll all the time be stimulating to learn content material from other writers and follow somewhat one thing from their store. I抎 favor to make use of some with the content material on my blog whether you don抰 mind. Natually I抣l give you a link in your web blog. Thanks for sharing.

  37. I and also my pals were digesting the nice tactics on your site while instantly developed a horrible feeling I never thanked the blog owner for those secrets. All of the guys were for that reason glad to study them and already have pretty much been using these things. Appreciate your genuinely well thoughtful and for obtaining variety of fine subject areas millions of individuals are really needing to know about. Our own sincere apologies for not saying thanks to earlier.

  38. I wanted to post you a little word just to say thanks a lot the moment again over the remarkable solutions you’ve featured in this article. It was really tremendously generous with you to supply publicly all a lot of folks might have supplied for an electronic book to earn some dough for their own end, and in particular since you might well have done it if you ever decided. The advice likewise worked to be a good way to comprehend other individuals have the same dream really like my own to see great deal more on the topic of this matter. I’m sure there are some more fun situations ahead for individuals that read through your website.

  39. I am only writing to let you know what a outstanding discovery my princess developed studying yuor web blog. She figured out several things, including what it is like to have a wonderful teaching nature to let many people effortlessly gain knowledge of specific impossible subject matter. You undoubtedly exceeded her expectations. Thank you for supplying such interesting, healthy, revealing and also fun tips on your topic to Kate.

  40. Hola Yolanda,Me alegro muchísimo que te haya servido mi blog para encontrar información para tu viaje. La verdad es que Texel me pareció una isla preciosa… fácil para recorrer en bici y muy tranquila… una gozada. Espero que lo paséis muy bien en vuestro viaje!Un saludo,Sonia.

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>