Foro de elhacker.NET

Hola chic@s, os dejo la solución del problema:
Código:
#include <algorithm>
#include <iostream>

using namespace std;


/*

PRECONDICION DE LA FUNCION: 
  ---Escribe aqu� la precondici�n de la funci�n.

   0<=n<=tam(v) && crec(v,n)  
*/
unsigned int num_k_emparejados(int v[], unsigned int n, unsigned int k);
/*
POSTCONDICION DE LA FUNCION: 
  ---Escribe aqu� la poscondici�n de la funci�n. Para refirte 
  ---al valor devuelto por la funci�n, utiliza la pseudo-variable
  ---'res'
  
  (1) Definiciones auxiliares (si procede):
   crec(v,n) = PARATODO i: 0<=i<n-1: v[i] < v[i+1]
   num_k_emp(v,n,k) = #i,j:0<=i<=j<n:|v[i]-v[j]|=k

  
  (2) Postcondici�n
   res = num_k_emp(v,n,k)

  
 */
 
 /* DISE�O DEL ALGORITMO:
 --- Detalla aqu� el proceso seguido para dise�ar el
 --- algoritmo
 
 
PASO 1. Variables
 v,n,res,i,j
 
 
PASO 2. Invariante
  (1) res = num_k_emp_hasta(v,n,k,i)
       donde 
        num_k_emp_hasta(v,n,k,t) = #u,w:0<=u<=w<n && u < t:|v[u]-v[w]|=k 		  
  (2) 0 <= i <= j <= n
  (3) no_k_emp(v,k,i,j)
       donde no_k_emp(v,k,i,j) = PARATODO u,w: i<=u<=w<j: |v[u]-v[w]|<k 
 
PASO 3. Inicializaci�n:
     i=0
     j=0
	 res = num_k_emp_hasta(v,n,k,j) = num_k_emp_hasta(v,n,k,0) = 
      	   (#u,w:0<=u<=w<n && u < 0:|v[u]-v[w]|=k) = 
		   (#u,w:false:|v[u]-v[w]|=k) = 0
 
PASO 4: Continuaci�n y finalizaci�n:
         j != n
       * Si j = n, entonces:
	       (1) El invariante asegura que res = num_k_emp_hasta(v,n,k,i)
		   (2) Tambi�n asegura que no_k_emp(v,k,i,j)
           (3) Por tanto, res = num_k_emp_hasta(v,n,k,j)
           (4) Pero,como j=n, entonces res = num_k_emp_hasta(v,n,k,n)
		 	  
 
PASO 5: Cuerpo del bucle. Como 0 <= i <= j <= n y adem�s j != n 
        (por la condici�n del bucle), podemos asegurar que 0<=i<n y
		 0<=j < n. Por tanto, tanto v[i] como v[j] tienen sentido.
        * Si |v[i]-v[j]|<k:
            (1) Incrementamos j, para hacer la diferencia m�s grande.
                Esto afecta a:
                (1) 0 <= i <= j <= n. Pero, como 0 <= j <n antes
				      del incremento, despu�s de incrementar j
					  el t�rmino sigue siendo v�lido.
                (2)  no_k_emp(v,k,i,j). Pero, como |v[i]-v[j]|<k, y
				       como v es estrictamente creciente, entonces
					   el t�rmino se preserva. 
		* Si |v[i]-v[j]|>k: Incrementamos i. Esto afecta a:
                (1) 0 <= i <= j <= n. Pero como, antes de incrementar i, 
				    0 <= i <=j, y |v[i]-v[j]|>k asegura que i < j (por ser
					v estrictamente creciente), el t�rmino se preserva tras 
					incrementar i.
			    (2) res = num_k_emp_hasta(v,n,k,i). Pero, como
                      se cumpl�a: (i) no_k_emp(v,k,i,j); 
					  (ii) |v[i]-v[j]|>k; (iii) el vector es estrictamente
                      creciente, por lo que, al ser |v[i]-v[j]|>k,
                      no podemos encontrar un w > j, tal que 
                      |v[i]-v[w]|=k, tras incrementar i podemos
                      asegurar que el t�rmino contin�a verific�ndose.
         * Si |v[i]-v[j]|=k. En este caso:
               (1) Incrementamos 'res', al haber encontrado una 
                   nueva k-pareja.
			   (2) Pero esto afecta a res = num_k_emp_hasta(v,n,k,i).
                   Como el vector es estrictamente creciente, 
                   y como |v[i]-v[j]|=k, no habr� w > j, tal que
                   |v[i]-v[w]|=k. Por tanto, para reestablecer el 
                   t�rmino basta incrementar i. Pero esto afecta:
   				    (2.1) A no_k_emp(v,k,i,j). Pero como, antes de
					      incrementar i, se cumple para v[i..j),
						  podemos asegurar que se cumpl�a tambi�n
                          para v(i..j). Por tanto, tras incrementar
                          i el t�rmino sigue siendo v�lido.
                    (2.2) A 0 <= i <= j <= n. Si, antes del incremento,
					      i=j, el t�rmino se viola. Para evitarlo, en
						  este caso debemos incrementar j. Pero entonces,
						  puede verse afectado:
						   (2.1.1) 0 <= i <= j <= n. Pero este 
						           t�rmino sigue cumpli�ndose, ya
								   que, tras incrementar j, i=j 
								   (al serlo antes de incrementar i y j),
								   y adem�s 0<=j<n.
						   (2.1.2) no_k_emp(v,k,i,j). Pero, como i=j,
						           esto es no_k_emp(v,k,i,i) =  
								   PARATODO u,w: i<=u<=w<i: |v[u]-v[w]|<k 
								   = true. 
 
PASO 6: Terminaci�n		  
    2n - (i+j) es una expresi�n de cota.
	  * Como en cada iteraci�n se incrementa i o j, la expresi�n
	   disminuye.
	  * Adem�s, podemos comprobar que 2n - (i+j) >= 0 es un invariante
        del bucle:
           - Al inicializar i=j=0, 2n - (i+j) = 2n >= 0.
           - Supongamos que 2n - (i+j) >= 0 se cumple al entrar en
             el cuerpo del bucle. Como i < n y j <n, 
             2n - (i+j) no va a ser m�s peque�a que 
             2n - ((n-1)+(n-1)) = 2n - 2n + 2 = 2.
             Por tanto, en el caso m�s extremo en el que incrementamos
             tanto i como j, a la salida del bucle 2n - (i+j) no 
             va a ser m�s peque�a que 0.     			 
 
*/
 

unsigned int num_k_emparejados(int v[], unsigned int n, unsigned int k) {
	int i=0;
	int j=0;
	int res=0;
	while (j!=n) {
		int d = v[j]-v[i];
		if (d < k) {
			j++;
		}
		else {
			if (d == k) {
			  res++;
              if (i == j) j++;			  
			}
			i++;
		}
	}
	return res;
}	

/*
Complejidad: Determina justificadamente el orden de complejidad
de este algoritmo: 
  * Con la expresi�n de cota hemos visto que el bucle no da
    m�s de 2n vueltas. Como el cuerpo se ejecuta en tiempo
	constante, la complejidad es lineal ( O(n) ). 

*/ 



bool procesa_caso() {
	int v[100];
	int n, k;
	cin >> n;
	if (n != -1) {
		cin >> k;
		for (int i = 0; i < n; i++) {
			cin >> v[i];
		}
		cout << num_k_emparejados(v, n, k) << endl;
		return true;
	}
	else {
		return false;
	}
}

int main() {
	while (procesa_caso());
}
Por si os interesa, saludos.