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.

2,402 thoughts on “Escada perfeita (OBI2006)

  1. Lyfa là em gái Kirito đấy ( đọc LN chưa mà phán bậy thế ) nghĩ sao lại nói bỏ asuna , Kirito vào ALO chủ yếu là tìm asuna mừ .

  2. I must voice my passion for your kind-heartedness giving support to men and women that have the need for help on in this matter. Your special commitment to getting the solution across appears to be quite good and have always permitted ladies much like me to get to their endeavors. Your warm and friendly facts indicates so much to me and further more to my mates. Best wishes; from everyone of us.

  3. nós brasileiros ainda vamos pagar uma conta elevada. A dívida que o 51 contraiu e ninguem sabe onde parou este dinheiro. 0 fato é que o mantega está pagando horrores em juros e amortização. E na época soprou aos 4 ventos – que estamos emprestando dinheiro as FMI. É a história da mulher que comprava a duzia de óvos por 11 e vendia por 10 – mas como vendia muito…….

  4. Sometimes I think that Steve is writing about obvious facts that almost all of us know (except maybe those who go to Harvard and Yale and have never mixed with regular people) but that we all pretend for good reason do not exist. But in cases like this it seems that the pretending does become a negative rather than a positive and thus it is good that he writes about them.

  5. I’m impressed, I must say. Really rarely do I encounter a blog that’s both educative and entertaining, and let me tell you, you may have hit the nail on the head. Your concept is excellent; the difficulty is one thing that not enough people are talking intelligently about. I am very completely happy that I stumbled across this in my search for one thing referring to this.

  6. Have you ever considered the possibility that T. Boone Pickens has not yet shared his whole plan? After all, the man is a very sharp operator and he is from Texas, the land of poker players.Here is a link to an article that I wrote about his plan that might give you some food for thought:

  7. I’ve observed that in the world these days, video games are classified as the latest popularity with kids of all ages. Occasionally it may be impossible to drag the kids away from the video games. If you want the best of both worlds, there are numerous educational video games for kids. Interesting post.

  8. cialis pas chere|cialis non|cialis et psa|cialis professional pharmacy|il costo di walmart cialis|best site cialis soft uk|cialis tadalafil 20m original|how long can you take cialis|cialis ber hausarzt|cialis order mastercard|cialis keine ejakulation|buy cheap cialis softtabs|cialis 20 mg 12 compresse|cialis ventas genricas|discount cialis from canada|cialis funziona forum|cialis online no presription|cialis rezeptfrei per rechnung|generisk cialis|is cialis 200mg real|canada cialis generic online|le cialis levitra|farmacia di usa per cialis|medicare drug discount cialis|cheap cialis tablets|no rx female cialis online|cialis mas alcohol|cialis originale acquist|paquetes de muestra de cialis|cialis generika preise|cialis 10mg side effects|enter site get cialis cheap|farmacia de india cialis|cialis in singapore delivery|cialis jelly overnight|buy cialis 25 mg|cialis purchase|can buy cialis australia|precio de cialis 5 mg|visit web site buy cialis uk|cialis farmaco etico|cialis bucodispersable|only best offers no rx cialis|cialis hchstdosis|how to buy discount cialis|cialis 5 mg acquisto online|cialis le meilleur effet|cialis tabletas for sale|preiswertes cialis 5 mg|cialis online de|cialis pharmacie france|woman testimonial of cialis|cialis espaa|50 mg of cialis|cialis generico precio mexic|precios cialis online|ordinare cialis on line|cialis on purchse|cialis doesage|online pharmacy cialis buy|cialis 10 mg einnehmen|cialisw|cialis 5 vidal|usefull link cialis c 50|only now genuine cialis online|achat cialis original lign|lilly cialis sales|cialis compared|light orange cialis pills|buy some cialis|click here liquid cialis|how to get cialis in australia|generic cialis farmacia|best site to buy brand cialis|cialis pldoras suaves|sante canada cialis|just try cialis med store|cialis europe pharmacy|price walgreens cialis|visit our site cialis soft gel|cheap cialis with prescription|comprar cialis en linea mexico|comprar cialis bogota|try it real cialis for sale|orden de los cialis|venta de cialis argentina|where to buy cialis 100|cialis generico funciona|direct meds buy cialis usa|cialis farmacia meritxell|hay algun generico cialis|compra cialis generico online|cialis sale in malaysia|click here cialis to buy|genuine 5mg cialis|cialis pharmacie moins cher|the best place cialis no rx|barato cialis suave|apcalis cialis|cialis generic difference|cialis sans ordonnance 50mg|cialis per levitr|wie viel cialis|costo cialis nelle farmacie|only here order cialis online|user cialis|cialis utilisatio|best prices generic cialis|cialis duree de vie|cialis us sin|rabatt cialis online|cialis discontinued|cialis di ordine britannici|buy cialis online order|cialis generico en tijuana|cialis 5mg bayer|cialis hondura|generic cialis online cheap|comprare cialis internet|cose il cialis generico|cialis 200mg pills price|compre cialis muy barato|fda approved cialis|5 mg cialis every other day|cialis 20mg original preis|overnight canadian cialis|cialis similar|cialis daily use benefits|usefull link pharmacy cialis|cialis 20 generika|cialis vasodilatator|cialis gnrique forum|effet cialis naturel|cialis uk online sales|cialis 20mg test|try it prescription cialis|cialis in apotheke|cialis daily generic|cialis discussion|cialis garantito|como se usa o cialis|non generic cialis price|look here cialis sale|cialis 20mg how to|cost for one cialis pill|elilly cialis 5mg price in uk|lilly cialis compra|cialis 5mg best pricewalmart|what do cialis best price|how to you purchase cialis|potenzmittel cialis paypal|only now buy cialis china|pacchi campione cialis liberi|cialis priligy zusammen|we use it cialis 50mg|cialis spedizione rapida|cialis non funziona pi|when will generic cialis|we like it get cialis cheap|cialis blutdruck|canadian cialis super active|brand cialis buy online|buy cialis soft tablets|buy cialis africa|generic cialis kamagra|eli lilly cialis 20m|visit web site cialis no rx|kann man cialis gunstig kaufen|con la rx online cialis|el cialis sin recet|cialis 25mg generic|only here get cialis cheap|cialis coupon phone number|pharmacy online u k cialis|cialis sold in canada|cialis 10mg apotheke|cialis professional uk|cialis boite de 28|just try cialis brand name|singular cialis|comparatif cialis levitra|cialis 5mg gnstig kaufen|cialis cheapest price uk|cialis australia cheap|cialis im internet kaufen|cialis halbe tablette|cialis vente particulie|cialis price guide sa|cialis 20 pharmacie|cialis virkemte|buy cialis in barcelona spain|cialis bestellen rechnung|dosaggi cialis|compren cialis|cialis cost 20|average cost cialis 20mg|buy cialis tablets from uk|purchase cipla cialis|acquisto cialis veloce|achat de taureau de cialis|best site to buy cialis online|cialis 10 mg compresse|info cialis|uk supplied soft tab cialis|cialis the in|cialis 10mg dosag|look here canada cialis|cialis prezzi farmaci|enter site buy cialis 50 mg|acheter cialis foru|cialis sale nz|comprar cialis generica espana|cialis 20 mg colombia|www cialis com generic|costo farmacia 5 cialis|achat cialis le mexique|cialis tadalafil pills c50|aggression and cialis|the best site 50 mg cialis|we like it cialis testimonial|vendita cialis ne|recensioni cialis online|cialis high blood pressure|dove trovare cialis generico|we like it cialis to buy|the best choice cialis canda|cialis for erection|order cialis online generic|cialis deutchland venta|cialis essen|cialis acheter in antwerpen|try it discount online cialis|le cialis forum|low cost canadian cialis|how much cialis|cialis for females|niedrige preise fr cialis|costo cialis nelle farmacie|cialis super active generic|acheter cialis 20 m|cialis scadut|cialis se vende con receta|cialis 30 ans|uk pharmacy cialis online|normal dose of cialis|we use it where to find cialis|kosten cialis rezep|40mg generic cialis|cialis online pagamento paypal|linguette di cialis

    [url=http://cialisindiansq.com/]buy cialis[/url]
    indian cialis

    cialis pas chere|cialis non|cialis et psa|cialis professional pharmacy|il costo di walmart cialis|best site cialis soft uk|cialis tadalafil 20m original|how long can you take cialis|cialis ber hausarzt|cialis order mastercard|cialis keine ejakulation|buy cheap cialis softtabs|cialis 20 mg 12 compresse|cialis ventas genricas|discount cialis from canada|cialis funziona forum|cialis online no presription|cialis rezeptfrei per rechnung|generisk cialis|is cialis 200mg real|canada cialis generic online|le cialis levitra|farmacia di usa per cialis|medicare drug discount cialis|cheap cialis tablets|no rx female cialis online|cialis mas alcohol|cialis originale acquist|paquetes de muestra de cialis|cialis generika preise|cialis 10mg side effects|enter site get cialis cheap|farmacia de india cialis|cialis in singapore delivery|cialis jelly overnight|buy cialis 25 mg|cialis purchase|can buy cialis australia|precio de cialis 5 mg|visit web site buy cialis uk|cialis farmaco etico|cialis bucodispersable|only best offers no rx cialis|cialis hchstdosis|how to buy discount cialis|cialis 5 mg acquisto online|cialis le meilleur effet|cialis tabletas for sale|preiswertes cialis 5 mg|cialis online de|cialis pharmacie france|woman testimonial of cialis|cialis espaa|50 mg of cialis|cialis generico precio mexic|precios cialis online|ordinare cialis on line|cialis on purchse|cialis doesage|online pharmacy cialis buy|cialis 10 mg einnehmen|cialisw|cialis 5 vidal|usefull link cialis c 50|only now genuine cialis online|achat cialis original lign|lilly cialis sales|cialis compared|light orange cialis pills|buy some cialis|click here liquid cialis|how to get cialis in australia|generic cialis farmacia|best site to buy brand cialis|cialis pldoras suaves|sante canada cialis|just try cialis med store|cialis europe pharmacy|price walgreens cialis|visit our site cialis soft gel|cheap cialis with prescription|comprar cialis en linea mexico|comprar cialis bogota|try it real cialis for sale|orden de los cialis|venta de cialis argentina|where to buy cialis 100|cialis generico funciona|direct meds buy cialis usa|cialis farmacia meritxell|hay algun generico cialis|compra cialis generico online|cialis sale in malaysia|click here cialis to buy|genuine 5mg cialis|cialis pharmacie moins cher|the best place cialis no rx|barato cialis suave|apcalis cialis|cialis generic difference|cialis sans ordonnance 50mg|cialis per levitr|wie viel cialis|costo cialis nelle farmacie|only here order cialis online|user cialis|cialis utilisatio|best prices generic cialis|cialis duree de vie|cialis us sin|rabatt cialis online|cialis discontinued|cialis di ordine britannici|buy cialis online order|cialis generico en tijuana|cialis 5mg bayer|cialis hondura|generic cialis online cheap|comprare cialis internet|cose il cialis generico|cialis 200mg pills price|compre cialis muy barato|fda approved cialis|5 mg cialis every other day|cialis 20mg original preis|overnight canadian cialis|cialis similar|cialis daily use benefits|usefull link pharmacy cialis|cialis 20 generika|cialis vasodilatator|cialis gnrique forum|effet cialis naturel|cialis uk online sales|cialis 20mg test|try it prescription cialis|cialis in apotheke|cialis daily generic|cialis discussion|cialis garantito|como se usa o cialis|non generic cialis price|look here cialis sale|cialis 20mg how to|cost for one cialis pill|elilly cialis 5mg price in uk|lilly cialis compra|cialis 5mg best pricewalmart|what do cialis best price|how to you purchase cialis|potenzmittel cialis paypal|only now buy cialis china|pacchi campione cialis liberi|cialis priligy zusammen|we use it cialis 50mg|cialis spedizione rapida|cialis non funziona pi|when will generic cialis|we like it get cialis cheap|cialis blutdruck|canadian cialis super active|brand cialis buy online|buy cialis soft tablets|buy cialis africa|generic cialis kamagra|eli lilly cialis 20m|visit web site cialis no rx|kann man cialis gunstig kaufen|con la rx online cialis|el cialis sin recet|cialis 25mg generic|only here get cialis cheap|cialis coupon phone number|pharmacy online u k cialis|cialis sold in canada|cialis 10mg apotheke|cialis professional uk|cialis boite de 28|just try cialis brand name|singular cialis|comparatif cialis levitra|cialis 5mg gnstig kaufen|cialis cheapest price uk|cialis australia cheap|cialis im internet kaufen|cialis halbe tablette|cialis vente particulie|cialis price guide sa|cialis 20 pharmacie|cialis virkemte|buy cialis in barcelona spain|cialis bestellen rechnung|dosaggi cialis|compren cialis|cialis cost 20|average cost cialis 20mg|buy cialis tablets from uk|purchase cipla cialis|acquisto cialis veloce|achat de taureau de cialis|best site to buy cialis online|cialis 10 mg compresse|info cialis|uk supplied soft tab cialis|cialis the in|cialis 10mg dosag|look here canada cialis|cialis prezzi farmaci|enter site buy cialis 50 mg|acheter cialis foru|cialis sale nz|comprar cialis generica espana|cialis 20 mg colombia|www cialis com generic|costo farmacia 5 cialis|achat cialis le mexique|cialis tadalafil pills c50|aggression and cialis|the best site 50 mg cialis|we like it cialis testimonial|vendita cialis ne|recensioni cialis online|cialis high blood pressure|dove trovare cialis generico|we like it cialis to buy|the best choice cialis canda|cialis for erection|order cialis online generic|cialis deutchland venta|cialis essen|cialis acheter in antwerpen|try it discount online cialis|le cialis forum|low cost canadian cialis|how much cialis|cialis for females|niedrige preise fr cialis|costo cialis nelle farmacie|cialis super active generic|acheter cialis 20 m|cialis scadut|cialis se vende con receta|cialis 30 ans|uk pharmacy cialis online|normal dose of cialis|we use it where to find cialis|kosten cialis rezep|40mg generic cialis|cialis online pagamento paypal|linguette di cialis

  9. 蘇淇寬回應說﹕「就算在陸佑堂晚宴,每人也要花200多元訂到會,晚宴支出差不多。但在酒店舉行可有一個嚴肅、隆重的場合體驗,我們已『格價』到最便宜的!」原來大學嘅禮堂(陸佑堂)喺冇酒店咁嚴肅隆重。。。。可想而知,這位仁兄,是怎樣看待自己的大學。"該系二年級生 Ivy 說,去年首次參與這類盛大晚宴,需穿上晚裝與參加者交際和跳舞,感到十分新鮮,更對籌辦學長另眼相看。"哈哈,難怪"訂金暫由幹事用存款或向家人借款墊支。"

  10. I and my pals were checking the best suggestions found on your site and then I had an awful feeling I had not expressed respect to the web blog owner for them. All of the women became so excited to read through all of them and have now without a doubt been enjoying these things. Thank you for simply being quite considerate and for considering these kinds of fabulous topics millions of individuals are really needing to be aware of. My personal sincere regret for not expressing gratitude to earlier.

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>