Algorithm


Problem Name: 2 AD-HOC - beecrowd | 1266

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/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 & Try With Live Editor

Input

x
+
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

x
+
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 & Try With Live Editor

Input

x
+
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

x
+
cmd
2
2
3
Advertisements

Demonstration


Previous
#1252 Beecrowd Online Judge Solution 1252 Sort! Sort!! And Sort!!! - Solution in C, C++, Java, Python and C#
Next
#1267 Beecrowd Online Judge Solution 1267 Pascal Library Solution in C, C++, Java, Js and Python