Ecoulement – Épreuve régionale 2015

Niveau 3

Énoncé

On fait s'écouler de l'eau à travers un milieu en forme de pyramide composé d'alvéoles hexagonales. Pour chaque hexagone, l'eau s'écoule sur les deux alvéoles adjacentes de l'étage inférieur. En outre, chaque hexagone de ce milieu a une perméabilité différente à l'eau.

On vous donne un schéma indiquant le temps en secondes que met l'eau à traverser une alvéole du milieu. En retour, on veut savoir combien de temps la base de la pyramide mettra pour être complètement mouillée, c'est-à-dire que chaque hexagone à la base de la pyramide aura été traversé par une chute d'eau.

Entrée

Sur la première ligne, un entier N représentant le nombre d'étages de la pyramide.

Le schéma est compris sur les N lignes suivantes. À la i-ème ligne du schéma, il y a i entiers (séparés par des espaces) représentant la perméabilité des alvéoles (c'est à dire le temps en seconde pour le traverser) du milieu sur cet étage.

Sortie

Un seul nombre entier, le temps en secondes à partir duquel la base de la pyramide est complètement mouillée.

Contraintes

  • 1 ≤ N ≤ 100

Contraintes d'exécution

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

Exemples d'entrée/sortie

Exemple d'entrée
3
1
2 3
4 5 1
Exemple de sortie
8
Commentaire

Les trois images de gauche à droite représentent l'état de l'infiltration de l'eau après respectivement 3, 7 et 8 secondes après le début. À t = 7 sec, il reste encore une case en bas non mouillée, alors qu'à t = 8 sec ce n'est plus le cas, la réponse est donc 8.