Millor desordre. X71160

Definim el desordre d’un vector v d’aquesta manera:

Feu la funció

millor_desordre(v)

tal que, donat un vector v de mida n > 0 que conté enters (positius i negatius) que no han d’estar necessàriament ordenats, torni un parell de subíndexos i, j tals que 0 ≤ i < j < n de manera que l’intercanvi dels valors d’aquestes dues posicions siguin les que maximitzin el valor de desordre(v). Si hi ha més d’un parell que maximitzi amb el mateix valor la funció desordre(v), torneu la més petita, tenint en compte que

si i només si

En cas que no n’hi hagi cap intercanvi que maximitzi el valor de desordre(v) cal tornar (0,0).

Per exemple, si v = [1, 4, 2, 3], llavors la funció tornarà el vector (1 ,3), ja que desordre([1, 4, 2, 3]) = 2, però si intercanviem les posicions 1 i 3 tenim que v = [1, 3, 2, 4] i per tant tenim que desordre([1, 3, 2, 4]) = 3. A més, aquest és l’intercanvi que maximitza el valor d’aquesta funció.

És evident que si fer una funció que calculi desordre(v) us pot ajudar a resoldre el problema.

Observació

Només cal que enviïs el fitxer amb la funció (i les funcions auxiliars que hagis fet) que et demanem i prou en un sol fitxer que es digui solution.py.

El fitxer main.py et pot servir per a fer la teva solució, però no n’has d’enviar el contingut.

Per a executar el programa al teu terminal, hauràs de tenir els fitxers main.py i solution.py al mateix directori, amb els fitxers dels jocs de proves. Si vols executar el primer joc de proves, cal que facis:

python3 main.py < sample-1.inp

Entrada

Un vector v de mida n > 0 que conté enters (positius i negatius) que no han d’estar necessàriament ordenats

Sortida

El parell de subíndexos i, j tals que 0 ≤ i < j < n que maximitzen desordre(v). Si no n’hi ha cap, llavors ha de tornar (0, 0).