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.

1,945 thoughts on “Escada perfeita (OBI2006)

  1. Hello Michelle,I have enjoyed your website lately. I have had a brayer for a while, but hardly use it. I really like a couple of your tutorials, so I did a version of what I saw here. Check it out at itsastampthing.blogspot.com. I even gave you a reference in my post! Hope you like my versions!Kristy

  2. A real problem is that most non critical thinkers think of themselves as critical thinkers, or at least see no reason to think that the thinking of others is any better than their own. This is also seen in other developmental stages, be they cognitive, moral, etc.–

  3. Basic details but wonderful information offered. Hopefully we can all learn from this, great read, find it difficult to get sufficient wish there was more like this kind of. will like this particular post in facebook.

  4. X / É um ABSURDO que o país dê as costas para os bravos guerreiros que abriram mão de suas vidas e as deixaram a mercê da sorte para voltar. Simplesmente um absurdo, nada alem disso.

  5. Kókusz,vanilia,gyümölcs illatu tusfürdö…ezeknek egy hibája van,baromira éhes leszek ha magamra kenem,komolyan.FÅ‘leg a kókusztol és olyankor sütnöm kell nincs mese.

  6. Very good post – though about the longest I can cope with when reading on screen. See if you can write the next one without referring to Stockport County!Football is sick right now, and you've identified many of the problems here. The trouble is that those in power simply don't want to hear it. Depressing stuff indeed.

  7. Pershendetje,une doja tju thoja se sapo kam mbaruar dieten 24 ditore dhe rash 6 kile, por javen e fundit nuk e di pse nuk rash me asnje kile biles shtova rreth 1 kile….gjths pyetja ime ishte a mund te filloj dieten 2 javore direkt mbas 24 ditores se kam dhe 3 kile te tjera qe dueht te heq… ju flm

  8. “I am commited to aging gracefully and am searching vast avenues to maintain my ‘inner glow’.” I love this notion of yours – great blog, though I don’t tend to wear too much make-up these days Best wishes from nice & warm southern Spain

  9. Semoga Bro Azrin lekas semboh….Dlam berpuasa nie kalau ada keuzuran dikecualikan daripada berpuasa. Kalau larat boleh teruskan.Kalau tak larat jangan. Takut rebah dan pitam pulak nanti. Kamal Mustafa recently posted..

  10. June 2, 2011 at 1:41 pmGreat recap. Enjoy reading some of the other ones as well. Same goes for WDS. I’ll live vicariously through pics, tweets, and recaps.I’ll definitely be on the lookout for that interview on CBS.Look forward to hearing more about the book proposal if it turns into something cool.Exciting stuff and I know it’ll only get better. Reply

  11. I KNOW RIGHT!!! I DON’T HAVE AN IPAD OR FACEBOOK!!! I HOPE THYE PUT IT ON THE IPOD, CUZ I’M GETTING ONE 4 MY BIRTHDAY! BY THE WAY, I WILL FRIEND YOU ON WEBKINZ. – 9t6t

  12. Really trustworthy blog. Please keep updating with great posts like this one. I have booked marked your site and am about to email it to a few friends of mine that I know would enjoy reading..

  13. . Your favorite justification appeared to be on the internet the simplest thing to be aware of. I say to you, I definitely get irked while people consider worries that they just don’t know about. You managed to hit the nail upon the top as well as defined out the whole thing without having side-effects , people can take a signal. Will likely be back to get more. Thanks

  14. I’m now not certain the place you are getting your information, but great topic. I needs to spend a while learning more or working out more. Thank you for excellent info I was on the lookout for this info for my mission.

  15. This is one beautiful watch. Mine is 0330 Gold Arsenal and it constantly reminds you that you’re wearing it…it is HEAVY! I have 2 other Invecta’s that I love. If Invecta came out with all black and a black and rose gold Arsenal…I’d buy both in a heartbeat.

  16. Hi AprilIf a Canon is too expensive, look at a Yongnuo 465 for example, that’s the lowest cost entry into the ETTL world. For a bigger budget, the Nissin Di622 Mark II is an interesting offer.

  17. Kibic Polski pisze:1/Wisła ma najlepszych kibiców w Polsce, ale Kielce pokazały na FF, że są w stanie się do nich zbliżyc poziomem /ostatni mecz w Kielcach niestety kibice Vive „zburaczyli”, ale może się do finału PO ucywilizują?/2/ Vive ma najsilniejszą drużynę, ale Wisła pokazała w ostatnim meczu, że jest w stanie powalczyc.Jeżeli 1/ dodac do 2/, to = szykuje się Finał Play-Off, jakiego jeszcze nie oglądaliśmy ! Oby…Pozdrawiam Jednych i Drugich, do zobaczenia na Play-Off !!

  18. oh and I forgot to mention, another way for google to make money? Oh yeah, because they charge us loads to use all their website… Oh wait, they're free..They have to make money somehow, so even if they did make $1/2 off this, why complain, simply dont buy them?

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>