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,002 thoughts on “Escada perfeita (OBI2006)

  1. I not to mention my buddies have been reviewing the great things located on your website while all of the sudden I got a terrible feeling I had not thanked you for them. All the ladies came for that reason warmed to learn all of them and have without a doubt been loving them. Appreciate your really being so thoughtful and also for having this sort of exceptional subjects millions of individuals are really needing to know about. Our own sincere apologies for not saying thanks to you earlier.

  2. Kun joku tuossa mainitsi, että miksei olisi samanlaista reaktiota vaikka jalkapipareista. No varmasti olisi, jos se jalkapipari olisi tehty oivalluksella, ja siinä olisi jotain hupaisaa, kyllä sellainenkin varmasti onnistuu. Ei minua ainakaan kovasti liikuttanut, että kyseessä on juuri "wow, häpypipari, hihhihhiii", vaan että se oli hauskasti tehty. Minusta tällaisessa piparkakussa ei ole mitään pahaa tai hävettävää, ennemminkin voisi vähän muunlaisista karsia, sen verran pahempaakin tarjontaa tulee joka tuutista nykyään.

  3. I have not checked in here for a while since I thought it was getting boring, but the last several posts are really great quality so I guess I’ll add you back to my daily bloglist. You deserve it my friend.

  4. I precisely wished to thank you so much again. I’m not certain the things I might have followed in the absence of the actual pointers documented by you relating to that subject matter. It was a very intimidating circumstance in my circumstances, but observing your specialized manner you solved the issue made me to cry for gladness. I will be grateful for the guidance as well as trust you really know what a powerful job you happen to be putting in training the others via your web blog. I am sure you have never met any of us.

  5. Wow,i never had soap make me drool before..Bravo,So Stinking Sweet!!! I like the Strawberry Rhubarb Shea Butter Bath Soap,Black Berry Fizz Soap,Shaving Soap Berry Bewitching,all of the roll on perfume oils and the She Drives Me Crazy Soap and the……. cyclona66(at)aol(dot)com

  6. I was wondering what is up with that weird gravatar??? I know 5am is early and I’m not looking my greatest at that hour, but I hope I don’t look like this! I may possibly however make that face if I’m asked to do 100 pushups. lolOctober 19, 2011, 2:41 pm

  7. I intended to write you a very little observation so as to thank you once again for the marvelous guidelines you have shared in this case. It’s wonderfully open-handed with people like you to deliver freely what a lot of folks could possibly have distributed as an e-book to generate some profit for themselves, especially seeing that you could have done it in the event you wanted. These tricks likewise worked like the fantastic way to be sure that most people have a similar eagerness like my own to know somewhat more in regard to this condition. Certainly there are thousands of more enjoyable occasions ahead for people who find out your blog.

  8. BIG UP GIGGS HE DESEVERD 2 WIN DAT WALK IN DA PARK MURKED IT R THEY GUNNA SHOW GIGGS IN DA AWARDS HE NEEDS 2 PUT OUT A VIDEO ON MAINSTREAM BIG DJS LIKE U SEMTEX,WESTWOOD, BIG RYDE 4 PLAYIN GIGGS Y DONT LOGAN SAMA PLAY GIGGS

  9. a superb appealing materials….It’s difficult to construct knowledgeable consumers in regards to the topic, yet, you seem like do you realize what goes upon you’re discussing concerning! Thank people…

  10. – my husband is a chiropractor and recommends these products to his patients and has done so for many years. We’ve seen a lot of happy users and believe me, if they weren’t happy with their Nikken products, they would let us know!

  11. My husband and i have been happy when Chris could complete his survey through the entire precious recommendations he discovered out of your web pages. It’s not at all simplistic just to happen to be giving out information and facts that many people have been making money from. Therefore we figure out we’ve got the website owner to appreciate because of that. The most important illustrations you’ve made, the straightforward site navigation, the relationships your site make it possible to foster – it’s many astounding, and it is aiding our son in addition to the family know that the matter is interesting, and that’s pretty mandatory. Thanks for the whole thing!

  12. Important info and outstanding layout you received right here! I might prefer to thanks for sharing your ideas and time into the things you submit!! Thumbs up!

  13. I simply wanted to thank you so much all over again. I’m not certain what I could possibly have used without the entire creative concepts shown by you regarding this question. It had been the challenging problem for me personally, however , encountering a well-written way you dealt with the issue took me to weep for happiness. I am thankful for this information and then pray you comprehend what a great job you have been accomplishing teaching many people with the aid of your websites. Most likely you have never come across all of us.

  14. I have read your article & chavih I am posting here just to let you know that you are doing a great job by keeping us posted about this. Please keep on posting such quality articles as this is a rare thing to find these days

  15. Gina I can no longer share posts from my business page’s news feed onto the timeline. I go through the process and get a message saying that the post was successfully shared, but it isn’t there. Anyone know what’s going on? And yes, I am making sure to designate the proper location from the top left drop down menu. Thanks!

  16. I would like to express my appreciation to this writer just for bailing me out of this type of issue. Right after exploring through the search engines and seeing strategies which are not productive, I was thinking my entire life was gone. Being alive without the answers to the difficulties you have solved all through your good site is a crucial case, and the kind that could have in a wrong way damaged my entire career if I had not noticed your site. Your talents and kindness in touching all the details was very helpful. I’m not sure what I would’ve done if I had not come across such a step like this. I can also at this point look ahead to my future. Thank you very much for your reliable and results-oriented help. I will not think twice to recommend your site to anyone who wants and needs counselling about this situation.

  17. Colin W. StetsonHi, Robyn,So much appreciated the description of your build up to Noah’s role of Billy. I’m from Indiana, (made the drive here to see this weekends series of shows) have seen BETM all over the globe, London, NYC, Toronto, Chicago and so looking forward to seeing Noah’s performance either today or tomorrow when his assignment comes up. Wishing you both my best in this wonderful venture as Billy, and I know he will be a smashing success equal to the dozens of Billies I’ve seen up to this point.Deepest Regards,Colin Stetson, Department of Athletics, Culver Academies, Culver, IN

  18. I just want to tell you that I am very new to weblog and absolutely liked this web page. Probably I’m likely to bookmark your website . You absolutely come with really good articles. Thanks a bunch for revealing your website page.

  19. mir gerade Gedanken darüber gemacht, wie man außerhalb der übliche Keyword-Tools an Ideen kommt, um die passenden Keywords zu finden. Denn bei vielen SEM- und SEO-Projekten sind

  20. I’m just commenting to let you understand of the cool discovery my cousin’s princess obtained reading your site. She figured out plenty of things, with the inclusion of how it is like to possess an incredible helping character to have men and women without problems know precisely various hard to do matters. You truly surpassed my expectations. I appreciate you for coming up with these interesting, dependable, explanatory and in addition cool guidance on your topic to Jane.

  21. I needed to write you this little bit of remark to finally say thanks a lot yet again about the stunning techniques you have discussed on this site. It was simply surprisingly open-handed of people like you to offer publicly what exactly many people would’ve offered for an ebook to help make some profit for their own end, most notably considering the fact that you might well have tried it in the event you decided. Those tactics as well worked to provide a great way to realize that other people have the identical eagerness really like my personal own to figure out a lot more around this problem. I am sure there are some more pleasurable situations up front for many who go through your blog post.

  22. Wenn du die Sigma DP1/DP1s/DP2/DP2s meinst dann braucht Fuji die X100 gar nicht rausbringen – das sind ja alles Todgeburten, auch nicht zuletzt wegen der Fixbrennweiten.PS: Der FoveonX3 ist kein APS-C, wenn auch nur geringfügig kleiner

  23. Es un gran suplemento. Espero que sigáis torturando a esos voluntarios todos los años porque creo que se aprende más de periodismo que con el proyecto fin de carrera y además se disfruta tanto cuando lo ves impreso que merece la pena el trabajo.Isabel

  24. I simply needed to thank you so much once more. I’m not certain what I would’ve accomplished in the absence of the entire creative concepts contributed by you regarding my subject. This has been a frightful matter in my opinion, however , coming across the very expert way you treated it made me to weep with gladness. I’m just thankful for the work and as well , pray you recognize what a great job you are undertaking educating some other people through a web site. I am sure you have never come across all of us.

  25. Thank you so much for providing individuals with a very marvellous possiblity to read critical reviews from this website. It really is so useful and as well , stuffed with fun for me and my office colleagues to search your web site really 3 times weekly to learn the newest issues you have. And indeed, I am also usually contented concerning the gorgeous knowledge you serve. Some 4 points in this post are in truth the simplest we’ve had.

  26. Thank you a lot for providing individuals with such a splendid possiblity to read critical reviews from here. It’s always so sweet and as well , stuffed with a great time for me and my office acquaintances to search the blog minimum three times in one week to learn the fresh tips you have. And of course, I’m also actually amazed for the mind-boggling strategies you serve. Certain 2 facts in this post are indeed the most efficient we’ve had.

  27. A lot of thanks for your own labor on this website. Kate enjoys doing investigation and it’s obvious why. I notice all about the powerful form you render very helpful strategies through this web blog and even welcome contribution from visitors about this concept so our daughter is without a doubt discovering a whole lot. Take advantage of the remaining portion of the year. You have been conducting a dazzling job.

  28. It’s been a busy week for you. What’s the best way to get rid of the stress of a busy week? The best and only way is by spending some time with the beauties over at http://www.camgirl.pw These are the girls who know how to treat a man right.

  29. I precisely desired to appreciate you once more. I am not sure the things I could possibly have followed without the actual ways shared by you about my topic. It truly was a horrifying issue in my view, but seeing a specialized manner you handled the issue took me to jump over joy. I’m just grateful for your guidance and even pray you are aware of a powerful job that you are doing educating the others using your site. Most probably you’ve never got to know any of us.

  30. A good time is what you’ll have with the girls at http://www.camgirl.pw. This is by far the most exciting site on the entire internet. Don’t think twice about visiting this site. Not if you’re in the mood to have a little kinky fun.

  31. My spouse and i have been absolutely lucky when Louis could deal with his inquiry from the ideas he grabbed through your weblog. It’s not at all simplistic to simply be giving out procedures that others have been selling. So we grasp we have got the blog owner to be grateful to for that. The specific explanations you’ve made, the straightforward website navigation, the friendships you will help to promote – it is all sensational, and it’s facilitating our son and us imagine that the situation is amusing, which is rather vital. Thanks for all!

  32. Are you searching for a little fun? If you are, then http://www.camgirl.pw is the best site for just that. You’ll find plenty of hot babes there who love to get down and dirty. That’s exactly what you’re looking for right this very second.

  33. I have to voice my passion for your kindness supporting persons who actually need help on this particular field. Your real dedication to passing the message throughout appeared to be definitely interesting and have surely permitted girls just like me to get to their dreams. This helpful facts signifies a whole lot to me and especially to my peers. Thanks a ton; from all of us.

  34. I must show thanks to you for rescuing me from this problem. As a result of looking through the online world and getting principles that were not productive, I thought my life was well over. Existing without the presence of solutions to the issues you have solved all through your good short article is a serious case, as well as the ones which might have badly affected my entire career if I had not come across your blog post. Your primary training and kindness in playing with almost everything was invaluable. I’m not sure what I would’ve done if I hadn’t encountered such a thing like this. It’s possible to at this moment look ahead to my future. Thanks for your time very much for this skilled and result oriented guide. I won’t think twice to refer your blog post to anyone who wants and needs counselling about this problem.

  35. I have to express my passion for your kindness supporting visitors who should have help on this one theme. Your personal dedication to getting the message all around appeared to be quite practical and have encouraged somebody much like me to achieve their goals. Your new interesting suggestions means so much to me and additionally to my colleagues. Many thanks; from each one of us.

  36. I not to mention my friends were examining the nice key points from your site then suddenly developed an awful feeling I never thanked the website owner for those strategies. All of the ladies became consequently happy to study all of them and now have in truth been loving these things. Thank you for turning out to be considerably accommodating as well as for pick out certain nice tips millions of individuals are really desperate to discover. Our own sincere regret for not expressing appreciation to you sooner.

  37. Take a good look at http://www.camgirl.pw This is the one site where you can have a lot of fun. The fun you can have here is exactly what you’re looking for. Enjoy yourself and meet some sexy ladies in the process.

  38. I precisely wished to say thanks all over again. I’m not certain the things that I could possibly have worked on without the type of tactics provided by you over this field. It had been a fearsome crisis for me personally, but considering a specialized technique you resolved it made me to leap over happiness. I am thankful for your assistance and thus sincerely hope you realize what an amazing job you are putting in teaching people today via your blog post. Most probably you have never got to know any of us.

  39. My husband and i have been absolutely joyous that John could conclude his reports because of the precious recommendations he got while using the web site. It is now and again perplexing to simply choose to be offering instructions which people today may have been trying to sell. So we figure out we now have the website owner to thank for this. All of the explanations you made, the easy blog menu, the relationships your site make it easier to promote – it’s all extraordinary, and it’s really aiding our son and the family consider that that issue is enjoyable, and that’s incredibly mandatory. Many thanks for all!

  40. The weekend is fast approaching. Why not spend it with a sexy cam girl? There’s plenty of them over at http://www.camgirl.pw All of these girls are wanting to have a good time. That’s exactly what you’re looking for too. The most fun you’ll ever have online is right here. Have yourself a good time and meet someone new. That’s what this site is all about.

  41. I do not even know how I ended up right here, however I thought
    this publish was once great. I do not understand who you
    might be however certainly you’re going to a well-known blogger in the
    event you are not already. Cheers!

  42. Did you know that people make their entire income promoting ClickBank? You too could be one of the many who have quit their job. Affiliate marketing is as old as the internet. It’s not going to go away any time soon. You too can get your piece of the pie. Why shouldn’t you? Do you really like working the job you have? Are you going to be able to do it until you retire? If you’re job requires physical labor, then you know the answer to that question. There’s no way you’re going to be able to do that when you get older. That’s just the truth and no one needs to tell it to you. Right now you could be making money online. Does it require work? You better believe it does. No honest person is ever going to tell you that it’s possible to become a millionaire online without doing any work whatsoever. It’s not possible. That doesn’t mean there isn’t money to be made. There’s plenty of money out there to be made by people just like yourself. Now you know there’s going to be a pitch for a product. You’re right about that. Click on the link http://64efd6-lz41s3rcelbr7s2xl7x.hop.clickbank.net/ and check it out. There’s a video you can watch that will explain everything. It will tell you how to make money using ClickBank. Watch the video and see what you think. You too can be one of the many who earn a living promoting ClickBank. Some people earn a good living and there’s no reason why you can’t.

  43. Just imagine for a second if you could get into the mind of a millionaire. Think of all the things that you could learn. Well, you actually can do just that. A millionaire is giving away all of his secret right on the internet. You don’t even need to leave the house to learn what made him rich. All it takes is visiting http://e31a67zd-ccr7u13el2cflqp0d.hop.clickbank.net He will literally teach you all of the secrets to making money. Don’t you think it’s time that you earned the living that you deserve? Change your life today by simply following the link above. Do it for yourself and everyone that you care about.

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>