Hướng dẫn giải của AMSOI 2024 Round 4 - Hack điểm

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hack điểm

Sub 1 : ~N \le 9~ :

  • Ta xét tất cả các tập con của tập ~A~. Với mỗi tập con được xét, để tối ưu kết quả, ta gán tất cả các điểm số trong tập được chọn thành ~5~, và tính điểm tổng trung bình.
  • Ta có thể quản lí các tập con bằng bitmask ~mask~ với bit thứ ~i = 1~ tức phần tử thứ i được chọn
  • ĐPT: ~O(2^n*n)~

Sub 2 : ~N \le 10^5~ :

  • Gọi ~s = \sum_{i=1}^n A_i~, ta cần tăng ít các phần tử của ~A~ nhất để ~s/n \ge 4.5~.
  • Dễ thấy, để tối ưu nhất, ta tăng các số ~A_i~ bé lên 5. Như vậy ta sort lại dãy ~A~ tăng dần, sau đó duyệt qua dãy ~A~, tăng các vị trí ~A_i~ lên 5 và tìm vị trí gần nhất thỏa mãn ~s/n > 4.5~
  • ĐPT: ~O(nlogn)~

Code mẫu:

#include "bits/stdc++.h"

using namespace std;

#define ln "\n"
#define fast_cin()                  \
  ios_base::sync_with_stdio(false); \
  cin.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define int long long
int MOD = 1e9 + 7;
const int N = 1e5 + 7;
int n, a[N];

signed main() {
    fast_cin();
    cin >> n;
    int s = 0;
    for(int i = 1; i <= n; i++) cin >> a[i], s += a[i];
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++) {
        if((double)s/n >= 4.5) {
            cout << i-1;
            return 0;
        }
        s += 5 - a[i];
    }
    cout << n;
    cerr << "\nTime: " << clock() * 1000 / CLOCKS_PER_SEC;
}