Connecter les îles – Regional event 2024

Level 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$

Runtime constraints

Maximum memory usage
100000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
10
0 1 1 0 0 1 1 1 0 0
Sample output
2
Note

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.

Sample input
16
0 0 1 1 0 0 0 0 1 1 1 0 1 0 0 0
Sample output
5
Note

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.

Sample input
7
0 0 1 1 1 1 0
Sample output
0
Note

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.

Submit your solution

You have to register or log in to be able to submit your solution.