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.

498 thoughts on “Escada perfeita (OBI2006)

  1. My husband and i ended up being very peaceful Louis could deal with his inquiry while using the ideas he grabbed out of your web pages. It’s not at all simplistic just to possibly be giving freely guidance which usually other folks might have been selling. And we all recognize we have got the blog owner to thank for that. The most important explanations you have made, the simple web site menu, the relationships your site aid to engender – it’s got many fantastic, and it’s helping our son in addition to the family feel that this content is interesting, and that’s highly important. Thanks for the whole lot!

  2. Aug22norma A mídia da WWF apresenta, com frequência, uma abordagem delicada, suave mesmo, para passar as suas mensagens, em comparação a outras organizações, tipo: PETA. Em alguns, sente-se um ‘namoro’ com o subliminar, como o passado pelo título do presente. Funciona!Grata e Boa Sorte!Norma

  3. Thank you a lot for providing individuals with an extraordinarily spectacular chance to read articles and blog posts from this site. It really is so pleasing plus full of a good time for me personally and my office colleagues to visit your site the equivalent of three times per week to read the latest guides you have. And lastly, I’m also always happy concerning the striking tips served by you. Selected 3 areas in this article are easily the finest I have had.

  4. I and my guys appeared to be going through the great tips and hints on your website then at once I got a horrible feeling I never thanked the web blog owner for those strategies. The boys had been for that reason thrilled to study them and have now seriously been using these things. We appreciate you genuinely so thoughtful as well as for settling on this form of brilliant useful guides millions of individuals are really needing to learn about. Our own sincere regret for not expressing gratitude to sooner.

  5. savistar pratikriya denaar aahe. Aflatoon post aahe.. Ya veli tumheech goa madhe majhi mast soy kelit.. Tevhaachyaa khadadi vishayi lihin. Martins corner miss jhale. Maheetach navhate. Kenchuky maheet aahe.Ya veli ratri colva beach che shawarama haanale feni sobat.

  6. I am really impressed with your writing skills and also with the layout on your weblog. Is this a paid theme or did you customize it yourself? Either way keep up the nice quality writing, it is rare to see a nice blog like this one nowadays..

  7. I actually wanted to compose a brief remark in order to say thanks to you for the fabulous points you are writing on this site. My long internet look up has now been honored with good insight to exchange with my friends. I would mention that most of us website visitors actually are very endowed to be in a fine website with many awesome professionals with very beneficial concepts. I feel very happy to have come across your website page and look forward to tons of more fabulous moments reading here. Thanks a lot again for a lot of things.

  8. Dreambes, je veux pas te manquer de respect, ou te paraitre condescendant, mais franchement, pourquoi tu l’ouvre? Cette album, Wars of the roses, est plein de bonnes idées, mais c’est vrai, la piste Providence avec ses coeurs c’est mauvais et pas à sa place…et l album dans l ensemble laisse une impression de "j ai raté le c…

  9. aoifemcThey were awesome sausages. They basically had the texture of normal sausage but with the denser taste of black pudding. I’m sure it’s a secret recipe! They’re don’t seem to be available on the website so they could be a new product, but keep an eye out in Sheridan’s on South Anne Street for them. So yum!

  10. I want to show my admiration for your kind-heartedness in support of people who really want assistance with your concept. Your very own commitment to passing the message throughout appeared to be surprisingly good and have enabled guys like me to realize their ambitions. Your personal helpful facts denotes a great deal a person like me and even more to my fellow workers. Best wishes; from everyone of us.

  11. My spouse and i felt quite cheerful Raymond could deal with his homework using the precious recommendations he was given when using the web pages. It’s not at all simplistic to simply always be making a gift of information and facts that many most people could have been selling. So we recognize we have the blog owner to be grateful to because of that. The specific illustrations you have made, the simple blog menu, the relationships you can aid to foster – it’s got mostly unbelievable, and it’s really facilitating our son in addition to our family know that this situation is amusing, which is extraordinarily mandatory. Many thanks for all!

  12. Have you ever considered writing an e-book or guest authoring on other blogs? I have a blog based upon on the same information you discuss and would love to have you share some stories/information. I know my audience would enjoy your work. If you are even remotely interested, feel free to shoot me an e mail.

  13. Thank you so much for providing individuals with an extremely pleasant chance to read critical reviews from this site. It is always very superb plus full of amusement for me personally and my office mates to visit your blog a minimum of three times in one week to study the latest guides you have. Of course, I’m certainly pleased concerning the splendid information served by you. Selected 3 ideas on this page are honestly the simplest we’ve had.

  14. I am incredibly jealous of you. Now I’m even more excited to play Uncharted 3! :’cAlso, it’s cool that you’re fond of the 3D support for it. I’m not a fan of 3D at all. Still, I’m curious. Have you encountered any other games on the PS3 you’d say stand out as making it worthwhile?

  15. Io, urmatoarea runda de elevi va fi sortata in aceasta seara. Pana vei afla din ce casa faci parte, poti comenta la postarile din cadrul turului. Casele vor fi atribuite prin tragere la sorti; daca Jobenul spune la Astropufi, atunci acolo vei fi. Imi pare rau, dar nu pot schimba chestia asta! :( Poate Jobenul va crede ca esti demna de un Astropuf.

  16. : oh que si l'enthousiasme est toujours bine présent ( dévoré d'une seule traite traite) car Anne Percin ne nous ressert pas les aventures des premiers tomes ! Elle as su donner un nouveau souffle toute cette équipe!

  17. We’re history buffs who love politics, so Marcus McGee’s books about former California Assembly Speaker/San Francisco mayor Willie Brown were a real treat for us. We’ve followed Wille for years through the ups and downs. These books give us detailed insights about some of the most significant events that happened at the State Capitol, ever. Our favorite: The Speakership Battles, but they are all good!

  18. My husband and i were quite thankful that Louis could do his research through your ideas he received in your web site. It is now and again perplexing to just find yourself offering helpful tips which usually most people could have been selling. And we all do understand we have got the blog owner to give thanks to because of that. Those illustrations you made, the easy web site navigation, the friendships your site make it easier to engender – it’s got everything superb, and it is assisting our son and the family understand that issue is fun, which is highly important. Many thanks for the whole thing!

  19. sin lugar a dudas este gobierno en pleno se ha convertido en un peligro social, los deberiamos declarar delincuentes; ahora como esto les parece poco y lo va a ser y visto qeu respondemos a sus requerimientos en europa o mejor en alemania quieren montar un grupo de expertos que fiscalice las cuentas de todos los paises. esto es una locura, o los paramos o nos paran a nosotros. nos vemos en la calle.

  20. jetzt wollte ich mich doch mal für deine ganzen lieben kommentare bei mir bedanken :) und der link zu den karten ist toll. das werde ich mir gleich erstmal in ruhe anschauen. scheint genau mein geschmack zu sein :) liebe grüße,sandra

  21. Afonso,The point is that the Muslims in Russia are well integrated in general since long time back (Chechnya being the exception). This works when there is a strong and self-confident national culture. We see the same in e.g. Bulgaria. The ease with which some of them convert to Christianity is an indication of this.Anyone understanding the nature of Islam knows that in a Muslim community where people convert to Christianity at ease, not considering it a big thing, it tells something about that Muslim community as a whole. So I assumed that in a forum like this, that statement would suffice to give the whole picture.

  22. I’m writing to make you know what a outstanding discovery my wife’s girl gained going through your blog. She picked up a wide variety of details, which include what it is like to possess an incredible coaching nature to get men and women with ease grasp specific impossible topics. You really surpassed readers’ expectations. Thank you for displaying those good, safe, informative and also fun thoughts on the topic to Ethel.

  23. Does your blog have a contact page? I’m having problems locating it but, I’d like to send you an e-mail. I’ve got some creative ideas for your blog you might be interested in hearing. Either way, great website and I look forward to seeing it develop over time.

  24. I definitely wanted to jot down a remark to thank you for all the stunning advice you are posting here. My time consuming internet investigation has at the end been rewarded with reliable insight to exchange with my company. I would say that we site visitors actually are unquestionably endowed to dwell in a fantastic site with many marvellous individuals with great concepts. I feel very much happy to have come across the web page and look forward to really more cool minutes reading here. Thanks once again for all the details.

  25. I have to show my thanks to this writer for bailing me out of this type of setting. As a result of checking through the internet and finding views that were not helpful, I assumed my life was gone. Being alive without the presence of approaches to the problems you’ve fixed through your entire review is a serious case, as well as the kind which could have adversely damaged my entire career if I hadn’t discovered your site. Your own competence and kindness in touching all the pieces was helpful. I don’t know what I would have done if I hadn’t encountered such a subject like this. I can now relish my future. Thanks for your time so much for this professional and effective help. I will not hesitate to recommend the sites to any individual who would like guidelines on this matter.

  26. Doutor, eu torci para que o Corinthians não passasse do Palmeiras, pois, achava que assim o Tite cairia. Pra mim o problema dele é não dar uma alternativa tática ao time, as mudanças são sempre as mesmas. O senhor não acha que pra um time que não possui criatividade no meio campo, ele poderia que testado o time com 3 zagueiros dando oportunidade para o Paulo André e liberando os laterais para dar mais opções ofensivas ao time, e para mim,então, sairia o Dentinho e entraria o Paulo André.

  27. Thanks for all your valuable effort on this blog. My daughter really likes participating in research and it is simple to grasp why. We all notice all of the dynamic mode you render helpful suggestions on the web site and even improve response from some others on that article so our favorite daughter is without a doubt learning a lot of things. Have fun with the rest of the new year. You’re performing a useful job.

  28. Wonderful blog! I found it while surfing around on Yahoo News. Do you have any tips on how to get listed in Yahoo News? I’ve been trying for a while but I never seem to get there! Many thanks

  29. I must point out my passion for your kindness in support of people that need help on that matter. Your very own commitment to passing the solution throughout appeared to be extremely good and has made those much like me to reach their desired goals. Your amazing warm and helpful help and advice indicates much to me and somewhat more to my peers. Thank you; from everyone of us.

  30. Jöregn Bergmark, tyvärr är det nog så att det du ser är politisk feghet. Landsbygden tros generera för få röster. jag tror att den analysen är fel, men jag tror att det är förklaringen. I klok arguemntation om landet och livet här skulle tas emot positivt av majoriteten.

  31. Rita Beny will be teaching an intermediate mini course – Sept 6, 7, 13, 14, Tuesday & Wednesday 2:00 – 4:30, Seaside Room. The cost is $42 for 4 sessions. You must be a member of the CB55+ Association to participate in classes held at the centre. Membership is $40.00 per year or $20 from July to December.Hope this helps,Diane

  32. I not to mention my friends have been checking the best strategies from the blog then then developed an awful feeling I never expressed respect to the blog owner for them. Most of the men ended up so stimulated to read them and have now actually been loving these things. Appreciation for getting indeed helpful and for selecting variety of quality subject matter most people are really needing to understand about. My very own sincere regret for not expressing gratitude to you sooner.

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>