Tetris Invaders – Épreuve régionale 2013

Énoncé¶

Des tetriminos (pièces du jeu Tetris) arrivent vers vous (de gauche à droite), vous devez les détruire dans leur ordre d'arrivée. Ceux-ci sont décomposables en deux lignes de blocs, celle du haut et celle du bas. Tirer sur un tetrimino lui retire un bloc, dès qu'une des deux lignes du tetrimino est détruite, le tetrimino disparaît.

À chaque tour, vous pouvez :

• tirer pour détruire le bloc de tetrimino le plus proche sur votre ligne ;
• utiliser les touches directionnelles (haut ou bas) pour changer de ligne.

Sachant que vous commencez sur la case du haut, sur combien de touches devrez-vous appuyer au minimum pour détruire tous les blocs ?

Entrée¶

• Sur la première ligne, le nombre N de tetriminos.
• Sur les N prochaines lignes : un tetrimino, c'est-à-dire deux nombres, le premier est le nombre de blocs de la ligne du haut, le second est le nombre de blocs de la ligne du bas.

Les N dernières lignes sont dans l'ordre d'arrivée des tetriminos, la dernière ligne contient donc le dernier tetrimino à détruire.

Sortie¶

Le nombre de touches nécessaires pour détruire tous les blocs.

Contraintes¶

• 1 <= N <= 100 000