Văn nghệ (HSG9 NB 2023)

Điểm: 1200 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: vannghe.inp

Output: vannghe.out

Tác giả:

Sunlight

Dạng bài

Trong một cuộc thi văn nghệ, có $N$ thí sinh tham gia thi. Cuộc thi được tổ chức với nhiều vòng thi khác nhau. Mỗi vòng thi, thí sinh biểu diễn tốt nhất được $N$ điểm, thí sinh tốt thứ nhì được $N-1$ điểm, thí sinh tốt thứ ba được $N-2$ điểm, ... thí sinh xếp cuối cùng được $1$ điểm. Điểm chung cuộc của từng thí sinh là tổng điểm của thí sinh đó đạt được qua các vòng thi. Thí sinh nào có điểm chung cuộc cao nhất sẽ giành giải nhất. Nếu có nhiều thí sinh cùng đạt điểm chung cuộc cao nhất thì tất cả họ đều giành giải nhất.

Hiện nay, chỉ còn một vòng thi nữa là cuộc thi kết thúc, tổng điểm của các thí sinh đạt được đến vòng thi này lần lượt là $a_1, a_2, ..., a_N$

Yêu cầu: Có bao nhiêu thí sinh có cơ hội giành được giải nhất chung cuộc?

Input, Output và Subtasks

Input: (vannghe.inp)

Dòng đầu tiên chứa số nguyên $N$ ( $3\le N\le 10^5$ ) là số lượng thí sinh tham gia cuộc thi
$N$ dòng tiếp theo, mỗi dòng ghi một số nguyên $a_i$ ( $0<a_i\le 10^6, 1\le i\le N$ ) là số điểm của thí sinh thứ $i$ trước vòng thi cuối cùng

Output: (vannghe.out)

Dòng 1 ghi số lượng thí sinh có cơ hội giành được giải nhất chung cuộc
Dòng 2 ghi ra số thứ tự của các thí sinh có cơ hội giành được giải nhất chung cuộc theo thứ tự từ bé đến lớn, mỗi số cách nhau bởi một khoảng trắng

Subtasks

Subtask 1 $(40\%)$ : $N\le 100$
Subtask 2 $(40\%)$ : $N\le 10^3$
Subtask 3 $(20\%)$ : Không có ràng buộc gì thêm

Sample 1

Input (vannghe.inp)

Output (vannghe.out)

3
1 2 4

Note

Thí sinh thứ nhất có cơ hội giành được giải nhất nếu vòng thi cuối được $4$ điểm; thí sinh thứ hai chỉ giành được $2$ điểm, thí sinh thứ ba giành được $3$ điểm và thí sinh thứ tư giành được $1$ điểm. Khi đó thí sinh thứ nhất có điểm chung cuộc là $13$ và giành giải nhất
Thí sinh thứ hai có cơ hội giành được giải nhất nếu đạt được $4$ điểm ở vòng cuối cùng mà không cần quan tâm đến điểm ở vòng cuối của các thí sinh còn lại
Thí sinh thứ ba không còn cơ hội giành được giải nhất
Thí sinh thứ tư chỉ cần đạt được $3$ hoặc $4$ điểm ở vòng cuối là có cơ hội giành được giải nhất

Bình luận

Không có bình luận nào.