Trong phòng thí nghiệm thuật toán bí mật của Code Jam, chúng tôi dành vô số giờ vật lộn với một trong những bài toán phức tạp nhất thời đại: sắp xếp hiệu quả một danh sách số nguyên theo thứ tự không giảm. Sau khi nghiên cứu cẩn thận thuật toán bubble sort kinh điển, chúng tôi vui mừng công bố một biến thể mới.

Phép toán cơ bản của bubble sort chuẩn là xét một cặp số kề nhau và đảo cặp đó nếu số bên trái lớn hơn số bên phải. Thuật toán của chúng tôi lại xét một nhóm ba số kề nhau; nếu số ngoài cùng bên trái lớn hơn số ngoài cùng bên phải, nó đảo ngược cả nhóm. Vì đây là một kiểu “bubble sort theo bộ ba”, chúng tôi gọi tắt nó là Trouble Sort.

  TroubleSort(L): // L is a 0-indexed list of integers
    let done := false
    while not done:
      done = true
      for i := 0; i < len(L)-2; i++:
        if L[i] > L[i+2]:
          done = false
          reverse the sublist from L[i] to L[i+2], inclusive

Ví dụ, với \(L=\) 5 6 6 4 3, Trouble Sort diễn tiến như sau:

• Lượt thứ nhất:

  • Xét 5 6 6, không làm gì: 5 6 6 4 3.
  • Xét 6 6 4, nhận thấy \(6>4\), đảo bộ ba: 5 4 6 6 3.
  • Xét 6 6 3, nhận thấy \(6>3\), đảo bộ ba: 5 4 3 6 6.

• Lượt thứ hai:

  • Xét 5 4 3, nhận thấy \(5>3\), đảo bộ ba: 3 4 5 6 6.
  • Xét 4 5 6, không làm gì: 3 4 5 6 6.
  • Xét 5 6 6, không làm gì: 3 4 5 6 6.

• Sau đó, lượt thứ ba xét cả ba bộ ba mà không làm gì, nên thuật toán kết thúc.

Chúng tôi đang háo hức chuẩn bị giới thiệu Trouble Sort tại hội nghị Special Interest Group in Sorting ở Hawaii thì một thực tập sinh vừa chỉ ra vấn đề: Trouble Sort có thể không sắp xếp danh sách đúng! Chẳng hạn, hãy xét danh sách 8 9 7.

Chúng tôi cần bạn giúp nghiên cứu thêm. Cho một danh sách gồm \(N\) số nguyên, hãy xác định Trouble Sort có sắp xếp thành công danh sách theo thứ tự không giảm hay không. Nếu không, hãy tìm chỉ số — đánh số từ 0 — của lỗi sắp xếp đầu tiên sau khi thuật toán kết thúc, tức vị trí đầu tiên có giá trị lớn hơn giá trị đứng ngay sau nó trong danh sách cuối cùng.

Dữ liệu vào

Dòng đầu tiên chứa số lượng test \(T\). Mỗi test gồm hai dòng: dòng thứ nhất chứa số nguyên \(N\), là số phần tử của danh sách; dòng thứ hai chứa \(N\) số nguyên \(V_i\), là các giá trị trong danh sách.

Dữ liệu ra

Với mỗi test, in một dòng Case #x: y, trong đó x là số thứ tự test bắt đầu từ 1; y là OK nếu Trouble Sort sắp xếp danh sách đúng, hoặc là chỉ số đánh từ 0 của lỗi sắp xếp đầu tiên như mô tả ở trên.

Ràng buộc

• \(1\le T\le100\).
• \(0\le V_i\le10^9\) với mọi \(i\).

Phân nhóm

Test Set 1 (công khai): \(3\le N\le100\).

Test Set 2 (ẩn): \(3\le N\le10^5\).

Lưu ý đặc biệt

Test Set 2 có lượng dữ liệu vào lớn, nên bộ đọc không có đệm có thể khiến việc đọc chậm hơn. Ngoài ra, hãy nhớ rằng một số ngôn ngữ mặc định có bộ đệm đầu vào nhỏ.

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
5
5 6 8 4 3
3
8 9 7

Case #1: OK
Case #2: 1

Nguồn

Google Code Jam 2018, Vòng loại, bài Trouble Sort.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.