Thông tin Bài tập Bảng xếp hạng Thống kê

https://meet.jit.si/DungTanKhoa

codelearn.io

HỌC SINH HAM CHƠI (TRUNG BINH CONG LON NHAT)

Tóm tắt đề bài

Cho một dãy số gồm \(N\) số nguyên dương (\(1 \le N \le 10^5\))[cite: 17].

  • Tìm một dãy con liên tiếp sao cho trung bình cộng các phần tử là lớn nhất[cite: 17].
  • In ra kết quả trung bình cộng lớn nhất đó[cite: 17].

Hướng giải quyết đơn giản nhất (Nhận xét toán học)

  1. Giả sử giá trị lớn nhất trong toàn bộ dãy số là \(M\).
  2. Nếu ta chọn một dãy con chỉ gồm đúng 1 phần tử duy nhất có giá trị \(M\), thì trung bình cộng của đoạn con này chính bằng \(M\).
  3. Nếu ta ghép thêm bất kỳ phần tử nào khác nhỏ hơn \(M\) vào đoạn con, trung bình cộng chắc chắn sẽ bị kéo giảm xuống (\(< M\)).
  4. Do đó, trung bình cộng lớn nhất của một đoạn con luôn luôn bằng chính phần tử lớn nhất trong dãy (\(M\)).
  5. Bài toán đơn giản chỉ là: duyệt qua dãy và tìm giá trị lớn nhất[cite: 17].

Điền vào chỗ trống

C++
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    ... >> n;

    long long max_val = 0;

    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        max_val = max(max_val, ...);
    }

    cout << ... << "\n";

    return 0;
}
YUGIOH (THAM LAM CO BAN)

Tóm tắt đề bài

Yugi có \(n\) lá bài[cite: 14]. Lá thứ \(i\) có sức mạnh \(A_i\)[cite: 14]:

  • Nếu \(A_i \ge 0\): Yugi được cộng \(A_i\) máu[cite: 14].
  • Nếu \(A_i < 0\): Kaiba bị trừ \(\vert{}A_i\vert{}\) máu[cite: 14].
  • Yugi muốn trừ máu Kaiba nhiều nhất có thể khi được dùng tối đa \(m\) lá bài[cite: 14].
  • In ra số máu tối đa Kaiba bị trừ[cite: 14].

Hướng giải quyết đơn giản nhất

  1. Chỉ những lá bài có giá trị âm (\(A_i < 0\)) mới trừ máu của Kaiba[cite: 14].
  2. Muốn trừ máu Kaiba nhiều nhất, ta cần chọn những lá có giá trị âm nhỏ nhất (tức là \(\vert{}A_i\vert{}\) lớn nhất)[cite: 14].
  3. Các bước làm:
    • Sắp xếp dãy số \(A\) tăng dần bằng sort(a, a + n).
    • Dùng vòng lặp duyệt tối đa \(m\) lá bài đầu tiên: nếu lá nào có giá trị âm (\(a[i] < 0\)), ta cộng dồn \(\vert{}a[i]\vert{} = -a[i]\) vào kết quả[cite: 14].
    • Dừng lại nếu gặp số không âm (\(a[i] \ge 0\)) hoặc đã chọn đủ \(m\) lá bài[cite: 14].

Điền vào chỗ trống

C++
#include <iostream>
#include <algorithm>
using namespace std;

int a[10005];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    ... >> n >> m;

    for (int i = 0; i < n; i++) {
        cin >> a[...];
    }

    // Sắp xếp mảng tăng dần để các số âm nhỏ nhất lên đầu
    sort(a, a + ...);

    long long ans = 0;

    // Chọn tối đa m lá bài
    for (int i = 0; i < m; i++) {
        if (a[i] < 0) {
            ans += -a[...];
        } else {
            ...; // Gặp số không âm thì dừng vì không trừ máu Kaiba
        }
    }

    cout << ... << "\n";

    return 0;
}
GÀU NƯỚC (CÔNG THỨC 1 DÒNG TOÁN HỌC)

Tóm tắt đề bài

Có \(L\) lít nước (\(1 \le L \le 10^{18}\)), có vô hạn gàu loại \(5\) lít và \(2\) lít[cite: 15].

  • Tìm tổng số gàu ít nhất để đong được ít nhất \(L\) lít nước[cite: 15].

Hướng giải quyết bằng mẹo

  1. Vì chỉ cần đong ít nhất \(L\) lít (được phép dư), dùng gàu \(5\) lít luôn luôn có lợi hơn gàu \(2\) lít[cite: 15].
  2. Ta chỉ cần dùng toàn bộ gàu \(5\) lít[cite: 15].
  3. Số gàu cần dùng là phép chia làm tròn lên: \((L + 4) / 5\)[cite: 15].

Điền vào chỗ trống

C++
#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long L;
    ... >> L;

    // Làm tròn lên của phép chia L cho 5
    long long ans = (L + ...) / ...;

    cout << ... << "\n";

    return 0;
}
MUA XĂNG (CHI PHI TOI THIEU)

Tóm tắt đề bài

Cần mua đúng chính xác \(N\) lít xăng (\(1 \le N \le 10^9\))[cite: 16]:

  • Mua bình 1L tốn giá \(a\) đồng[cite: 16].
  • Mua bình 2L tốn giá \(b\) đồng[cite: 16].
  • Tìm chi phí ít nhất để mua đúng \(N\) lít[cite: 16].

Hướng giải quyết đơn giản nhất

  1. Giá của 2 lít xăng khi mua lẻ từng bình 1L là \(2 \times a\) đồng[cite: 16].
  2. So sánh giữa việc mua 1 bình 2L (\(b\) đồng) và mua 2 bình 1L (\(2 \times a\) đồng)[cite: 16]:
    • Trường hợp 1 (\(2 \times a \le b\)): Mua bình 1L luôn rẻ hơn hoặc bằng \(\rightarrow\) toàn bộ \(N\) lít đều mua bằng bình 1L với chi phí \(N \times a\)[cite: 16].
    • Trường hợp 2 (\(2 \times a > b\)): Mua bình 2L rẻ hơn \(\rightarrow\) ưu tiên mua tối đa các bình 2L:
    • Mua \((N / 2)\) bình loại 2L với giá \((N / 2) \times b\)[cite: 16].
    • Nếu \(N\) lẻ (\(N \% 2 == 1\)), mua thêm \(1\) bình 1L với giá \(a\)[cite: 16].
  3. Dùng kiểu dữ liệu long long để tránh tràn số vì \(N, a, b \le 10^9\)[cite: 16].

Điền vào chỗ trống

C++
#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long n, a, b;
    ... >> n >> a >> b;

    long long ans = 0;

    if (2 * a <= b) {
        // Mua toàn bộ bằng bình 1 lít
        ans = n * ...;
    } else {
        // Ưu tiên mua bình 2 lít
        ans = (n / 2) * ... + (n % 2) * ...;
    }

    cout << ... << "\n";

    return 0;
}

Bình luận

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

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