TRAOGIAI - Trao giải

Xem dạng PDF
Gửi bài giải
Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Tác giả:
Hiếu Nguyễn
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Kỳ thi học sinh giỏi khối ~10~ môn Tin học năm nay có ~n~ học sinh tham gia với tổng điểm của các học sinh lần lượt là các số tự nhiên ~d_1, d_2, …, d_n~. BTC quyết định chọn các học sinh để trao giải theo nguyên tắc sau: Đầu tiên chọn ~[\frac{n}{2}]~ (phần nguyên của ~\frac{n}{2}~) số học sinh có điểm từ cao xuống thấp, sau đó chọn thêm những học sinh bằng điểm với học sinh có điểm thấp nhất trong số này. Em hãy giúp BTC tính số lượng học sinh có giải.

Input

  • Dòng đầu chứa số nguyên dương ~n~;
  • Dòng thứ hai chứa ~n~ số tự nhiên ~d_1, d_2, …, d_n~.Hai số liên tiếp trên một dòng được ghi cách nhau một dấu cách.

Giới hạn:

  • ~2 ≤ n ≤ 10^5; 0 ≤ d_i ≤ 10^6~.

Output

  • Một số nguyên duy nhất là số học sinh có giải.

Sample

Input #1
5
98 97 100 98 98
Output #1
4

Hint

Xem xét #1:

  • ~[\frac{n}{2}] = [\frac{5}{2}] = 2~. Hai học sinh được chọn có điểm từ cao xuống thấp là ~100~ và ~98~, tiếp theo, còn ~2~ học sinh cùng đạt ~98~ điểm nữa cũng được chọn. Vậy có ~4~ học sinh có giải.

Problem source: Chuyên Sơn La Online Judge

Bình luận

Please read the guidelines before commenting.


  • 0
    minhtriszw  đã bình luận lúc 19, Tháng 4, 2026, 10:24

    1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1


    • 0
      minhtriszw  đã bình luận lúc 19, Tháng 4, 2026, 10:24

      lam kieu j v


  • 0
    minhtai2013vn  đã bình luận lúc 3, Tháng 4, 2026, 12:43

    TRAOGIAI


  • 0
    Haiquan  đã bình luận lúc 14, Tháng 1, 2026, 13:30

    include <bits/stdc++.h>

    using namespace std;

    long long a[100005];

    int main() { long long n; cin>>n; for (long long i = 0; i < n; i++) cin >> a[i]; sort(a, a + n, greater<long long>()); long long b = n / 2; long long c = a[b - 1]; long long d = 0; for (long long i = 0; i < n && a[i] >= c; i++) d++;

    cout << d << "\n";

return 0;

    }


  • 0
    Haiquan  đã bình luận lúc 13, Tháng 1, 2026, 7:47 ← chỉnh sửa

    hello


    • 0
      Haiquan  đã bình luận lúc 13, Tháng 1, 2026, 7:52

      hhe


  • 0
    Haiquan  đã bình luận lúc 13, Tháng 1, 2026, 7:44 ← chỉnh sửa

    chao


  • 0
    buinguyenhung2025  đã bình luận lúc 6, Tháng 12, 2025, 0:43

    ok


  • 1
    hgb_donut  đã bình luận lúc 3, Tháng 12, 2025, 14:18

    include <bits/stdc++.h>

    using namespace std; long long n; int main() { cin>> n; long long d[n]; for(int i=0;i<n;++i) { cin>>d[i];} sort(d,d+n,greater<int>()); long long a=n/2-1; long long s=d[a]; long long t=0; for(int i=0;i<n;++i) { if(d[i]>=s) t++; } cout<<t<<endl; return 0; }


  • -2
    congtyluuthaibao1978  đã bình luận lúc 27, Tháng 11, 2025, 12:14

    include <bits/stdc++.h>

    using namespace std;

    int main() { ios::syncwithstdio(false); cin.tie(nullptr);

    int n;
cin >> n;
vector<int> d(n);
int max_point = 0;
for(int i = 0; i < n; i++) {
    cin >> d[i];
    max_point = max(max_point, d[i]);
}

vector<int> freq(max_point + 1, 0);
for(int i = 0; i < n; i++) freq[d[i]]++;

int need = n / 2; // floor(n/2)
int sum = 0;
int threshold = -1;

// duyệt từ điểm cao xuống
for(int p = max_point; p >= 0; p--) {
    if(freq[p] == 0) continue;
    if(sum + freq[p] >= need) {
        threshold = p;
        break;
    }
    sum += freq[p];
}

// đếm tất cả học sinh có điểm >= threshold
int count = 0;
for(int i = 0; i < n; i++)
    if(d[i] >= threshold) count++;

cout << count << "\n";
return 0;

    }


  • -1
    Minh_Khoa  đã bình luận lúc 17, Tháng 10, 2024, 7:25

    đr test 2 là gì vậy