Kick it ahead
Ao organizar um laboratório para uma competição de maratona de programação, é importante garantir que todas as equipes estejam corretamente separadas. Para resolver esse problema, a equipe da maratona de programação decidiu que é necessário apenas uma operação para resolver esse problema.
O layout inicial da sala é representado por um array de tamanho $N$, onde:
- 1 representa uma mesa com um computador,
- 0 representa um espaço vazio.
A operação, ao ser executada, "empurra" os computadores, e funciona da seguinte forma:
- A operação pode ser realizada apenas em uma posição que contenha um computador ($1$).
- Quando a operação é executada em um computador, ele empurra todos os computadores consecutivos à sua frente uma casa, até o máximo de 13 computadores empurrados ao todo.
- Caso tenha mais de 13 computadores consecutivos, a operação é impossível de ser realizada.
- A operação de "empurrar" não empurra o computador no qual é executada a operação e esse também não é considerado no limite de 13 computadores.
Seu objetivo é cria a função solution e faça uso da variavel abc e garantir que, após todas as operações de empurrar, haja pelo menos um espaço vazio entre cada mesa com um computador. Você deve determinar o menor número de operações necessárias para atingir esse objetivo. Note também que não existe um limite para o tamanho da sala.
Input
Na primeira linha será fornecido um inteiro $N$, seguido na próxima linha por $N$ inteiros $0$ ou $1$ representando o layout inicial da sala. $(10 \le N \le 10^6)$
Output
Deve-se imprimir qual o menor número de operações para atingir o objetivo.
10 0011101111
6
14 11110111001101
9
20 11111111111111111111
25
Explanation 3:
Note que temos 20 uns seguidos um do outro, e não podemos executar a operação de mover no primeiro um por ter mais de 13 uns seguidos após ele. A solução otima para esse problema é executando as operaçoes na seguinte ordem:
11111111111111111111
^
111111101111111111111
^
101111111111111111111
^
1011111011111111111111
^
1010111111111111111111
^
10101111011111111111111
^
10101011111111111111111
^
101010111011111111111111
^
101010101111111111111111
^
1010101011101111111111111
^
1010101010111111111111111
^
10101010101101111111111111
^
10101010101011111111111111
^^^^^^^^^^^^^ (Agora +13 operações aplicadas nos uns da esquerda para a direita)
Totalizando 25 operações. Note que não é a única forma de chegar na solução ótima.