JOI 2026 - Class Division

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 1000 (p) Thời gian: 2.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Có \(N\) học sinh lớp 10 của trường JOI, được đánh số từ \(1\) đến \(N\). Điểm thi của học sinh \(i\) là \(A_i\) và không phải tất cả điểm đều bằng nhau.

Dựa trên kết quả kỳ thi này, nhà trường chia lớp cho năm học tiếp theo. Chọn một số nguyên \(x\): học sinh có điểm ít nhất \(x\) vào lớp nâng cao, các học sinh còn lại vào lớp thường. Mỗi lớp phải có ít nhất một học sinh. Cách chia được chọn sao cho chênh lệch số học sinh giữa hai lớp là nhỏ nhất; nếu vẫn có nhiều cách, chọn cách có ít học sinh lớp nâng cao hơn.

Hãy tìm điểm thấp nhất trong lớp nâng cao của cách chia được chọn.

Dữ liệu vào

Dòng đầu chứa \(N\). Dòng thứ hai chứa \(A_1, A_2, \ldots, A_N\).

Dữ liệu ra

In điểm thấp nhất của một học sinh trong lớp nâng cao.

Ràng buộc

  • \(2 \le N \le 500000\).
  • \(1 \le A_i \le 10^9\).
  • Tồn tại \(i < j\) sao cho \(A_i \ne A_j\).
  • Mọi giá trị số trong dữ liệu vào đều là số nguyên.

Phân nhóm

  1. \(20\) điểm: \(N = 3\).
  2. \(20\) điểm: mỗi \(A_i\) thuộc \(\{500, 800, 1000\}\).
  3. \(20\) điểm: các \(A_i\) đôi một khác nhau.
  4. \(40\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

Input 
3
1000 500 800
Output 
1000
Giải thích

Chẳng hạn, chọn \(x=900\) thì học sinh \(1\) vào lớp nâng cao, còn học sinh \(2,3\) vào lớp thường. Cách chia còn lại là cho học sinh \(1,3\) vào lớp nâng cao và học sinh \(2\) vào lớp thường, có thể thực hiện bằng cách chọn \(x=800\). Cả hai cách đều có chênh lệch sĩ số bằng \(1\), nên chọn cách thứ nhất vì lớp nâng cao có ít học sinh hơn. Điểm thấp nhất của lớp này là \(1000\).

Ví dụ này thỏa mãn các nhóm \(1\), \(2\), \(3\), \(4\).

Ví dụ 2

Input 
6
100 75 41 75 13 89
Output 
89
Giải thích

Chọn \(x=89\) thì học sinh \(1,6\) vào lớp nâng cao, còn học sinh \(2,3,4,5\) vào lớp thường. Điểm thấp nhất của lớp nâng cao là \(89\).

Ví dụ này thỏa mãn các nhóm \(4\).

Ví dụ 3

Input 
6
20 25 12 7 13 16
Output 
16
Giải thích

Ví dụ này thỏa mãn các nhóm \(3\), \(4\).

Ví dụ 4

Input 
8
364353982 103422534 437367896 91518637 364353982 221490368 437367896 103422534
Output 
364353982
Giải thích

Ví dụ này thỏa mãn các nhóm \(4\).

Nguồn

JOI 2025/2026 - Vòng loại 2, bài Class Division.

Tài liệu gốc của Japanese Committee for IOI được phát hành theo giấy phép CC BY-SA 4.0.

Tệp

Bình luận

Mới nhất
Tải bình luận...

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

Kỳ thi: