Chaîne de 0 et de 1 : où couper ? – Qualification 2002

Niveau 2

Énoncé

On vous donne une suite de '0' et de '1'. Écrire un programme qui détermine la position avant laquelle il faut couper cette suite pour que le nombre de '1' à gauche de cette coupure plus le nombre de '0' à droite soit le plus petit possible.

Les positions sont comptées à partir de 0. Pour couper tout à gauche, on coupe donc avant la position 0.

Entrée

On vous fournit deux lignes sur l'entrée standard :

  • Le nombre $N$ d'éléments '0' ou '1' de la suite.

  • Les caractères de la suite, sans séparations.

Sortie

Vous devez écrire une ligne sur la sortie standard :

  • La position avant laquelle on doit couper. Si plusieurs positions donnent le même total, vous devez écrire la première (la plus petite).

Contraintes

$0 <= N <= 100 000$

Contraintes d'exécution

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

Exemples d'entrée/sortie

Exemple d'entrée
42
001101011000010110110011101001101010101010
Exemple de sortie
13