Connecter les îles – Épreuve régionale 2024

Niveau 1 ⋅ Validation weight: 100%

Énoncé

Le Ragnarök approche!

Sur son chemin, Jøsëf Marchand trouve une série d’îles déconnectées peuplées. Pour aider les villageois à s'enfuir, il décide de rejoindre toutes les îles entre elles.

On représente le paysage d'îles sous la forme d'un tableau de 0 ou 1 :

  • Un 1 indique la présence d'une île ;
  • Un 0 indique qu'il n'y a pas d'île.

Pour ajouter une île sur une case, il faut ajouter 1 tonne de sable sur cette case.

Indiquez à Jøsëf le nombre d'îles à construire pour que toutes les îles soient reliées.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, la taille du tableau représentant le paysage.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : paysage, le tableau décrivant le paysage. Un 1 représente la présence d'une île.

Sortie

Afficher, sur une ligne, le nombre minimum d'îles que l'on doit construire afin que toutes les îles soient connectées.

Si aucune île n'est présente, la réponse est 0 car il n'y a aucune île à connecter.

Contraintes

  • $1 \le N \le 40$

Contraintes d'exécution

Utilisation mémoire maximum
100000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
10
0 1 1 0 0 1 1 1 0 0
Exemple de sortie
2
Commentaire

Ici, le tableau est composé de deux groupes d'îles séparées par 2 tuiles d'eau :

1
2
0 1 1 0 0 1 1 1 0 0
      ^^^

Il faudra donc 2 tonnes de sable pour les rejoindre.

Exemple d'entrée
16
0 0 1 1 0 0 0 0 1 1 1 0 1 0 0 0
Exemple de sortie
5
Commentaire

Ici, le paysage est composé de trois groupes d'îles. Elles sont séparées par deux zones de respectivement 4 tuiles d'eau et 1 tuile d'eau.

1
2
0 0 1 1 0 0 0 0 1 1 1 0 1 0 0 0
        ^^^^^^^       ^

Il faudra donc au total 5 tonnes de sable pour que toutes les îles soient reliées.

Exemple d'entrée
7
0 0 1 1 1 1 0
Exemple de sortie
0
Commentaire

Ici, toutes les îles sont déjà reliées. Il n'y a donc rien à faire. Il ne faut donc pas de sable supplémentaire pour connecter toutes les îles.