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

Bedao Mini Contest 06 - YUGIOH

Points: 0.50 (partial)

Time limit: 1.0s

Memory limit: 256M

Input: stdin

Output: stdout

Author:

bedao

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

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.
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
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 :(