Bạn sở hữu một cửa hàng sữa lắc. Có \(N\) hương vị khác nhau mà bạn có thể chuẩn bị, và mỗi hương vị có thể được chế biến theo kiểu "malted" (có mạch nha) hoặc "unmalted" (không có mạch nha). Vì vậy, bạn có thể tạo ra \(2N\) loại sữa lắc khác nhau.

Mỗi khách hàng của bạn có một tập hợp các loại sữa lắc mà họ thích, và họ sẽ hài lòng nếu bạn chuẩn bị ít nhất một trong những loại đó. Trong số các loại mà một khách hàng thích, có tối đa một loại là hương vị "malted".

Bạn muốn tạo ra \(N\) mẻ sữa lắc sao cho:

• Có đúng một mẻ cho mỗi hương vị sữa lắc, và nó là malted hoặc unmalted.
• Đối với mỗi khách hàng, bạn tạo ra ít nhất một loại sữa lắc mà họ thích.
• Số lượng mẻ sữa lắc malted là ít nhất có thể.

Hãy tìm xem có thể làm hài lòng tất cả khách hàng của bạn với những ràng buộc này hay không, và nếu có, bạn nên làm những loại sữa lắc nào.

Nếu có thể làm hài lòng tất cả khách hàng, sẽ chỉ có duy nhất một đáp án tối thiểu hóa số lượng mẻ malted.

Dữ liệu vào

• Một dòng chứa số nguyên \(C\), số lượng bộ dữ liệu trong tệp đầu vào.
• Đối với mỗi bộ dữ liệu:
  • Một dòng chứa số nguyên \(N\), số lượng hương vị sữa lắc.
  • Một dòng chứa số nguyên \(M\), số lượng khách hàng.
  • \(M\) dòng, mỗi dòng cho một khách hàng, chứa:
    • Một số nguyên \(T \ge 1\), số lượng loại sữa lắc khách hàng thích, theo sau bởi
    • \(T\) cặp số nguyên "\(X\) \(Y\)", mỗi cặp cho một loại khách hàng thích, trong đó \(X\) là hương vị sữa lắc từ \(1\) đến \(N\), kể cả hai đầu, và \(Y\) là 0 để chỉ unmalted, hoặc 1 để chỉ malted.
    • Lưu ý:
      • Không có cặp nào xuất hiện nhiều hơn một lần cho cùng một khách hàng.
      • Mỗi khách hàng sẽ thích ít nhất một hương vị (\(T \ge 1\)).
      • Mỗi khách hàng sẽ thích tối đa một hương vị malted (tối đa một cặp cho mỗi khách hàng có \(Y = 1\)).

Tất cả các số này được phân tách bằng các khoảng trắng đơn.

Dữ liệu ra

\(C\) dòng, mỗi dòng cho một bộ dữ liệu theo thứ tự xuất hiện trong tệp đầu vào, mỗi dòng chứa chuỗi "Case #\(X\): " trong đó \(X\) là số thứ tự của bộ dữ liệu, bắt đầu từ 1, tiếp theo là:

• Chuỗi "IMPOSSIBLE", nếu không thể thỏa mãn sở thích của các khách hàng; HOẶC
• \(N\) số nguyên cách nhau bởi khoảng trắng, mỗi số cho một hương vị từ \(1\) đến \(N\), là 0 nếu hương vị tương ứng nên được chuẩn bị unmalted, và 1 nếu là malted.

Ràng buộc

Phân nhóm

• Small dataset (Test set 1):
  • \(C = 100\)
  • \(1 \le N \le 10\)
  • \(1 \le M \le 100\)
• Large dataset (Test set 2):
  • \(C = 5\)
  • \(1 \le N \le 2000\)
  • \(1 \le M \le 2000\)
  • Tổng của tất cả các giá trị \(T\) cho các khách hàng trong một bộ dữ liệu sẽ không vượt quá 3000.

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
5
3
1 1 1
2 1 0 2 0
1 5 0
1
2
1 1 0
1 1 1

Case #1: 1 0 0 0 0
Case #2: IMPOSSIBLE

Nguồn

Google Code Jam 2008, Vòng 1A, bài Milkshakes.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.

Đề bài

Cho hai vectơ \(v_1 = (x_1, x_2, ..., x_n)\) và \(v_2 = (y_1, y_2, ..., y_n)\). Tích vô hướng của hai vectơ này là một số duy nhất, được tính bằng \(x_1y_1 + x_2y_2 + ... + x_ny_n\).

Giả sử bạn được phép hoán vị các tọa độ của mỗi vectơ theo ý muốn. Hãy chọn hai hoán vị sao cho tích vô hướng của hai vectơ mới là nhỏ nhất có thể và xuất ra giá trị tích vô hướng tối thiểu đó.

Dữ liệu vào

Dòng đầu tiên của tệp dữ liệu vào chứa số nguyên \(T\) - số lượng bộ dữ liệu (test case). Với mỗi bộ dữ liệu:

• Dòng đầu tiên chứa số nguyên \(n\).
• Hai dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên, lần lượt là tọa độ của \(v_1\) và \(v_2\).

Dữ liệu ra

Với mỗi bộ dữ liệu, xuất ra một dòng:

Case #X: Y

Ràng buộc

Phân nhóm

• Tập kiểm thử 1 (Small dataset - Công khai):
• \(T = 1000\)
• \(1 \le n \le 8\)
• \(-1000 \le x_i, y_i \le 1000\)
• Tập kiểm thử 2 (Large dataset - Ẩn):
• \(T = 10\)
• \(100 \le n \le 800\)
• \(-100000 \le x_i, y_i \le 100000\)

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
3
1 3 -5
-2 4 1
5
1 2 3 4 5
1 0 1 0 1

Case #1: -25
Case #2: 6

Nguồn

Google Code Jam 2008, Vòng 1A, bài Minimum Scalar Product.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.

Numbers

Đề bài

Trong bài toán này, bạn phải tìm ba chữ số cuối cùng trước dấu phẩy thập phân của số \((3 + \sqrt{5})^n\).

Ví dụ, khi \(n = 5\), \((3 + \sqrt{5})^5 = 3935.73982...\) Câu trả lời là \(935\).

Với \(n = 2\), \((3 + \sqrt{5})^2 = 27.4164079...\) Câu trả lời là \(027\).

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test theo sau, mỗi bộ trên một dòng riêng biệt. Mỗi bộ test chứa một số nguyên dương \(n\).

Dữ liệu ra

Với mỗi bộ test, bạn nên xuất ra:

Case #X: Y

trong đó \(X\) là số thứ tự của bộ test và \(Y\) là ba chữ số nguyên cuối cùng của số \((3 + \sqrt{5})^n\). Trong trường hợp số đó có ít hơn ba chữ số nguyên, hãy thêm các số không ở đầu để đầu ra của bạn chứa đúng ba chữ số.

Ràng buộc

• \(1 \le T \le 100\)

Phân nhóm

• Tập kiểm tra 1 (Visible): \(2 \le n \le 30\)
• Tập kiểm tra 2 (Hidden): \(2 \le n \le 2000000000\)

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
5
2

Case #1: 935
Case #2: 027

Nguồn

Google Code Jam 2008, Vòng 1A, bài Numbers.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.