Cod sursa(job #2454815)

Utilizator dragostanTantaru Dragos Constantin dragostan Data 9 septembrie 2019 21:22:12
Problema A+B Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <iostream>
#include <algorithm>

using namespace std;
const int DIM = 1001;

int sir[DIM], heat[DIM];
int n, power;

void colorAll(int);
int findNextOneR(int);
int findNextOneL(int);
int main()
{
	cin >> n >> power;
	int numero = 0;
	for (int i = 1; i <= n; ++i)
	{
		cin >> sir[i];
		if (sir[i] == 1) numero++;
	} 

	int totesL = 0;
	int i;
	for (i = findNextOneR(1); i <= n; ++i)
	{
		if (sir[i] == 1)
		{
			colorAll(i);
			totesL++;
			if(findNextOneR(i) != i)
				i = findNextOneR(i) - 1;
		}
	}
	bool lBad = false;
	for(int i = 1; i <= n; ++i)
	{
		if(heat[i] == 0)
		{
			lBad = true;
			break;
		}
	}

	for (int i = 1; i <= n; ++i)
	{
		if (heat[i])
			heat[i] = 0;
	}
	int totesR = 0;
	for (int i = findNextOneL(n); i >= 1; --i)
	{
		if (sir[i] == 1)
		{
			colorAll(i);
			totesR++;
			if (findNextOneL(i) != i)
			{
				i = findNextOneL(i) + 1;
			}
		}
	}
	bool rBad = false;
	for (int i = 1; i <= n; ++i)
	{
		if (heat[i] == 0)
		{
			rBad = true;
			break;
		}
	}

	if (lBad && rBad)
	{
		cout << "-1";
	}
	else if (lBad)
	{
		cout << totesR;
	}
	else if (rBad)
	{
		cout << totesL;
	}
	else
	{
		cout << min(totesL, totesR);
	}
	getchar();
	getchar();
	getchar();
	return 0;
}

int findNextOneR(int ind)
{
	int i, pz = ind, cnt = 0;
	if (ind == 1)
	{
		cnt++;
		for (int i = ind; cnt <= power && i <= n; ++i, ++cnt)
		{
			if (sir[i] == 1)
			{
				pz = i;
			}
		}
	}
	else
		for (i = ind; cnt <= 2 * power && i <= n; ++i, ++cnt)
		{
			if (sir[i] == 1)
			{
				pz = i;
			}
		}
	return pz;
}

int findNextOneL(int ind)
{
	int i, pz = ind, cnt = 0;
	if (ind == n)
	{
		cnt++;
		for (i = ind; cnt <= power && i >= 1; --i, ++cnt)
		{
			if (sir[i] == 1)
			{
				pz = i;
			}
		}
	}
	else
	{
		for (i = ind; cnt <= 2 * power +1 && i >= 1; --i, ++cnt)
			{
				if (sir[i] == 1)
				{
					pz = i;
				}
			}
	}

	return pz;
}

void colorAll(int ind)
{
	int i = ind - power + 1;
	if (ind - power + 1 <= 1)
		i = 1;
	for (int i = 1; i <= ind + power - 1 && i <= n; ++i)
	{
		heat[i] = 1;
	}
}