SHUFFLEK - Shuffling cards
English | Vietnamese |
Một bộ bài gồm 2n quân bài được đưa vào máy tráo bài, trên các lá bài từ trên xuống dưới, người tag hi lần lượt các số từ 1 tới 2n. Máy tráo bài thực hiện một dãy m lệnh biểu diễn bởi m số nguyên k1,k2,…,km, mỗi lệnh ki (1<=|ki| Giáo sư X nhận lại bộ bài sau khi đã được tráo bởi m lệnh k1,k2,…,km. Ông ta muốn rút bỏ vài lá bài ở trong bộ bài sao cho các số ghi trên các quân bài từ trên xuống dưới có thứ tự tăng dần. Nhiệm vụ của bạn là hãy giúp giáo sư X xác định số lượng ít nhất các lá bài phải trút bỏ. Input Dòng 1 chứa 2 số nguyên dương n,m (2<=n<=10^9; m<=10^5), Dòng 2 chứa m số nguyên dương k1,k2,…,km (1<=|ki| Các số trên một dòng được ghi cách nhau bởi một dấu cách. Output Một số nguyên là số lượng ít nhất các lá bài phải rút bỏ Sample input 3 2 -2 1 Sample Output 2
Added by: | sieunhan |
Date: | 2011-06-22 |
Time limit: | 0.904s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | ACM Regional Hanoi 2010 |