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

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

Runtime constraints

Maximum memory usage
1000 kilobytes
Maximum execution time
25 milliseconds

Input/output samples

Sample input
42
001101011000010110110011101001101010101010
Sample output
13

Submit your solution

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