France-IOI
Contexte
Les codes correcteurs d'erreurs permettent de transmettre des messages sur des canaux de transmission bruités et de retrouver dans certains cas à l'arrivée les messages initialement envoyés en corrigeant les éventuelles erreurs apparues pendant la transmission.
Les codes linéaires binaires ont la propriété de transmettre des messages binaires (tableau de 0 et de 1) qui sont linéairement liés les uns aux autres.
Un tel code est défini par une matrice G de taille n par k. Ce code assure la transmission de messages de taille k en les transformant en des messages plus longs de taille n. Les bits ajoutés permettront de corriger des erreurs lors de la transmission.
Concrètement, si l'on souhaite transmettre un message V de taille k, le code transmettra le message G*V (où * dénote le produit matriciel sur les bits) de taille n. Puisqu'il est possible de demander l'envoi de n'importe quel mot binaire en entrée, il y a au plus 2^k messages possibles (éventuellement moins si la matrice G n'est pas de rang k).
Un paramètre de première importance pour mesurer l'efficacité d'un tel code est sa distance minimale. Cette distance représente le nombre minimum de bits qui différent entre deux mots différents obtenus de cette manière.
Il est simple de montrer que du fait que le code est linéaire, cette distance peut s'exprimer autrement. La distance minimale est donc également le nombre minimum de bits `1` dans les mots de taille n, sans considérer le mot ne contenant que des 0.
Enoncé
Étant donné une matrice G binaire de taille n lignes par k colonnes, estimer quel est le nombre minimum de 1 dans un vecteur G*V, avec V vecteur binaire de taille k contenant au moins un `1`. Attention de bien noter qu'il s'agit d'un produit entre une matrice et un vecteur binaires. Ceci veut dire que les opérations + et × utilisées lors du calcul de ce produit sont les opérations correspondantes binaires, à savoir respectivement le "ou exclusif" et le "et".
Limites de temps et de mémoire (Python)
- Temps : 1 s sur une machine à 1 GHz.
- Mémoire : 8 000 ko.
Entrée
L'entrée donne sur une première ligne les paramètres n et k, séparés par une espace.
Ensuite se trouve la matrice G, une ligne par ligne et les colonnes séparées par des espaces. Les coefficients de cette matrice ne peuvent être que 1 ou 0.
Sortie
La sortie du programme est l'entier représentant le nombre minimum de 1 dans un vecteur G*V, où V est un vecteur binaire de taille k qui contient au moins un `1`. Cette valeur sera suivie d'un passage à la ligne.
Exemples
Exemple 1
entrée :
8 4 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1
sortie :
4
Exemple 2
entrée :
6 4 0 1 0 1 1 0 1 0 0 0 1 1 1 1 0 0 1 0 0 1 0 1 1 0
sortie :
0
Exemple 3
entrée :
4 2 1 1 0 0 1 1 0 0
sortie :
0
Commentaires
Squelettes de codes :
[GROUPFULL:skeleton]Vous devez être connecté(e) pour résoudre ce problème.
L'inscription ne prendra qu'une minute et vous pourrez alors résoudre les exercices puis faire valider automatiquement vos solutions.
Une fois identifié(e), vous pourrez demander sur cette page des conseils pour résoudre le sujet ou demander de l'aide sur le forum d'entraide.
Lorsque vous serez connecté(e), vous pourrez voir vos actions ici.
Une correction détaillée sera disponible lorsque vous aurez résolu le sujet.