Nội dung Bài tập
- Mã:
- Greedy_contests
- Tên:
- Cuộc thi
- Dạng thi:
- oi
- Thang điểm:
- 3 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 256 MB
- Nguồn bài tập:
- Vinhdinhcoder
- Được tạo bởi:
- hungphitkn
Một hệ thống chấm bài tự động đang có N bài tập với độ khó khác nhau. Độ khó của bài tập thứ i là ai. Ban tổ chức muốn tổ chức một contest online. Contest cần lấy một tập con trong N bài tập trên với điều kiện không có bài tập có độ khó gấp hai lần độ khó của một bài khác, các bài tập không cần liên tiếp nhau.
Ban tổ chức muốn tạo một contest chứa nhiều bài tập nhất có thể. Hãy lập trình đưa ra số lượng bài tập lớn nhất có thể.
Input: Gồm hai dòng
- Dòng đầu chứa số nguyên N là số lượng bài tập
- Dòng thứ hai chứa N số nguyên là độ khó của các bài, mỗi số cách nhau đúng một khoản trắng.
Output:
- Gồm một số nguyên duy nhất là số lượng bài tập tối đa có thể chọn theo điều kiện trên.
Ví dụ:
Input
Output
10
1 2 5 6 7 10 21 23 24 29
4
Giải thích: 4 bài tập được chọn là các bài có độ khó: 21, 23, 24, 29
Giới hạn:
- Subtask1(50% số điểm): ai <= 10^9, n <= 10^3
- Subtask2(50% số điểm): ai <= 10^9, n <= 10^5
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
THPT_NK_DEQUY
#include <iostream>using namespace std;int main(){ cout << "Co ga...