Tập Hợp Dài Nhất

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
ami
Dạng bài
Điểm: 250 Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

ami có một mảng \(a\) gồm \(n\) phần tử \(a_1\), \(a_2\), ..., \(a_n\). Hai dãy số \(a\) và \(b\) được gọi là giống nhau nếu nó thoả cả hai điều kiện sau

  • Các số trong dãy \(a\) đều xuất hiện trong dãy \(b\).
  • Các số trong dãy \(b\) đều xuất hiện trong dãy \(a\).

Ví dụ, dãy [1 2 3 4] và dãy [1 1 2 3 4 4] là giống nhau, còn dãy [5 12 2001] và [18 12 2001] là khác nhau.

Các bạn cần tìm một đoạn con chuẩn dài nhất của mảng \(a\) mà đoạn con đó giống với dãy \(a\).

Một đoạn con của \(a\) được gọi là chuẩn nếu nó có độ dài nhỏ hơn độ dài của \(a\).

Input

  • Dòng đầu tiên chứa một số nguyên dương \(n\) là số phần tử trong mảng \(a\).

  • Dòng tiếp theo chứa \(n\) số nguyên dương \(a_i\) là một phần tử của mảng \(a\).

Output

  • Hãy in ra độ dài đoạn con chuẩn dài nhất của \(a\) mà đoạn con này giống với dãy \(a\). Nếu không tồn tại đoạn con nào, các bạn cần in ra -1.

Scoring

Trong tất cả các test, \(1 \leq a_i \leq 1000\).

  • Subtask \(1\) (\(50\%\) số điểm): \(1 \leq n \leq 100\).

  • Subtask \(2\) (\(50\%\) số điểm): \(1 \leq n \leq 1000\).

Example

Test 1

Input 
3
?2 3 6
Output 
-1

Test 2

Input 
2
?2 2
Output 
1
Note

Ở ví dụ 1, tất cả các dãy con chuẩn của \(a\) đều không giống với \(a\).

Ở ví dụ 2, tất cả dãy con chuẩn của \(a\) đều là [2] và giống với \(a\).

Bình luận


  • 1
    longkold00    4:25 p.m. 5 Tháng 11, 2021

    Đếm phân phối và 2 con trỏ :> thì sao nhỉ


    • 1
      VoBaThongL921    4:34 p.m. 5 Tháng 11, 2021

      em cũng nghĩ thế á anh, nhưng vì \(n\) nhỏ, time lại \(2s\) nên em làm 2 vòng for duyệt trâu và đếm phân phối chứ không làm 2 con trỏ cũng được (mà em vẫn sai 6 test:))


      • 1
        longkold00    11:16 p.m. 5 Tháng 11, 2021

        đếm phân phối là đủ để ac r em ới :V, thì e chỉ cần kiểm tra xem số lần xuất hiện của a1 và an có đồng thời = 1 không, nếu có thì return -1, ngược lại return n-1 là oke đó :V


        • 1
          VoBaThongL921    7:01 a.m. 6 Tháng 11, 2021 ← đã chỉnh sửa

          vch anh ac luôn rồi ạ:)

          • à em hiểu vì sao sai rồi:) đề kêu tìm dãy con dài nhất:)

      • 1
        longkold00    8:26 p.m. 5 Tháng 11, 2021

        để lát a code thử xem nếu xong sớm :>

      1 bình luận nữa