Enter The Matriks – Qualification 2022

Énoncé¶

Vous êtes l'élu, le maître de la Matriks. Cependant, comme vous le savez car vous êtes un fan incontestable de la trilogie des sœurs Wachowskis, il y a eu plusieurs versions de la matrice avant d'aboutir à celle dans laquelle ont vécu Neo, Morpheus et Trinity.

En effet, au lieu d'être dans la matrice (forme finale du cocon informatique dans lequel sont immergés les êtres humains), vous êtes dans une version plus primaire, une version Test. Cette pre-release de la matrice s'appelle la "Matriks". Pour en sortir et sauver Sion, la dernière ville des Hommes encore debout, vous devez trouver deux clés (des listes d'entiers). Ces deux clés sont cachées dans le code de la Matriks (une grosse liste d'entiers écrits en vert sur fond noir qui descend en colonnes de manière assez stylé).

Vous savez deux choses : le produit des sommes de ces deux clés est égal à un nombre magique $X$, qui vous est donné. Et vous savez que les deux clés doivent être les plus longues possibles (maximiser la somme des longueurs des sous-listes). À vous de trouver ces clés !

Attention, l'ordre des clés importe, vous devez d'abord afficher la plus grande des deux listes, si elles sont de même taille, affichez d'abord celle dont la somme est la plus grande.

S'il n'y a pas de sous-liste qui respecte ces conditions, écrire "IMPOSSIBLE" (vous n'êtes alors peut-être pas l'élu ?).

Note : une sous-liste d'une liste L est une sous-partie contiguë de L. Par exemple si L = [1 2 3 4 5], alors [1 2 3] et [3 4] sont des sous-listes mais pas [1 3 4].

Entrée¶

L’entrée contiendra :

• Sur la première ligne, un entier : $X$, le nombre magique.
• Sur la ligne suivante, un entier : $N$, la longueur du code la Matriks.
• Sur la ligne suivante, une liste de $N$ entiers séparés par des espaces : L, le code de la Matriks.

Sortie¶

Les deux clés (chacune sur une ligne) ou le message "IMPOSSIBLE".

Contraintes¶

• $2 \le N \le 10\,000$