Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Toán rời rạc] Kiểm tra song ánh

    Một ánh xạ f:A→Af: A \to Af:A→A với A={1,…,n}A=\{1,\ldots,n\}A={1,…,n} là song ánh (bijection) nếu nó vừa đơn ánh (injective: các giá trị đôi một khác nhau) vừa toàn ánh (surjective: phủ hết AAA). Trên tập hữu hạn cùng kích thước, song ánh tương đương với việc fff là một hoán vị của AAA.

    Cho f(1),f(2),…,f(n)f(1), f(2), \ldots, f(n)f(1),f(2),…,f(n) (mỗi giá trị thuộc {1,…,n}\{1,\ldots,n\}{1,…,n}), hãy in YES nếu fff là song ánh, ngược lại NO.

    Ví dụ: f=(2,3,1)f = (2,3,1)f=(2,3,1) là hoán vị → YES; f=(1,1,2)f=(1,1,2)f=(1,1,2) không đơn ánh → NO.

    • Định dạng đầu vào:

      Dòng 1: nnn. Dòng 2: nnn số nguyên f(1),…,f(n)f(1),\ldots,f(n)f(1),…,f(n), mỗi số thuộc [1,n][1,n][1,n].

    • Ràng buộc đầu vào:

      1≤n≤1051 \le n \le 10^51≤n≤105.

    • Định dạng đầu ra:

      Một dòng: YES nếu song ánh, ngược lại NO.

    Ví dụ:

    Đầu vào:

    3
2 3 1

    Đầu ra:

    YES

    Giải thích:

    $f=(2,3,1)$ chứa đủ và đôi một khác nhau các giá trị 1,2,3 → hoán vị → YES.

    Đang tải editor...