1353 . Shuffling cards
Description
A deck of 2N cards with distinct values of 1,2, ..., 2N is given to the shuffling machine. At the beginning, the cards are arranged in the deck in ascending order from the top to the bottom. The shuffling machine executes a sequence of M instructions determined by M integers k1, k2,..., kM for shuffling the cards. The instruction determined by the number ki (1 ≤ |ki| < N), commands the machine to shuffle the
cards as follows:
• If ki > 0: remove a pile of 2ki cards at the middle of the deck and stacks them on top of the deck.
• If ki < 0: remove a pile of -2ki cards at the middle of the deck and inserts them into bottom of the
deck.
Mr. X received the deck after it has been shuffled according to M instructions. He wants to throw away some cards from the deck in such a way that the values of the remained cards
are in an increasing order from the top to the bottom. Given the M instructions for the shuffling machine, your task is to write a program to help Mr. X determine the minimum number of cards to be removed after the deck has been shuffled.
Input Format
The input file consists of several data sets. The first line of the input file contains the number of data
sets which is a positive integer and is not bigger than 20. The following lines describe the data sets.
Each data set consists of two lines. The first line contains two positive integers N and M (2 ≤ N ≤ 109; 0
≤ M ≤ 105) separated by a space. The second line contains M integer k1, k2,…, kM separated by a space.
Output Format
For each data set, write in one line the minimum number of cards to be removed after the deck has been shuffled.
Sample Input 1
2 3 2 -2 1 1000000000 3 999999999 -1 2
Sample Output 1
2 7
Hints
Problem Source
Migrated from old NTUJ.
The ACM-ICPC 2010 Asia Regional Contest, Site Hanoi
Subtasks
| No. | Testdata Range | Score |
|---|