Tetris Invaders – Regional event 2013

Level 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

Runtime constraints

Maximum memory usage
5000 kilobytes
Maximum execution time
2000 milliseconds

Input/output samples

Sample input
3
1 3
3 1
2 2
Sample output
5
Note

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

Sample input
5
1 3
2 1
1 3
4 1
2 2
Sample output
8
Note

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.

Submit your solution

You have to register or log in to be able to submit your solution.