Sắp xếp truyện tranh


Submit solution

Points: 3
Time limit: 1.0s
Memory limit: 250M

Author:
Problem type

Vincent làm một sinh viên năm nhất nhưng cậu ta rất chăm chỉ, ngoài việc học trên trường, cậu còn làm việc part-time tại một của hàng cho thuê đĩa truyện tranh. Công việc của cậu là sắp xếp lại các cuốn truyện theo đúng thứ tự (theo từng tập tăng dần).

Hôm nay có rất nhiều khác hàng ghé thăm cửa hàng và giờ đây thứ tự các tập truyện đã bị thay đổi. Vì vậy, cậu phải thực hiện công việc hằng ngày của mình là xếp lại chúng. Trên một hàng của giá sách chứa tập 1 đến N của bộ truyện nhưng không theo thứ tự.

Ở vị trí thứ i-th là Tập \(A_i\) của bộ truyện và Vincent muốn sắp xếp chúng theo thứ tự từ tập 1 đến N và để chúng ở hàng bên dưới của giá sách.

Vincent bắt đầu đi từ trái qua phải của giá sách, khi cậu ta thấy tập 1, cậu sẽ cho xuống hàng bên dưới và tiếp tục đi tiếp và tìm tập 2, khi thấy tập 2 cậu ta lại cho xuống hàng dưới, cứ tiếp như vậy đi hết hàng của giá sách. Khi trên hàng còn truyện, cậu lại tiếp tục quay lại từ đầu hàng và lại đi từ trái qua phải, tiếp tục lặp lại đến khi trên hàng của giá sách không còn tập truyện nào.

Ví dụ:

Giả sử thứ tự các tập trên hàng của giá sách lúc này là 4, 5, 3, 1, 2, 6.

Lượt 1. Cậu đi từ trái qua phải và chuyển được tập 1 và 2 xuống hàng bên dưới.

Lượt 2. Cậu đi từ trái qua phải và chuyển được tập 3 xuống hàng bên dưới.

Lượt 3. Cậu đi từ trái qua phải và chuyển được tập 4, 5, 6 xuống hàng bên dưới.

Input:

  • Dòng đầu tiên chứ một số nguyên mô tả số lượng testcase T \(( 1 \le T \le 100)\)
  • Với mỗi testcase là một số nguyên N. \(( 1 \le N \le 200,000)\)
  • Tiếp đó là N số nguyên \(A_1\), \(A_2\), ... \(A_n\) với \(( 1 \le A_i \le N)\)
  • Với \(A_i\) đại diện cho tập của cuốn truyện tại vị trí thứ i-th từ trái qua phải của hàng.

Output:

  • Dòng duy nhất gồm 1 số nguyên duy nhất X (theo định dạng #Case t: X với t là testcase tương ứng) chỉ số lượt mà Vincent phải đi từ trái qua phải hàng đến khi bộ truyện được sắp xếp
  • Hay nói cách khác, trên hàng không còn tập truyện nào.

Example:

Input:

3
3
3 2 1
6
4 5 3 1 2 6
2
1 2

Output:

#Case 1: 3
#Case 2: 3
#Case 3: 1

Comments

There are no comments at the moment.