Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2452
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2452
Semente
Por OBI - Olimpíada Brasileira de Informática 2014 
Brazil
Timelimit: 1
Um experimento biológico utiliza uma fita de papel branco especial, na qual algumas gotas de um reagente são colocadas em posições específicas. Inicialmente a gota de reagente faz com que o papel se torne preto na posição em que foi colocada. A cada dia o reagente se propaga pelo papel, em todas as direções, com velocidade de 1 posição por dia, colorindo a região em que o reagente se propagou. A figura abaixo mostra um experimento com uma fita de 13 posições, com três gotas de reagente inicialmente, colocadas nas posições 2, 6 e 13 (a posição 1 é a primeira mais à esquerda da fita). Ao final do terceiro dia, a fita está completamente tomada pelo reagente.
Você foi contratado para escrever um programa que, dados o comprimento da fita de papel e as posições das gotas de reagente no início do experimento, determine quantos dias serão necessários para a fita de papel ficar completamente tomada pelo reagente.
Entrada
A primeira linha contém dois inteiros F (1 ≤ F ≤ 100000) e R (1 ≤ R ≤ 1000), indicando respectivamente o comprimento da fita de papel, em números de posições, e o número de gotas no início do experimento. A segunda linha contém R inteiros, indicando as posições das gotas de reagente, que são dadas em ordem crescente.
Saída
Seu programa deve produzir uma única linha, contendo um único inteiro, o número de dias necessários para que a fita de papel fique totalmente tomada pelo reagente.
| Exemplos de Entrada | Exemplos de Saída |
|
13 3 |
3 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
#define true 1
#define false 0
#define MAXSIZE 100100
typedef struct tipoNo{
int numero;
struct tipoNo *proximo;
}tipoNo;
typedef struct tipoFila{
tipoNo *primeiro;
tipoNo *ultimo;
} tipoFila;
void queue(tipoFila *);
_Bool empty(tipoFila *);
void push(tipoFila *, int );
_Bool pop(tipoFila *, int *);
int main (void)
{
tipoFila fila;
_Bool flag = false;
int k, i, x, res, dias;
unsigned comprimento, numGotas;
queue(&fila);
int vetor[MAXSIZE];
scanf("%d %d", &comprimento, &numGotas);
for (i = 0; i < numGotas; ++i)
scanf("%d", &x), push(&fila, x);
for (i = 1; i < = comprimento; ++i)
vetor[i] = 0;
x = k = 0;
res = dias = 0;
while (!empty(&fila))
{
pop(&fila, &x);
++res;
vetor[x] = 1;
if (vetor[x - 1] == 0 && x - 1 > 0)
push(&fila, x - 1), ++k, vetor[x - 1] = 1;
if (vetor[x + 1] == 0 && x + 1 < = comprimento)
push(&fila, x + 1), ++k, vetor[x + 1] = 1;
if (res == numGotas)
{
numGotas = k;
k = 0;
if (flag)
++dias;
res = 0;
flag = true;
}
}
printf("%d\n", dias);
}
void queue(tipoFila *fila)
{
fila->primeiro = NULL;
fila->ultimo = NULL;
}
void push(tipoFila *fila, int numero)
{
tipoNo *auxiliar;
auxiliar = (tipoNo *) malloc(sizeof(tipoNo));
if (!auxiliar)
exit(1);
if (fila->primeiro)
{
fila->ultimo->proximo = auxiliar;
auxiliar->proximo = NULL;
}
else
fila->primeiro = auxiliar;
fila->ultimo = auxiliar;
auxiliar->numero = numero;
}
_Bool pop(tipoFila *fila, int *retorno)
{
tipoNo *auxiliar;
if (fila->primeiro)
{
if (fila->primeiro->proximo)
{
*retorno = fila->primeiro->numero;
auxiliar = fila->primeiro;
fila->primeiro = fila->primeiro->proximo;
free(auxiliar);
return true;
}
else
{
*retorno = fila->primeiro->numero;
auxiliar = fila->primeiro;
fila->primeiro = fila->ultimo = NULL;
free(auxiliar);
return true;
}
}
else
return false;
}
_Bool empty(tipoFila *fila)
{
return (fila->primeiro == NULL);
}
Input
2 6 13
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <cstdio>
#include <queue>
#include <set>
#define MAXN 100001
using namespace std;
set < int> visitado;
int resposta, n, m, trabalhando;
int main() {
queue < pair<int, int> > fila;
scanf("%d %d", &n, &m);
visitado.insert(0);
visitado.insert(n + 1);
for (int i = 0; i < m; i++) {
int x;
scanf("%d", &x);
fila.push(make_pair(x, 0));
}
while (!fila.empty() && visitado.size() - 2 < n) {
pair<int, int> davez = fila.front();
fila.pop();
resposta = davez.second;
trabalhando = davez.first;
visitado.insert(trabalhando);
if (!visitado.count(trabalhando - 1))
fila.push(make_pair(trabalhando - 1, resposta + 1));
if (!visitado.count(trabalhando + 1))
fila.push(make_pair(trabalhando + 1, resposta + 1));
}
printf("%d\n", resposta);
return 0;
}
Input
2 6 13
Output