Xây dựng dần tập mệnh giá

Ta sẽ xây dựng tăng dần một tập mệnh giá \(S\) giải được bài toán với số mệnh giá bổ sung nhỏ nhất, bằng cách chỉ thêm mệnh giá theo thứ tự từ nhỏ đến lớn.

Cùng lúc, duy trì số nguyên \(N\) là giá trị lớn nhất sao cho tạo được mọi giá trị từ 0 đến \(N\). Thực tế, sau mọi lựa chọn, \(S\) tạo được chính xác tập giá trị từ 0 đến \(N\) và không có giá trị nào khác.

Khi thêm mệnh giá \(X\) vào \(S\), ta có thể lấy mỗi giá trị cũ rồi cộng từ 0 đến \(C\) đồng mệnh giá \(X\). Nếu \(X\le N+1\), các khoảng này nối liền và tạo ra toàn bộ giá trị từ 0 đến \(N+XC\). Do đó cập nhật \(N\leftarrow N+XC\).

Khởi tạo \(S\) rỗng và \(N=0\).

Lựa chọn tham lam

Trong khi \(N<V\), thực hiện:

• Giá trị nhỏ nhất chưa tạo được là \(N+1\).
• Nếu còn mệnh giá có sẵn chưa dùng, gọi mệnh giá nhỏ nhất là \(X\). Nếu \(X\le N+1\), đưa nó vào \(S\) và cập nhật \(N\leftarrow N+XC\).
• Nếu không, ta chưa có cách tạo \(N+1\), nên buộc phải thêm vào \(S\) một mệnh giá mới \(X\) trong đoạn \([1,N+1]\). Chọn \(X=N+1\). Không lựa chọn nào khác tốt hơn: với \(X=N+1\), tập giá trị mới tạo được chứa tập giá trị thu được từ mọi lựa chọn \(X\) nhỏ hơn.

Khi \(S\) đã tạo được mọi giá trị tới \(V\), xuất số mệnh giá mới đã thêm.

Độ phức tạp

Nhánh dùng mệnh giá có sẵn chỉ xảy ra tối đa \(D\) lần. Ở nhánh thêm mệnh giá mới, \(N\) tăng thành \((C+1)N+C\). Vì dừng khi \(N\) đạt \(V\), nhánh này xảy ra \(O(\log V)\) lần. Tổng thời gian là \(O(D+\log V)\).

Mã tham khảo Java

import java.util.*;

public class C {
  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int T = scan.nextInt();
    for (int TC = 1; TC <= T; TC++) {
      int C = scan.nextInt();
      int D = scan.nextInt();
      int V = scan.nextInt();
      Queue<Integer> Q = new ArrayDeque<>();
      for (int i = 0; i < D; i++) {
        Q.add(scan.nextInt());
      }

      long N = 0;
      int add = 0;
      while (N < V) {
        // X = The smallest value we cannot produce.
        long X = N + 1;
        if (!Q.isEmpty() && Q.peek() <= X) {
          // Use pre-existing denomination we haven't used.
          X = Q.poll();
        } else {
          // No way to produce N+1, add a new denomination.
          add++;
        }
        N += X * C;
      }
      System.out.printf("Case #%d: %d\n", TC, add);
    }
  }
}

Lời giải C của Vitaliy trên bảng điểm là một ví dụ khác của cách tiếp cận này.

Dựa trên phân tích chính thức của Google Code Jam.