using System;
using System.Diagnostics;

namespace ConsoleApp3
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] a;

            var random = new Random();
            int n = 10;
            a = new int[n];

            for (int i = 0; i < n; i++)
            {
                a[i] = random.Next(3);
            }

            //a = new[] {1,0,2};
            Console.WriteLine(string.Join(",", a));

            Stopwatch stopwatch = new Stopwatch();
            stopwatch.Start();
            Console.WriteLine("brute: {0}", Brute(a));
            stopwatch.Stop();
            Console.WriteLine($"brute took {stopwatch.ElapsedMilliseconds} ms");
            Console.ReadKey();
        }

        private static int Brute(int[] a)
        {
            int n = a.Length;
            bool[] activated = new bool[n];

            int min = n;

            int i = 0;
            for(;;)
            {
                bool coversAll = true;
                for (int probe = 0; probe < n; probe++)
                {
                    bool covers = false;
                    for (int k = 0; k < n; k++)
                    {
                        if (activated[k] && probe >= k - a[k] && probe <= k + a[k])
                        {
                            covers = true;
                            break;
                        }
                    }

                    if (!covers)
                    {
                        coversAll = false;
                        break;
                    }
                }

                if (coversAll)
                {
                    int m = 0;
                    for (int k = 0; k < n; k++)
                    {
                        if (activated[k]) m++;
                    }

                    if (m < min) min = m;
                }

                if (!activated[i])
                {
                    activated[i] = true;
                }
                else
                {
                    while (i < n && activated[i])
                    {
                        activated[i++] = false;
                    }

                    if (i >= n)
                    {
                        break;
                    }
                    activated[i] = true;
                    i = 0;
                }
            }

            return min;
        }
    }
}