Bedao Mini Contest 06 - YUGIOH - VNOJ: VNOI Online Judge

Bedao Mini Contest 06 - YUGIOH

Điểm: 0,50 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Tác giả:

bedao

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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

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)~.

Bình luận

Hãy đọc nội quy trước khi bình luận.

-18
laikutef10 đã bình luận lúc 15, Tháng 9, 2021, 15:26
include<bits/stdc++.h>

define f 1e8

define ll long long

using namespace std;

bool check[10005]; ll a[10005]; int n,x,T=0,F=0; bool b[10005]; ll p[10005]; void input() { memset(check,1,sizeof(check)); freopen("yugioh.inp","r",stdin); freopen("yugioh.out","w",stdout); cin >> n >> x; for (int i=1;i<=n;i++) cin>>a[i]; } void era(int x) { memset(check,0,sizeof(check)); for (int i=1;i<=x;i++) check[i]=true; check[1]=0; for(int i = 2; ii <= x; i++) if(check[i]) for(int j = ii; j <=x ; j += i) check[j] = false; } void accept() { for (int i=1;i<=n;i++) if (check[a[i]]) { b[i]=1; T++; } else b[i]=0;

int tm=0; for (int i=1;i<=n;i++) { p[i]=tm; if (b[i]==0) tm++; } } void setting() { ll minn=100000005; for (int i=T;i<=n;i++) minn=min(minn,p[i]-p[i-T+1]); cout << minn;

} int main() { input(); era(x); accept(); setting();

return 0;

} code em sai cho nao` vay moi nguoi em dan newbie
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

1

casiofx580 đã bình luận lúc 5, Tháng 9, 2021, 4:52

xem test sai ở đâu vậy ạ

8

SPyofgame đã bình luận lúc 3, Tháng 9, 2021, 16:59 ← sửa 3 →

Bài hay phết UwU

7

letangphuquy đã bình luận lúc 3, Tháng 9, 2021, 17:04 ← chỉnh sửa →

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 đã bình luận lúc 3, Tháng 9, 2021, 18:41

And yes, giờ săn role Editorialist UwU

1

darkkcyan đã bình luận lúc 3, Tháng 9, 2021, 18:42

~UwU~

1

SPyofgame đã bình luận lúc 3, Tháng 9, 2021, 18:40

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