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

Level 2

ENONCE

On vous donne une suite de '0' et de '1'. Ecrire 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.

CONTRAINTES

0 \<= N \<= 100000, où N est le nombre d'éléments '0' ou '1' de la suite.

ENTREE

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éparartions.

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).

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.