Khảo sát dân cư

Xem dạng PDF

Gửi bài giải

Điểm: 0,05 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Nguồn bài:
Viettel Programming Challenge 2023
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Để chuẩn bị cho kế hoạch cải tạo, nâng cấp hạ tầng kết nối Internet trên cả nước, công ty VT tiến hành khảo sát dung lượng Internet sử dụng tại các địa phương.

Cuộc khảo sát được tiến hành trên ~n~ tỉnh và thành phố trực thuộc trung ương trên cả nước. Các thành phố này được đánh số từ ~1~ đến ~n~. Kết quả khảo sát cho thấy tỉnh/thành phố thứ ~i~ có dân số là ~p_i~ và dung lượng Internet sử dụng trong tháng vừa qua tại đây là ~c_i~.

Công ty VT muốn lựa chọn một số địa phương trọng điểm, có nhu cầu sử dụng Internet cao để tiến hành nâng cấp hạ tầng kết nối. Bởi vậy, công ty sẽ chọn ra một nhóm các tỉnh/thành phố trọng điểm, là nhóm các địa phương sao cho dung lượng sử dụng bình quân đầu người của các địa phương này là lớn nhất. Dung lượng Internet sử dụng bình quân đầu người được tính bằng tổng dung lượng Internet sử dụng của các địa phương trong nhóm chia cho tổng dân số của các địa phương trong nhóm.

Nói cách khác, công ty muốn chọn ra một dãy các địa phương ~i_1, i_2, \ldots, i_k~ sao cho:

  • ~k > 0~

  • ~1 \leq i_1 < i_2 < \ldots < i_k \leq n~

  • Giá trị ~\frac{c_{i_1} + c_{i_2} + \ldots + c_{i_k}}{p_{i_1} + p_{i_2} + \ldots + p_{i_k}}~ lớn nhất.

Hãy giúp công ty tìm ra nhóm địa phương trọng điểm.

Input

Dòng đầu tiên chứa số nguyên ~n~ ~(1 \leq n \leq 50)~ là số tỉnh/thành phố được tiến hành khảo sát.

Dòng thứ hai chứa ~n~ số nguyên ~p_1, p_2, \ldots, p_n~ ~(1 \leq p_i \leq 2 \cdot 10^7)~ lần lượt là dân số của các tỉnh/thành phố trong cuộc khảo sát.

Dòng thứ ba chứa ~n~ số nguyên ~c_1, c_2, \ldots, c_n~ ~(1 \leq c_i \leq 2 \cdot 10^8)~ lần lượt là tổng dung lượng Internet trong tháng vừa qua tại các tỉnh/thành phố được tiến hành khảo sát.

Output

Dòng đầu tiên in ra số nguyên ~k~ ~(1 \leq k \leq n)~ là số tỉnh/thành phố trong nhóm địa phương trọng điểm.

Dòng thứ hai in ra ~k~ số nguyên ~(1 \leq i_1 < i_2 < \ldots < i_k \leq n)~ thể hiện các địa phương trong nhóm trọng điểm này.

Nếu có nhiều nhóm với cùng dung lượng Internet sử dụng bình quân đầu người lớn nhất, bạn có thể in ra một nhóm bắt kỳ.

Sample Input 1

4
10 10 10 10
47 47 47 47

Sample Output 1

3
1 2 4

Sample Input 2

4
1234567 2345678 3456789 4567890
2345678 3456789 4567890 5678901

Sample Output 2

1
1

Sample Input 3

5
98 120 40 135 40
4606 5167 1880 1351 1879

Sample Output 3

2
1 3

Sample Input 4

1
1
20000000

Sample Output 4

1
1

Bình luận

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



  • 0
    AI  đã bình luận lúc 24, Tháng 3, 2024, 4:10

    Bài này mặc dù nó bảo in ra khu dân cư thế nào cũng được (tức là không nói sắp xếp tăng dần) nhưng mà mình phải sắp xếp nó mới cho ăn full hay sao ý, còn không chết tầm 6, 7 tests gì đó -_-

    Ai đó hiểu rõ giải thích giúp mình với T_T


  • -3
    sz16  đã bình luận lúc 3, Tháng 8, 2023, 11:53

    Không liên quan nhưng sao không lấy n<=63 cho nó đẹp nhỉ?


  • -12
    Xcode  đã bình luận lúc 31, Tháng 7, 2023, 9:34

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.