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. it will a smiley. Glistrup and Bodissey definitely have very different styles.That’s salmon story is very good, btw.Imagine the stories of poverty in Russia when they had nothing else to eat but Russian Caviar… There’s got to be such stories somewhere.

  2. Hej, jag håller på att baka detta nu men har fastnat lite. Blir så osäker när det är gram istället för dl, du skulle inte kunna hjälpa mej? (: tack för all inspration.

  3. Good day! I just would like to give an enormous thumbs up for the nice info you have right here on this post. I can be coming back to your weblog for extra soon.

  4. dit :Tu vois pas que ton jeu de fin de repas comme on est des pauvres on a baffré tout le caviar y en a plus pour jouer.Merci de le rebaptiser Jeu du début de repas.Et eske y a des couverts spéciaux pour le caviar? y a bien des fourchettes à huitres…

  5. 228Congrats Jessica!! You’re just a few weeks ahead of me. Can’t believe you went through this too. I had never heard of anything like this before I went through it. Life being a waste of time was pretty much exactly how I felt. So glad to be out of that dark place. At least going forward we’ll be able to spot this ahead of time if it ever rears its ugly head again. At the time, I didn’t know what was happening to me! Best of luck to you too & glad you’re feeling good!109

  6. Looking for work i liked when she pointed her toes and stroked it with her arches… then i loved the end when she was spreading the cum all over her feet… amazing

  7. Santana,Angela non ha detto “non ci sono foto decenti di Armstrong”. Ha detto “non si vede mai Armstrong”.Non solo: dove sarebbero le lamentele di Armstrong? Nella trascrizione dei dialogi dell’escursione lunare non ce n’è traccia.Non è esagerato parlare di bufala: sono ben tre miti da sfatare.

  8. Excelent, Iulia Popovici!Tin sa remarc, fara legatura cu subiectul, ca, daca luam comentariile drept indicator pentru genul de public al site-ului, majoritatea fanilor Critic Atac sunt de dreapta.Sa mori de ras!

  9. What if boys and girls do it together?Do yourself a favor and get your kids a copy of ‘Swallows & Amazons’. Boys and girls together doing ‘dangerous’ things and nothing remarkable or PC about it. Originally published back in the progressive, non-sexist year of … 1930.

  10. Vaig descobrir el Guillermo per recomanació de la meva àvia, i m’ho vaig passar molt bé llegint els llibres vermells de l’Editorial Molino, tot i que jo sóc en teoria d’una generació posterior.

  11. I appreciate, cause I found just what I was looking for. You’ve ended my four day long hunt! God Bless you man. Have a nice day. Bye

  12. made a lot of sense. But, think about this, what if you added a little content? I mean, I dont want to tell you how to run your blog, but what if you added something to maybe get peoples attention? Just like a video or a picture or two to get people excited about what youve got to say. In my opinion, it would make your blog come to life a little bit.

  13. Hola amigo tengo un pez angel que es agresivo solo con uno de mis goldfish que es 5 veces mas grande que él. El escalar mide uns 3cm y mi goldfish tiene 10cm y el angel muerde su cola ¿que hago? no tengo otro acuario donde ponerlo. Es con el único que es agresivo.

  14. Excellent finds, loving the swimsuit. Its actually not rained here which may be a bank holiday first! Altho technically dont think it is one in Scotland… But I'm still taking advantage! :)

  15. Thank you for your entire initiatives you’ve put in these kinds of. very useful data.? The exile? s every day life is absolutely no life.? by Leonidas concerning Tarentum.

  16. Dear Mr. Swain,The gleaners we are examining are mostly poor people who will enter fields and collect any crops left behind, or in some cases, will collect crops that are still growing. The scientists in your novel are being very thorough in destroying the test crops, though I was wondering if you had considered a story in which one of these gleaners consumed a test crop and experienced similar side-effects as the insects.

  17. Since QED it has been clear that even the simplest particle interactions have a fractal nature and so require an infinite amount of computation. By comparison o(2^N) is trivial. If I understand correctly, the only particle level problems that can be solved are the ones where there is enough symmetry to use analytic methods to get rid of the infinities, and all the other problems are left unsolved and experimental values are plugged in. Nature has no such luxury and is simply capable or doing all that, or else what is really happening is something quite different from what the models say is happening.

  18. excessive private debt is the problem. I’m surprised you even contest that.As for “counterfeiting cartel”, what else do you think “loans create deposits” means? Are you so naive as to think banks are good?!

  19. hola deseo obtener la tarjeta azul, soy medico con titulo medico homologado en españa con 16 años de experiencia que debo hacer para obtenerla gracias por su colaboracion.

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>