Dependències Ordenades W41859

Statement

Sigui una matriu $n \times m$ d’enters. Aquesta matriu representa una taula de dades de $n$ files i $m$ columnes ( $n \geq 2$ i $m \geq 2$ ).

Diem que la dependencia ordenada x -> y entre les columnes x i y, és vàlida a la matriu M si i només si per a tot parell de files i i j (on $i < j$ ) passa això:

l’ordre que tenen els valors a la columna x a totes dues files i i j és igual a l’ordre que tenen els valors a la columna y.

on la relació d’ordre pot ser $\leq$ o $\geq$ . Dit altrament: una dependència ordenada x -> y és vàlida si i només si per a qualsevol parell de files i,j de M passa una d’aquestes dues coses:

Si el valor que la fila i té a la columna x és més gran o igual que el valor que la fila j té a la columna x, aleshores el valor que la fila i té a la columna y sigui més gran o igual que el valor que la fila j té a la columna y.

o el simètric:
Si el valor que la fila i té a la columna x és més petit o igual que el valor que la fila j té a la columna x, aleshores el valor que la fila i té a la columna y sigui més petit o igual que el valor que la fila j té a la columna y.

Per exemple, sigui la taula (matriu) M de 5 files i 4 columnes:

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

Considerem la dependència ordenada 0 -> 1. Veiem que els valors de la columna 0 a les files 0 i 1 tenen aquesta relació d’ordre: $1 \leq 1$ , que es la mateixa que tenen els valors a la columna 1: $2 \leq 3$

1	2	2	1
1	3	2	2

i també, per exemple, en les files 3 i 4, on tenim $3 \geq 2$ i $5 \geq 4$ :

3	5	4	2
2	4	5	1

I veiem que en tots dos casos els valors de la columna 1 compleixen la mateixa relació d’ordre. I això passa per a tot parell de files. Per tant, la dependència ordenada 0 -> 1 és vàlida a M.

En canvi, la dependència ordenada 0 -> 3 no és vàlida perquè, per exemple, a les files 1 i 2 els valors de la columna 0 tenen aquesta relació: $1 \leq 2$ i els de la columna 3 aquesta: $2 \geq 1$

1	3	2	2
2	3	3	1

En aquest cas, podem dir que les files 1 i 2 invaliden 0 -> 3.

Fes una funció dependencia_ordenada amb la següent declaració i especificació:

/*
 * PRE:  M.size() > 0 and M[0].size() > 0 and and 0 <= x,y < M[0].size().
 *
 * POST: Retorna true si i només si la dependència ordenada x -> y
 * 		 és vàlida a la matriu M.        
 */
bool dependencia_ordenada(const Matriu& M, int x, int y);

Observació

Només cal enviar la funció que us demanem (i les funcions que hagueu pogut declarat vosaltres).

A més, al fitxer que envieu cal que també hi hagi això:

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

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

No es pot fer servir l’ordenació del C++: std::sort. Tampoc no es pot fer servir el mètode push_back() de la classe vector.

Si voleu, podeu fer servir les funcions min, max o swap.

Cal tenir en compte que la relació de relació entre dues files i i j respecte a la dependència x -> y és simètrica. És a dir, si el parell de files i i j no invalida la dependència x -> y, el parell j i i tampoc. Per això a la definició de la dependència especifiquem $i < j$ .

Entrada

L’entrada és una matriu i una seqüència de dependències ordenades. De la lectura ja se n’encarrega el programa principal.

Sortida

La sortida són els resultats per a cada dependència ordenada. De l’escriptura també se n’encarrega 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: Catalan
Other languages: Spanish
Official solutions: C++
User solutions: C++