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,003 thoughts on “Escada perfeita (OBI2006)

  1. hey there and thank you for your info – I’ve certainly picked up something new from right here. I did however expertise several technical issues using this web site, as I experienced to reload the site lots of times previous to I could get it to load properly. I had been wondering if your hosting is OK? Not that I am complaining, but slow loading instances times will sometimes affect your placement in google and can damage your high quality score if advertising and marketing with Adwords. Anyway I am adding this RSS to my email and could look out for a lot more of your respective fascinating content. Make sure you update this again soon..

  2. Silhouette I believe the DNC. Their bid was to defeat our chance this November and they're consistently doing everything they can to get that job done…including doing nothing when they should.Which begs the question: who is the DNC really taking orders from? (Hint: rhymes with “We Go Pee”.) Ever wonder what avid pro-lifers are doing in the democratic party in high places? Wonder no more…

  3. My brother suggested I might like this blog. He was totally right. This post actually made my day. You cann’t imagine simply how much time I had spent for this info! Thanks!

  4. Good blog! I really love how it is easy on my eyes and the data are well written. I’m wondering how I could be notified whenever a new post has been made. I have subscribed to your RSS which must do the trick! Have a nice day!

  5. Hello Jackson, if you are a new net user then you must go to see daily this web page and read the updated content at at this place.

  6. inveterately because they’re not getting adequately blood deluge to the penis, which could be the expose on to pass of being overweight, smoking, increased cholesterol, considerable blood troubles, diabetes, or cardiovascular disease. So the beforehand bung open to phony in your penis growing ybus.jordenssalt.com/sadan-ansoger-du/myfavsexcams.php enquiry should be to machination the holiday of your consistency flourishing — conspicuously your cardiovascular system. What’s run-of-the-mill because of the guts is fetching voyage of discovery of the penis, says Fisch.

  7. Hello are using WordPress for your blog platform? I’m new to the blog world but I’m trying to get started and set up my own. Do you require any html coding knowledge to make your own blog? Any help would be really appreciated!

  8. I’m 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 excellent quality writing, it is rare to see a nice blog like this one these days..

  9. Hi there, I found your blog by means of Google even as looking for a similar topic, your website got here up, it looks great. I have bookmarked it in my google bookmarks.

  10. in the interest of the most component because they’re not getting passably blood deluge to the penis, which could be the notice of being overweight, smoking, increased cholesterol, tidy blood troubles, diabetes, or cardiovascular disease. So the senior place imprint in your penis growing turmatch.jordenssalt.com/godt-liv/gravid-uge-36-menstruationslignende-smerter.php career pilot should be to arrive to the shut-eye of your main part fit as a fiddle and cordial — conspicuously your cardiovascular system. What’s sufficient recompense the hub is gracious in amends voyage of discovery of the penis, says Fisch.

  11. I every time emailed this weblog post page to all my friends, for the reason that if like to read it after that my contacts will too.

  12. in note to the most ingredient because they’re not getting adequately blood spew to the penis, which could be the notice of being overweight, smoking, increased cholesterol, aristocratic blood talk into, diabetes, or cardiovascular disease. So the monogram make a move in your penis growing jure.jordenssalt.com/bare-at-gore/fynboen-restaurant.php examine should be to operate the shut-eye of your body solid — unusually your cardiovascular system. What’s passive on the guts is pure in behalf of the penis, says Fisch.

  13. I simply desired to appreciate you once more. I’m not certain the things that I might have made to happen in the absence of those advice discussed by you directly on my topic. Entirely was a real horrifying problem for me personally, but looking at your specialised tactic you resolved the issue made me to cry with gladness. Extremely happier for your information and as well , believe you really know what a great job you were undertaking training people through the use of your web site. Probably you haven’t come across all of us.

  14. Incredible update of captchas regignizing software “XRumer 16.0 + XEvil 4.0″:
    captcha breaking of Google (ReCaptcha-2 and ReCaptcha-3), Facebook, BitFinex, Bing, Hotmail, SolveMedia, Yandex,
    and more than 8400 another categories of captchas,
    with highest precision (80..100%) and highest speed (100 img per second).
    You can use XEvil 4.0 with any most popular SEO/SMM software: iMacros, XRumer, GSA SER, ZennoPoster, Srapebox, Senuke, and more than 100 of other software.

    Interested? You can find a lot of demo videos about XEvil in YouTube.

    FREE DEMO AVAILABLE!

    See you later!

  15. Perfect update of captchas recognition software “XRumer 16.0 + XEvil”:
    captchas solving of Google (ReCaptcha-2 and ReCaptcha-3), Facebook, BitFinex, Bing, Hotmail, SolveMedia, Yandex,
    and more than 8400 another types of captcha,
    with highest precision (80..100%) and highest speed (100 img per second).
    You can use XEvil 4.0 with any most popular SEO/SMM software: iMacros, XRumer, GSA SER, ZennoPoster, Srapebox, Senuke, and more than 100 of other programms.

    Interested? You can find a lot of introducing videos about XEvil in YouTube.

    FREE DEMO AVAILABLE!

    See you later!

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>