Problème 1006
Sur le dernier relevé bancaire d'Alice, figure en haut de page le solde de fin du mois dernier. Puis, sur les lignes qui suivent, 12 nombres entiers non nuls (1 par ligne) correspondent aux opérations du mois. Le nombre est positif s'il s'agit d'un crédit sur le compte, négatif s'il s'agit d'une dépense. Curieusement, chaque nombre des lignes 1 à 10 est strictement supérieur au total des deux lignes qui suivent. De plus, les lignes 11 et 12 sont identiques aux lignes 1 et 2.- 1A. Combien y a-t-il, au plus, de nombres positifs sur les lignes 1 à 10 ?
- 2A. Sachant que le compte est à 10 € en fin de mois et que le maximum de lignes positives a été atteint, quel était le solde minimum de fin du mois dernier ?
Pour ce problème, j'ai effectué une recherche un peu exhaustive, en remarquant des propriétés sur les petites tailles (nombre de lignes du relevé), et en agrandissant ensuite la taille avec des restrictions. On remarque notamment très vite que les valeurs des lignes positives sont toujours petites et que les valeurs minimales négatives ne peuvent pas dépasser pas -30. On remarque aussi bien sûr que deux lignes consécutives ne peuvent pas être positives (ce qui se voit aussi facilement à partir des conditions de l'énoncé). En se basant sur cela, on peut effectuer une recherche exhaustive pour une taille de 12 (mais cela prend quand même un certain temps). Pour cette taille, on voit la structure qui se met en place pour toutes les tailles supérieures.
Le code du programme se trouve ici.
Remarque : Pour ce problème, je n'ai pas eu tous les points puisque le programme donné au-dessus comporte une erreur. En effet, il est fait l'hypothèse que la première ligne est positive (j'ai fait cette hypothèse quand j'ai recherché le nombre max de lignes positives et ne l'ai pas remise en cause ensuite). Or, le minimum est atteint lorsque la deuxième ligne est positive. Cela explique le résultat de 102 au lieu de 100.
Le code du programme se trouve ici.
Remarque : Pour ce problème, je n'ai pas eu tous les points puisque le programme donné au-dessus comporte une erreur. En effet, il est fait l'hypothèse que la première ligne est positive (j'ai fait cette hypothèse quand j'ai recherché le nombre max de lignes positives et ne l'ai pas remise en cause ensuite). Or, le minimum est atteint lorsque la deuxième ligne est positive. Cela explique le résultat de 102 au lieu de 100.
- 1A : Il y a au plus 4 nombres positifs sur les lignes 1 à 10.
- 2A : Le solde minimum de fin du mois dernier est 100€.