Xóa số (THTB N.An 2021)
Xem PDF
Điểm:
1200 (p)
Thời gian:
1.0s
Bộ nhớ:
1G
Input:
bàn phím
Output:
màn hình
Cho một dãy số nguyên dương gồm \(N\) phần tử. Từ dãy số đó, hãy xoá đi ít phần tử nhất để các phần tử còn lại thoả mãn tính chất sau: với mỗi hai phần tử \(x, y\) bất kì trong dãy còn lại, \(x\) chia hết cho \(y\) hoặc \(y\) chia hết cho \(x\).
Yêu cầu: Cho dãy số nguyên gồm \(N\) phần tử, đếm số lượng phần tử cần xoá đi ít nhất để thoả mãn yêu cầu bài toán.
Input
Vào từ thiết bị nhập chuẩn theo khuôn dạng:
- Dòng đầu tiên chứa số nguyên dương \(N\);
- Dòng thứ hai chứa \(N\) số nguyên dương, các số cách nhau bởi dấu cách và có giá trị không vượt quá \(10^6\).
Output
- Ghi ra thiết bị ra chuẩn một số nguyên duy nhất – số lượng phần tử cần xoá đi ít nhất để thoả mãn yêu cầu bài toán.
Scoring
- Subtask #1 (\(50\%\) số điểm): \(N \leq 20\);
- Subtask #2 (\(30\%\) số điểm): \(N \leq 5000\);
- Subtask #3 (\(20\%\) số điểm): \(N \leq 10^6\);
Example
Test 1
Input
5
6 16 3 2 4Output
2Note
Có thể xoá đi 2 số 6 và 3. Dãy còn lại: 16, 2, 4 đảm bảo tính chất mỗi hai phần tử \(x\) và \(y\) bất kì, \(x\) chia hết cho \(y\) hoặc \(y\) chia hết cho \(x\).
Bình luận
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
-
0
Haidepzai
10:54 p.m. 31 Tháng 7, 2024
4 bình luận nữacho ý tưởng đấy, làm j đc