1. Tính Toán Tổng Dãy Số Với Chu Kỳ Đảo Dấu

Bài toán yêu cầu tính tổng của một dãy số nguyên dương liên tiếp từ 1 đến n, trong đó dấu của các số được thay đổi theo chu kỳ. Cụ thể, cứ mỗi m số thì dấu sẽ được đảo ngược một lần, bắt đầu với dấu âm. Điều kiện tiên quyết là n phải chia hết cho 2m.

Thay vì sử dụng vòng lặp để duyệt qua từng phần tử dẫn đến độ phức tạp O(n) và nguy cơ超时 (timeout) khi dữ liệu lớn, ta có thể phân tích quy luật toán học. Mỗi chu kỳ gồm 2m số sẽ có tổng bằng m². Vì tổng số phần tử là n, số chu kỳ đầy đủ là n / (2m). Do đó, kết quả cuối cùng có thể tính trực tiếp bằng công thức O(1): (n * m) / 2.

import java.util.Scanner;

public class SequenceSumCalculator {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        if (scanner.hasNextInt()) {
            int limit = scanner.nextInt();
            int cycle = scanner.nextInt();
            
            // Áp dụng công thức toán học tối ưu thay vì vòng lặp
            long result = (long) limit * cycle / 2;
            System.out.println(result);
        }
        scanner.close();
    }
}

2. Chiến Lược Trò Chơi Bài Tối Ưu

Trong trò chơi này, hai người chơi luân phiên chọn bài từ một bộ gồm n lá, mỗi lá có một giá trị số nguyên nhất định. Người chơi trước muốn tối đa hóa điểm số của mình, trong khi người chơi sau cũng chơi tối ưu để đạt lợi ích cao nhất. Điểm số cuối cùng được tính bằng tổng giá trị các lá bài mỗi người cầm.

Chiến lược tham lam (Greedy) là phù hợp nhất: sắp xếp các lá bài theo thứ tự giảm dần. Người đi trước sẽ luôn chọn lá lớn nhất còn lại, người đi sau chọn lá lớn nhất tiếp theo. Hiệu số điểm sẽ là tổng đan dấu của dãy đã sắp xếp.

import java.util.Arrays;
import java.util.Scanner;

public class CardGameStrategy {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int cardCount = input.nextInt();
        int[] values = new int[cardCount];
        
        for (int i = 0; i < cardCount; i++) {
            values[i] = input.nextInt();
        }
        
        Arrays.sort(values);
        
        long scoreDifference = 0;
        // Duyệt từ lớn nhất xuống nhỏ nhất, cộng trừ luân phiên
        for (int i = cardCount - 1; i >= 0; i--) {
            if ((cardCount - 1 - i) % 2 == 0) {
                scoreDifference += values[i];
            } else {
                scoreDifference -= values[i];
            }
        }
        
        System.out.println(scoreDifference);
        input.close();
    }
}

3. Phân Phối Chocolate Với Ràng Buộc Tiêu Thụ

Bài toán đặt ra là tìm số lượng chocolate lớn nhất có thể ăn vào ngày đầu tiên sao cho đủ ăn trong N ngày với tổng M块巧克力. Điều kiện là số lượng ăn mỗi ngày không được ít hơn một nửa số lượng của ngày hôm trước (làm tròn lên).

Để giải quyết hiệu quả, ta sử dụng tìm kiếm nhị phân (Binary Search) trên đáp án. Nếu số lượng bắt đầu là X, ta có thể tính tổng số chocolate cần thiết cho N ngày. Hàm tính tổng này đơn điệu tăng theo X, do đó có thể áp dụng binary search để tìm giá trị X lớn nhất thỏa mãn tổng cần thiết nhỏ hơn hoặc bằng M.

import java.util.Scanner;

public class ChocolateDistribution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int days = scanner.nextInt();
        int totalChocolates = scanner.nextInt();
        
        int low = 1, high = totalChocolates;
        int maxFirstDay = 1;
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (checkFeasibility(mid, days, totalChocolates)) {
                maxFirstDay = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        
        System.out.println(maxFirstDay);
    }
    
    // Kiểm tra xem bắt đầu với amount có đủ ăn trong days ngày không
    private static boolean checkFeasibility(int amount, int days, int limit) {
        long totalNeeded = 0;
        int current = amount;
        for (int i = 0; i < days; i++) {
            totalNeeded += current;
            if (totalNeeded > limit) return false;
            // Ngày sau ăn ít nhất là ceil(current / 2)
            current = (current + 1) / 2;
            if (current == 0) current = 1; // Đảm bảo luôn có chocolate ăn
        }
        return totalNeeded <= limit;
    }
}

4. Đếm Tổ Hợp Danh Sách Nhạc Bằng Quy Hoạch Động

Cần tạo một danh sách nhạc có tổng độ dài chính xác K từ hai loại bài hát: X bài loại A (độ dài a) và Y bài loại B (độ dài b). Mỗi bài chỉ được chọn tối đa một lần và thứ tự không quan trọng. Yêu cầu tính số cách chọn modulo 10^9 + 7.

Đây là biến thể của bài toán cái túi (Knapsack Problem). Ta sử dụng mảng DP để lưu số cách đạt được độ dài j. Khi xét từng bài hát, ta cập nhật ngược mảng DP để đảm bảo mỗi bài chỉ được tính một lần cho mỗi trạng thái độ dài.

import java.util.Scanner;

public class PlaylistComposer {
    private static final int MODULO = 1000000007;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int targetLength = scanner.nextInt();
        int lenA = scanner.nextInt();
        int countA = scanner.nextInt();
        int lenB = scanner.nextInt();
        int countB = scanner.nextInt();
        
        int[] ways = new int[targetLength + 1];
        ways[0] = 1;
        
        // Xử lý loại bài hát A
        for (int i = 0; i < countA; i++) {
            for (int j = targetLength; j >= lenA; j--) {
                ways[j] = (ways[j] + ways[j - lenA]) % MODULO;
            }
        }
        
        // Xử lý loại bài hát B
        for (int i = 0; i < countB; i++) {
            for (int j = targetLength; j >= lenB; j--) {
                ways[j] = (ways[j] + ways[j - lenB]) % MODULO;
            }
        }
        
        System.out.println(ways[targetLength]);
        scanner.close();
    }
}