Bedao Mini Contest 06 - YUGIOH

View as PDF

Submit solution


Points: 0.50 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Như một đoạn phim, các giấc mơ của Muối biến hóa liên tục, giờ đây Muối là một bài thủ kỳ cựu trong trò Yugioh. Không phải ngẫu nhiên người ta gọi Muối là "Vua Trò Chơi". Một ngày đẹp trời, Muối đã đụng độ chân ái của đời mình, đó chính là HienJeony. Bản tính vốn toxic nhưng HienJeony đánh bộ bài còn toxic hơn khiến Muối phải khốn đốn mặc dù đã phòng thủ rất quyết liệt. Đương nhiên Muối không phải Yugi trong truyện nên không thể sử dụng "sức mạnh tình bạn" được nhưng Muối chắc chắn là nhân vật chính trong giấc mơ của mình nên Muối đã bốc được một lá Spell có thể giúp Muối lật kèo, chuyển bại thành thắng.

Lá Spell cho phép Muối lấy ~n~ lá bài quái thú có trong bộ bài lên tay, quái thú thứ ~i~ có sức tấn công là ~a_i~. Muối phải xếp bài nhanh nhất có thể sao cho các quái thú có sức tấn công là một số nguyên tố bé hơn hoặc bằng ~X~ được đặt cạnh nhau trong bộ bài. Biết rằng mỗi bước sắp xếp tương ứng với việc đổi chỗ ~2~ lá bài bất kỳ trong ~n~ lá.

Nếu Muối không thể xếp bài nhanh nhất thì Muối sẽ thua và tổn hại tên gọi "Vua Trò Chơi", ngược lại HienJeony sẽ thua và phải bỏ tính toxic suốt đời. Hãy tính giúp Muối số bước sắp xếp ít nhất để Muối có thể thắng. Biết rằng trong bộ bài của Muối có những lá bài vô dụng cực kỳ.

Input

  • Dòng thứ nhất gồm ~2~ số nguyên dương ~n~ và ~X~ ~(1 \leq n, X \leq 10^6)~.
  • Dòng thứ hai gồm ~n~ số nguyên mô tả các lá bài ~a_i~ ~(|a_i| \leq 10^9)~.

Output

  • Một dòng duy nhất in ra số bước sắp xếp ít nhất thỏa mãn.

Sample Input

10 10
2 1 5 4 7 8 5 12 3 10

Sample Output

2

Subtask

  • ~50\%~ số test có ~1 \leq n \leq 10^3~, ~1 \leq X \leq 10^4~, ~|a_i| \leq 10^4~.
  • ~50\%~ số test có ~1 \leq n, X \leq 10^6~, ~|a_i| \leq 10^9~.

Giải thích

Cần ít nhất 2 bước để sắp xếp thỏa mãn là thực hiện ~swap(a_1, a_4)~ và ~swap(a_6,a_9)~.


Comments

Please read the guidelines before commenting.



  • -15
    laikutef10  commented on Sept. 15, 2021, 3:26 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 0
    casiofx580  commented on Sept. 5, 2021, 4:52 a.m.

    xem test sai ở đâu vậy ạ


  • 8
    SPyofgame  commented on Sept. 3, 2021, 4:59 p.m. edit 3

    Bài hay phết UwU


    • 6
      letangphuquy  commented on Sept. 3, 2021, 5:04 p.m. edited

      Tui có viết sol bài Girls với Pyramid nhưng không bình luận (theo nội quy). Ông đừng viết 2 bài đó nữa nha.

      anyway SPyofgame come back. orz. OTL


      • 0
        SPyofgame  commented on Sept. 3, 2021, 6:41 p.m.

        And yes, giờ săn role Editorialist UwU


        • 1
          darkkcyan  commented on Sept. 3, 2021, 6:42 p.m.

          ~UwU~


      • 1
        SPyofgame  commented on Sept. 3, 2021, 6:40 p.m.

        Thực ra là bọn mình viết song song rồi nên tui ko hủy được :(