## Algorithm

Problem Name: 2 AD-HOC - beecrowd | 1266

# Tornado!

By Ricardo Anido  Brazil

Timelimit: 1

Is this crazy weather the result of mankind's continuous interference in the environment? Or is it simply the normal cycle of climate changes through the ages? No one seems to know for sure, but the fact is that natural phenomena such as tornadoes and hurricanes have been hitting our country with more force and frequence than in past decades.

One tornado has just hit Silverado Farm, a cattle and milk producer, and made havoc. The barn roof was torn, several trees were uprooted, the farm truck was overturned... But the worst thing is that the tornado destroyed several sections of the fence that surrounded the property. The fence was very well built, with concrete posts every two meters, and barbed wire enclosing the whole farm perimeter (the perimeter, in meters, is an even number, making the fence perfectly regular).

Now several posts are broken or missing, and there are gaps in the fence. To prevent the cattle from getting out of the property, the fence must be restored as quickly as possible. Reconstructing the fence to its original form, with concrete posts, will take a long time. In the meantime, the farm owners decided to close the gaps with a temporary fence, made with wooden posts. Wooden posts will be placed in exactly the same spots where missing/broken concrete posts were/are. However, in order to make the temporary reconstruction faster and less expensive, the owners decided to use fewer posts: a wooden post will be used to replace a missing/broken concrete post only if the length of the barbed wired needed to close the distance to the next post (wooden or concrete) exceeds four meters.

Given the description of which posts are missing/broken, you must write a program to determine the smallest number of wooden posts needed to close all the gaps in the fence, according to the owners' decision.

## Input

The input contains several test cases. The first line of a test case contains one integer N indicating the number of original concrete posts in the fence (5 ≤ ≤ 5000). The second line of a test case contains N integers Xi indicating the state of each concrete post after the tornado (0 ≤ Xi ≤ 1 for 1 ≤ i ≤ N) . If Xi = 1 post i is in good condition, if Xi = 0 post i is broken or missing. Note that post N is next to post 1. The end of input is indicated by N = 0 .

## Output

For each test case in the input your program must produce one line of output, containing an integer indicating the smallest number of wooden posts that are needed to restore the fence, according to the owners' decision.

 Sample Input Sample Output 10 1 0 0 1 0 0 1 0 1 1 11 1 0 0 1 0 0 0 1 1 0 1 12 0 0 0 0 0 1 1 0 0 0 1 1 0 2 2 3

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i  < = b; ++i)
#define RFOR(i, b, a) for (int i = b; i >= a; --i)
#define REP(i, N) for (int i = 0; i  <  N; ++i)
#define MAX 5010
#define pb push_back
#define mp make_pair

using namespace std;

int cerca[MAX];

int main()
{
int n;
while (scanf("%d", &n) && n) {
int ft = false;
REP(i, n)
scanf("%d", &cerca[i]);
if (cerca[0] == 0)
ft = true;
vector<int> dist;
if (ft) {
int j = n - 1;
while (cerca[j] == 0 && j >= 0)
j--;
if (j  <  0) {
if (n * 2 % 4 == 0)
printf("%d\n", (n * 2) / 4);
else
printf("%d\n", (n * 2) / 4 + 1);
} else {
int soma = 0, count = 0;
while (count  <  n) {
if (cerca[j] == 0) {
soma += 2;
while (count < n && cerca[j] == 0) {
soma += 2;
if (j == n - 1)
j = 0;
else
j++;
count++;
}
if (soma > 4)
dist.pb(soma);
soma = 0;
}
if (j == n - 1)
j = 0;
else
j++;
count++;
}
int resp = 0;
REP(i, dist.size())
if (dist[i] % 4 == 0)
resp += (dist[i] / 4 - 1);
else
resp += dist[i] / 4;
printf("%d\n", resp);
}
} else {
int soma = 0;
REP(i, n)
if (cerca[i] == 0) {
soma += 2;
while (i  <  n && cerca[i] == 0) {
soma += 2;
i++;
}
if (soma > 4)
dist.pb(soma);
soma = 0;
}
int resp = 0;
REP(i, dist.size())
if (dist[i] % 4 == 0)
resp += (dist[i] / 4 - 1);
else
resp += dist[i] / 4;

printf("%d\n", resp);
}
}
return 0;
}
``````
Copy The Code &

Input

cmd
10
1 0 0 1 0 0 1 0 1 1
11
1 0 0 1 0 0 0 1 1 0 1
12
0 0 0 0 0 1 1 0 0 0 1 1
0

Output

cmd
2
2
3

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
while True:
n = int(input())
if not n: break
print((input()+' ').replace('0 0 ', '* ').count('*'))

``````
Copy The Code &

Input

cmd
10
1 0 0 1 0 0 1 0 1 1
11
1 0 0 1 0 0 0 1 1 0 1
12
0 0 0 0 0 1 1 0 0 0 1 1
0

Output

cmd
2
2
3
Advertisements