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. sabar.dalam proses macam ni kita tak ada rujukan dari mana2 parti sebelum jadi peratus kejayaan memang tak ttingi apa lagi parti yang baru.jadi pada aku ada baiknya diberi laluan untuk mereka perbetulkan kesilapan disamping kita kenalpasti diperingkat bawahan..bukan dengan hentam membuta tuli.kalau benar2 tuan cekap kenapa tuan tidak berada disana? sekurang2nya untuk membantu

  2. It’s awesome to pay a visit this website and reading the views of all friends on the topic of this piece of writing, while I am also zealous of getting know-how.

  3. Admiring the persistence you put into your blog and detailed information you provide. It’s awesome to come across a blog every once in a while that isn’t the same old rehashed material. Wonderful read! I’ve saved your site and I’m adding your RSS feeds to my Google account.

  4. My point exactly, I think its kind of pathetic that they even put this article on the website because its just bad press for all parties involved especially with these unnamed sources, its just sad that this is what our world has come to…….

  5. A person necessarily assist to make seriously articles I would state. That is the first time I frequented your website page and to this point? I amazed with the analysis you made to make this actual post extraordinary. Wonderful task!

  6. Its my good fortune to pay a quick visit at this webpage and find out my required post along with video demo, that’s YouTube video and its also in quality.

  7. It is the happiest day of my life so far, when I am watching these} funny videos at this place, since after complete day working I was so tired and now feeling fine.

  8. Why YouTube video lessons are shared everywhere? I think one reason is that these are simple to take embed code and paste that code anywhere you wish for.

  9. Hi there to every body, it’s my first pay a quick visit of this weblog; this web site consists of remarkable and really fine stuff designed for visitors.

  10. Thank you for all your labor on this blog. My niece really likes managing internet research and it is easy to see why. We all notice all concerning the dynamic tactic you provide worthwhile suggestions by means of the website and foster participation from people on the issue plus our own daughter is undoubtedly understanding a lot. Take pleasure in the remaining portion of the year. You’re carrying out a fantastic job.

  11. 14/09/2009 – 12:24pm¿y alguno ha leído la noicia que dice más o menos; Ibrahimovic solo sabe jugar con Messi? Es de los más increíble, eso sin mencionar el desprecio de Roberto Palomar en la última página de hoy hacia equipos como el Valencia, parece que tienen prisa en descartar a otros equipos para dar la impresión que solo existe el Madrid y luego un Barsa que lo venden en plan catastrofista.

  12. When someone writes an article he/she maintains the plan of a user in his/her mind that how a user can be aware of it. Thus that’s why this paragraph is great. Thanks!

  13. Feb14carolinesherrard Oh, to stop the guilt when putting myself first. There’s a difference between self-care and selfishness. It’s how we do it that counts. Respecting others is, of course, essential. Yet we actually respect others more if we first properly, wholly and wholeheartedly look after ourselves first.

  14. Hurrah! After all I got a web site from where I can actually get helpful facts concerning my study and knowledge.

  15. I have read much about without charge blogging websites, however I have no clear idea regarding that, can any one tell me which one is best in support of free blogging and site-building?

  16. Hmmm, yup no uncertainty Google is most excellent in favor of blogging except nowadays word press is also fastidious as a blogging as its Search engine marketing is pleasant defined already.

  17. Asking questions are really good thing if you are not understanding something completely, but this post offers good understanding yet.

  18. Thanks a lot for providing individuals with a very remarkable chance to read in detail from this blog. It is always so excellent and as well , stuffed with a great time for me personally and my office co-workers to search your web site at least three times every week to find out the new items you have. And of course, I’m also usually fascinated with the impressive tricks you serve. Some 3 ideas in this article are definitely the best I have had.

  19. I loved as much as you will receive carried out right here. The sketch is attractive, your authored material stylish. nonetheless, you command get bought an shakiness over that you wish be delivering the following. unwell unquestionably come more formerly again since exactly the same nearly very often inside case you shield this increase.

  20. Hi there every buddy, it’s a fantastic entertaining at at this place viewing these funny YouTube movies at here, good stuff, thanks to admin of this site

  21. I am cheerful to see this you tube video at this website, so right now I am also going to add all my video lessons at YouTube web page.

  22. Hello it’s me Fiona, I am also visiting this web site regularly, this web page is really nice and the users are genuinely sharing pleasant thoughts.

  23. No problem, and further more if you wish for update alerts from this site then you must subscribe for it, it will be a suitable for you Jackson. Have a good day!

  24. This piece of writing regarding SEO presents clear picture in support of new SEO users that how to do Search engine optimization, thus keep it up. Fastidious job

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>