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. Thanks regarding giving your opinions listed right here. The other point will be that whenever a difficulty occurs having a computer technique motherboard, individuals ought not take the danger regarding restoring this themselves because if it is not carried out correctly it can cause permanent injury to the whole laptop. It will be safe in order to approach your dealer of one’s laptop for your repair with the motherboard. They’ve already technicians who have an knowledge when controling laptop motherboard problems which enable it to get the right prognosis and also conduct maintenance.

  2. Thanks a lot for giving everyone remarkably nice opportunity to read in detail from this site. It is always so nice and jam-packed with a lot of fun for me and my office co-workers to visit your website on the least three times every week to study the fresh stuff you have. And indeed, I’m just always happy with your exceptional pointers served by you. Some 3 points on this page are in truth the most beneficial I’ve ever had.

  3. I and also my pals ended up reviewing the best secrets and techniques located on the blog and so the sudden got an awful feeling I never thanked the web site owner for those secrets. Those women became consequently thrilled to read through them and have in effect surely been taking pleasure in these things. We appreciate you truly being indeed accommodating and also for considering varieties of smart resources millions of individuals are really desirous to know about. Our honest regret for not saying thanks to sooner.

  4. En nuestro cuarto taller hemos traducido automatix 4.5-2 hemos realizado la automatización de los procesos de instalación y construcción del paquete. Hemos preparado el camino para realizar nuevas traducciones si viene más gente.

  5. Dear sir thanks for all your help am realy learning alot from you web site.I am a second year student doing electronics and i wanted you to please help me on how i can connect that simple programmer on a microchip coz i dont wanna mess out thing,they are 5 wires out and dont know which is which,please help me out.

  6. Me he quedado delirando de lo bruto que soy, por mas que he tratado, no se que pasa, pero no puedo aumentar el tamaño del texto y como está me resulta ilegible.Salud

  7. about the nobody will notice your weak sides… thats not really true. if someone has something that someone else wants or if they are comparing themself to someone else doing the same thing they are doing there is always going to be someone looking for your weakness to bring you down and/or to make themselves feel better. that happens in every aspect of life doesnt it? always judging, always comparing, always competing. once we finally get to the point where we think we have what we want we start noticing others more and trying to compare ourselves to them.

  8. I really like your blog.. very nice colors & theme. Did you make this website yourself or did you hire someone to do it for you? Plz respond as I’m looking to construct my own blog and would like to find out where u got this from. appreciate it

  9. I love Lady Gaga's songs especially this one. The lyrics are great!First time I saw this video but I remember the song from Ms. Congeniality. Nice!Here's my for this week.By the way, I have an ongoing giveaway. The prize is something kids would love. Just to join.

  10. Did you pony up the $7 to delete yourself from the “high” risk data miners? It was very simple to delete myself from the low and medium risk firms — they all sent confirmation emails — but I think I’ll spend the change to eliminate myself (¡!) from the high risk firms. …thanks for this!

  11. An interesting dialogue is value comment. I believe that you must write extra on this subject, it might not be a taboo subject however generally persons are not sufficient to speak on such topics. To the next. Cheers

  12. I’ll gear this review to 2 types of people: current Zune owners who are considering an upgrade, and people trying to decide between a Zune and an iPod. (There are other players worth considering out there, like the Sony Walkman X, but I hope this gives you enough info to make an informed decision of the Zune vs players other than the iPod line as well.)

  13. A new avid reader of your blog..tried a few recipes and worked: choc molten cake, roast lamb etc..told so many ppl of your fab blog..do keep the great recipes rolling in. Got to know Lorraine through your blog too and got her to bake a few cakes which all turned out superb.Your blog and hers have become a must read daily..

  14. Det der må jo være helt midy i blinken for alle. Se som de skjønne ungene koser seg! Herlig.Kos dere sååå masse og nyt tiden dere er der nede.Klem Hege-Mamma til 3

  15. Curly questions…* Much of the novel is spent in bleaker lands than Narnia. Other than physical characteristics, what are some differences? Are any of the inhabitants at all similar to Narnians?* How do Puddleglum’s actions contrast with his attitudes? Does he do anything surprising? Can he be characterized as a hero? Can Jill or Eustace, given their behavior?

  16. if you have dish, you can get whats known as a TERK which clips on the back of the dish, and is amplified. They do quite well. Also, if you havent tried it already, go somewhere like radioshack and buy The HIGHEST GAIN amplified TV TOP antenna. These also do fairly well, with about a 30ish to 40ish db Gain.

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>