Dependencias Ordenadas W41859

Statement

Sea una matriz $n \times m$ de enteros. Esta matriz representa una tabla de datos de $n$ filas y $m$ columnas ( $n \geq 2$ y $m \geq 2$ ).

Decimos que la dependencia ordenada x -> y entre las columnas x y y, es válida en la matriz M si y solo si para todo par de filas i y j (donde $i < j$ ) ocurre lo siguiente:

el orden que tienen los valores en la columna x en ambas filas i y j es igual al orden que tienen los valores en la columna y.

donde la relación de orden puede ser $\leq$ o $\geq$ . Dicho de otro modo: una dependencia ordenada x -> y es válida si y solo si para cualquier par de filas i,j de M ocurre una de estas dos cosas:

Si el valor que la fila i tiene en la columna x es mayor o igual que el valor que la fila j tiene en la columna x, entonces el valor que la fila i tiene en la columna y es mayor o igual que el valor que la fila j tiene en la columna y.

o simétricamente:
Si el valor que la fila i tiene en la columna x es menor o igual que el valor que la fila j tiene en la columna x, entonces el valor que la fila i tiene en la columna y es menor o igual que el valor que la fila j tiene en la columna y.

Por ejemplo, sea la tabla (matriz) M de 5 filas y 4 columnas:

1	2	2	1
1	3	2	2
2	3	3	1
3	5	4	2
2	4	5	1

Consideremos la dependencia ordenada 0 -> 1. Vemos que los valores de la columna 0 en las filas 0 y 1 tienen esta relación de orden: $1 \leq 1$ , que es la misma que tienen los valores en la columna 1: $2 \leq 3$

1	2	2	1
1	3	2	2

y también, por ejemplo, en las filas 3 y 4, donde tenemos $3 \geq 2$ y $5 \geq 4$ :

3	5	4	2
2	4	5	1

Y vemos que en ambos casos los valores de la columna 1 cumplen la misma relación de orden. Y esto ocurre para todo par de filas. Por tanto, la dependencia ordenada 0 -> 1 es válida en M.

En cambio, la dependencia ordenada 0 -> 3 no es válida porque, por ejemplo, en las filas 1 y 2 los valores de la columna 0 tienen esta relación: $1 \leq 2$ y los de la columna 3 esta: $2 \geq 1$

1	3	2	2
2	3	3	1

En este caso, podemos decir que las filas 1 y 2 invalidan 0 -> 3.

Haz una función dependencia_ordenada con la siguiente declaración y especificación:

/*
 * PRE:  M.size() > 0 and M[0].size() > 0 and 0 <= x,y < M[0].size().
 *
 * POST: Devuelve true si y solo si la dependencia ordenada x -> y
 *       es válida en la matriz M.        
 */
bool dependencia_ordenada(const Matriu& M, int x, int y);

Observación

Solo hay que enviar la función que se pide (y las funciones que hayáis podido declarar vosotros).

Además, en el fichero que enviéis debe aparecer también esto:

#include <iostream>
#include <vector>
using namespace std;

typedef vector <int>   Vector;
typedef vector<Vector> Matriu;

No se puede usar la ordenación de C++: std::sort. Tampoco se puede usar el método push_back() de la clase vector.

Si queréis, podéis usar las funciones min, max o swap.

Hay que tener en cuenta que la relación entre dos filas i y j respecto a la dependencia x -> y es simétrica. Es decir, si el par de filas i y j no invalida la dependencia x -> y, el par j y i tampoco. Por eso en la definición de la dependencia especificamos $i < j$ .

Entrada

La entrada es una matriz y una secuencia de dependencias ordenadas. De la lectura ya se encarga el programa principal.

Salida

La salida son los resultados para cada dependencia ordenada. De la escritura también se encarga el programa principal.

Public test cases

Input

Output

0->1 SI
0->2 NO
0->3 NO
1->0 SI
1->2 NO
1->3 NO
2->0 NO
2->1 NO
2->3 NO
3->0 NO
3->1 NO
3->2 NO

Input

3 5
1  2  6  3  1
2  5  4  2  3
3  8  2  1  2

0 -> 1
0 -> 2
0 -> 3
0 -> 4
1 -> 0
1 -> 2
1 -> 3
1 -> 4
2 -> 0
2 -> 1
2 -> 3
2 -> 4
3 -> 0
3 -> 1
3 -> 2
3 -> 4
4 -> 0
4 -> 1
4 -> 2
4 -> 3

Output

0->1 SI
0->2 NO
0->3 NO
0->4 NO
1->0 SI
1->2 NO
1->3 NO
1->4 NO
2->0 NO
2->1 NO
2->3 SI
2->4 NO
3->0 NO
3->1 NO
3->2 SI
3->4 NO
4->0 NO
4->1 NO
4->2 NO
4->3 NO

Input

3 5
1  2  4  3  1
2  5  4  2  3
3  8  2  1  2

0 -> 1
0 -> 2
0 -> 3
0 -> 4
1 -> 0
1 -> 2
1 -> 3
1 -> 4
2 -> 0
2 -> 1
2 -> 3
2 -> 4
3 -> 0
3 -> 1
3 -> 2
3 -> 4
4 -> 0
4 -> 1
4 -> 2
4 -> 3

Output

0->1 SI
0->2 NO
0->3 NO
0->4 NO
1->0 SI
1->2 NO
1->3 NO
1->4 NO
2->0 NO
2->1 NO
2->3 SI
2->4 NO
3->0 NO
3->1 NO
3->2 SI
3->4 NO
4->0 NO
4->1 NO
4->2 NO
4->3 NO

Information

Author: PRO1
Language: Spanish
Translator
Original language: Catalan
Other languages: Catalan
Official solutions: C++
User solutions: C++