Início Inscrições Informações Gerais Regulamento Pratique Contato Resultados Mapa do Conteúdo

 Você está visitando: Início > Olimpíada Brasileira de Informática > Pratique > Modalidade Iniciação >
                                            > Nível 2

 

Tornado

Será que este clima maluco é o resultado da contínua interferência da humanidade no meio ambiente? Ou é simplesmente um ciclo normal, que acontece desde as eras remotas? Ninguém parece saber por certo, mas o fato é que fenômenos naturais como tornados e enchentes têm atingido nosso país com mais força e freqüÂência do que em décadas passadas. Um tornado acabou de atingir a Fazenda Boa Vista, que produz leite e carne, e causou grande destruiçÂão. O telhado da sede foi afetado, diversas árvores arrancadas, o trator foi tombado pelo vento... Mas a pior coisa que aconteceu foi que o tornado destruiu diversas seçÂões da cerca que circundava a propriedade. A cerca era muito bem construída, com postes de concreto a cada dois metros, e arame farpado cercando todo o perímetro da fazenda (o perímetro, em metros, é um número par, de forma que a cerca era perfeitamente regular).

Agora diversos postes estão quebrados ou simplesmente sumiram, levados pela força do vento, deixando vãos abertos na cerca. Para evitar que o gado saia da propriedade, a cerca deve ser restaurada o mais breve possível. No entanto, a reconstruçÂão nos mesmos padrões anteriores vai levar muito tempo; como soluçÂão provisória, os donos da fazenda decidiram fechar os vãos com uma cerca temporária, feita com postes de madeira. Os postes de madeira serão colocados exatamente nos mesmos lugares onde postes quebrados ou faltantes estavam. Além disso, para permitir uma reconstruçÂão mais rápida e menos custosa, os donos decidiram utilizar menos postes do que a cerca original: um poste de madeira será utilizado para repor um poste de concreto quebrado ou faltante apenas se o comprimento do arame farpado necessário para fechar o vão até o próximo poste (de madeira ou concreto) exceder quatro metros.

Tarefa

Dada a descriçÂão de quais postes originais estão quebrados ou faltando, você deve determinar o menor número de postes de madeira serão necessários para reconstruir a cerca de acordo com a decisão dos donos da fazenda.

Formato dos Testes

Cada caso de teste considera um mapa de danos, que consiste de uma seqüÂência de valores 0 e 1, representando o estado de cada poste de concreto após o tornado. O valor 0 indica que o poste respectivo está quebrado ou faltando, e o valor 1 indica que o poste está em bom estado. Note que o último valor da seqüÂência indica um poste que está contíguo ao poste representado pelo primeiro valor.

Exemplos

Caso de TesteResultado
1001011
000003
101110

Questão 1. Se o mapa de danos for 001010111000001000 o menor número de postes de madeira a serem utilizados é

2
3
1
4
5

Questão 2. Se o mapa de danos for 110011 o menor número de postes de madeira a serem utilizados é

1
0
2
3
4

Questão 3. Se o mapa de danos for 001101 o menor número de postes de madeira a serem utilizados é

2
0
1
4
3

Questão 4. Se o mapa de danos for 000010010 o menor número de postes de madeira a serem utilizados é

3
4
1
0
2

Questão 5. Se o mapa de danos for 100101001000 o menor número de postes de madeira a serem utilizados é

4
1
3
2
0

Questão 6. Se o mapa de danos for 100101001000 o menor número de postes de madeira a serem utilizados é

0
3
2
4
1

Questão 7. Se o mapa de danos for 00010010 o menor número de postes de madeira a serem utilizados é

3
2
1
4
0

 

Apoio: Unicamp Patrocínio: Fundação Carlos Chagas Promoção: SBC