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. I looove meatballs! here in Italy are quite popular, made in thousands of ways… I like your recipe! and they looks delicious! thank you for your visit! I follow you! Ciao from Italy!ps the name of your blog reminds me of a movie with Barbra Straisand "Mirror has two faces" where when eating she used to make the perfect bite with her fork!

  2. Hy again, well I have 5 months after the break out with my girlfriend, son since the last time I see her she told me that she dont love me anymore and i dont like me, so its that right? and since that 5 months I dont have comunication with her is she call me o find me? thanx.

  3. Dans mon dernier livre (2012-2016, CINQ ANNÉES QUI VONT CHANGER LE MONDE, XO) qui contient-entre autres- l’analyse geopolitico-astrologique de nbx. pays, je parle d’un climat révolutionnaire qui va agiter la Chine en 2014-2014… Ça bouillonne déjà!

  4. Saila: Ei ihme, että pelottaa kun on kaupungin pisimpiin lukeutuvat liukuportaat kyseessä ja ihmisiä pyörii joka puolella. Meidän pikku leopardi maukui kyllä aika kovaa, kun se siinäkin hälinässä kuului melkoisen hyvin.Naukulan Mamma ja ella: Enpä tiedä miten onnistuisi yhtään minnekään reissaaminen enemmän kuin yhden kissan kanssa – siinä yksi syy, miksi Mindy on ainokainen. Mindy ei mitenkään yrittänyt päästä takaisin pihalle, vaikka siellä varmasti viihtyi.

  5. Hi, was wondering if you are in love with Karen? Can lust bring you so far to Australia? Anyway you make me laugh… good sense of humour for a guy! But I censor all the swear words la! Post more ok!

  6. Nagyon jók a párnák!!! :) ) Hasonlót képzeltem el, de persze kép formában párnára, táskára. Meg persze felnőttebb verseket. Nem úgy néz ki, de remélem hamarosan nekikezdhetek az egyik kedvencemnek. :)

  7. No homo but that dress was just “aight”. ======================================================================= I ain’t going there; but I do know shorty wop’s best suit is her B-Day Suit. Dat Arse is 1st Clarse —————————————— THIS

  8. After research a couple of of the weblog posts in your website now, and I actually like your way of blogging. I bookmarked it to my bookmark website listing and shall be checking again soon. Pls take a look at my web page as nicely and let me know what you think.

  9. Es cierto que la libertad, la energía y la belleza que irradia el mar no tiene comparación posible…pero las dos últimas imágenes muestran unas piscinas totalmente diferentes y sumamente apetecibles para momentos como los de hoy en los que el calor se deja notar excesivamente.Feliz tarde también para ti Cecilia ,no importa donde …en la playa ,en la piscina ,haciendo maletas o con un grupo de amigas ….,lo importante es ser feliz.Un abrazo enorme.

  10. I’ve been surfing online more than 3 hours today, yet I never found any interesting
    article like yours. It’s pretty worth enough for me. Personally, if all
    web owners and bloggers made good content as you did, the internet will be a lot more useful
    than ever before.

  11. Gretchen,Congratulations on your new book. I loved the one on Rankin. You shared it in Ann Whitford Paul's class.I plan to be at HIGHLIGHTS for the session on YA and Non Fiction. Larry Dane Brimner and Carolyn Yoder will be there. Your comments make it even more exciting.Who is next on your subject list?

  12. DinkerTinker My point here is that you need money when you lose a job. Being debt free doesn’t help you. The proper financial goal is to accumulate assets, not just merely eliminate debt.

  13. I have discovered some considerations through your blog post. One other thing I would like to talk about is that there are plenty of games out there designed especially for toddler age little ones. They consist of pattern acknowledgement, colors, animals, and patterns. These typically focus on familiarization as opposed to memorization. This makes little ones occupied without experiencing like they are learning. Thanks

  14. Hola,Me ha gustado mucho el artículo, pero quería hacer incapié en dos cuestiones.1- ¿No hay ningún apartado de la tarificación eléctrica que considere los armónicos?.2- Con lo único que no estoy de acuerdo, es cuando dices que nuestro sistema eléctrico está sobredimensionado. Creo que gran parte de las redes transporte y distribución de nuestro país funcionan a su máxima capacidad.

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>