Tetris Invaders – Épreuve régionale 2013

Niveau 5

É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

Contraintes d'exécution

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

Exemples d'entrée/sortie

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

Pour détruire le premier tetrimino (1,3), il faut tirer une fois, puis aller en bas et tirer une fois pour détruire le deuxième (3,1) et enfin tirer deux fois pour détruire le troisième tetrimino (2,2). Ce qui fait un total de 5 tours (1 tir + 1 déplacement + 1 tir + 2 tirs).

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

Il faut au total 8 tours, la séquence d'action étant : 4 tirs, 1 déplacement (vers le bas), 3 tirs. La première séquence de 4 tirs permettant de détruire les 3 premiers tetriminos.