Một số kẻ chơi khăm đã xem quá nhiều kênh Discovery Channel và giờ họ muốn tạo ra một "tam giác mùa màng" trong đêm. Họ muốn xây dựng nó bên trong một cánh đồng lớn trông giống như một lưới các ô vuông đều nhau khi nhìn từ trên cao. Có một số cây được trồng trên cánh đồng. Mỗi cây nằm ở giao điểm của hai đường lưới (một điểm lưới).

Những kẻ chơi khăm muốn các đỉnh của tam giác mùa màng phải nằm tại các vị trí có cây này. Ngoài ra, để tam giác thêm phần thú vị, họ muốn trọng tâm của tam giác đó cũng phải nằm tại một điểm lưới. Chúng tôi nhắc lại rằng nếu một tam giác có các đỉnh là \((x_1, y_1)\), \((x_2, y_2)\) và \((x_3, y_3)\), thì trọng tâm của tam giác này sẽ có tọa độ là \(((x_1 + x_2 + x_3) / 3, (y_1 + y_2 + y_3) / 3)\).

Bạn được cho một tập hợp các điểm với tọa độ nguyên là vị trí của tất cả các cây trên lưới. Bạn được yêu cầu tính xem có bao nhiêu tam giác có thể tạo thành từ 3 đỉnh phân biệt trong tập hợp các điểm này sao cho trọng tâm của chúng cũng là một điểm lưới (tức là trọng tâm có tọa độ nguyên).

Nếu một tam giác có diện tích bằng 0, chúng ta vẫn coi đó là một tam giác hợp lệ.

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, \(N\). \(N\) bộ test theo sau. Mỗi bộ test bao gồm một dòng chứa các số nguyên \(n, A, B, C, D, x_0, y_0\) và \(M\) cách nhau bởi đúng một dấu cách. \(n\) là số lượng cây trong tập dữ liệu đầu vào.

Sử dụng các số \(n, A, B, C, D, x_0, y_0\) và \(M\), đoạn mã giả sau đây sẽ in ra tọa độ của các cây trong tập dữ liệu. \(mod\) biểu thị phép toán lấy số dư.

Các tham số sẽ được chọn sao cho tập hợp các cây đầu vào không có điểm nào trùng nhau.

X = x0, Y = y0
print X, Y
for i = 1 to n-1
  X = (A * X + B) mod M
  Y = (C * Y + D) mod M
  print X, Y

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #\(X\): " trong đó \(X\) là số thứ tự bộ test (bắt đầu từ 1). Tiếp theo là một số nguyên cho biết số lượng tam giác có thể được đặt tại 3 cây phân biệt và có trọng tâm là một điểm lưới.

Ràng buộc

• \(1 \le N \le 10\).
• \(0 \le A, B, C, D, x_0, y_0 \le 10^9\).
• \(1 \le M \le 10^9\).

Phân nhóm

• Tập kiểm tra 1 (Small - Visible): \(3 \le n \le 100\).
• Tập kiểm tra 2 (Large - Hidden): \(3 \le n \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
4 10 7 1 2 0 1 20
6 2 0 2 1 1 2 11

Case #1: 1
Case #2: 2

Nguồn

Google Code Jam 2008, Vòng 1B, bài Crop Triangles.

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

Mousetrap là một trò chơi bài đơn giản dành cho một người chơi. Trò chơi được chơi với một bộ bài đã được xáo trộn gồm các lá bài được đánh số từ \(1\) đến \(K\), úp xuống.

Bạn chơi bằng cách lật lá bài trên cùng của bộ bài và sau đó đặt nó xuống dưới cùng của bộ bài, đồng thời đếm xem bạn đã lật được bao nhiêu lá bài. Nếu bạn lật được một lá bài có số khớp với số lần đếm hiện tại, hãy loại bỏ nó khỏi bộ bài và thiết lập lại (reset) số lần đếm. Nếu số lần đếm đạt đến \(K+1\), bạn đã thua. Nếu bộ bài hết bài, bạn thắng.

Giả sử bạn có một bộ bài gồm 5 lá, theo thứ tự 2, 5, 3, 1, 4.
Bạn sẽ lật lá 2 ở lần đếm 1, lá 5 ở lần đếm 2, sau đó là lá 3 ở lần đếm 3. Vì giá trị khớp với số lần đếm, bạn loại bỏ lá 3 khỏi bộ bài và reset số lần đếm. Bây giờ bạn còn 4 lá bài theo thứ tự 1, 4, 2, 5. Tiếp theo bạn lật lá 1 ở lần đếm 1, và cũng loại bỏ nó (bạn đang làm rất tốt!). Tiếp tục theo cách này, bạn sẽ lần lượt loại bỏ lá 2, sau đó là lá 4, và cuối cùng là lá 5 để giành chiến thắng.

Bạn muốn sắp xếp một bộ bài sao cho bạn sẽ thắng trò chơi và loại bỏ các lá bài theo thứ tự tăng dần. Chúng ta sẽ gọi một bộ bài được sắp xếp theo cách này là "hoàn hảo".
Ví dụ, với 4 lá bài, bạn có thể sắp xếp bộ bài là 1, 4, 2, 3, và bạn sẽ thắng bằng cách loại bỏ các lá bài theo thứ tự 1, 2, 3, 4.

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\).
Mỗi bộ test bắt đầu bằng một dòng chứa \(K\), số lượng lá bài trong bộ bài.
Dòng tiếp theo bắt đầu bằng một số nguyên \(n\), theo sau là \(n\) số nguyên (\(d_1, d_2, \dots\)), là các chỉ số trong bộ bài.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #\(x\): " theo sau là \(n\) số nguyên (\(k_1, k_2, \dots\)), trong đó \(k_i\) là giá trị của lá bài tại chỉ số \(d_i\) của một bộ bài hoàn hảo có kích thước \(K\).
Các số trong đầu ra phải được phân tách bằng dấu cách và phải có ít nhất một dấu cách sau dấu hai chấm trong mỗi dòng "Case #\(x\):".

Ràng buộc

Phân nhóm

• Small dataset (Test set 1 - Visible):

• \(T = 100\).

• \(1 \le K \le 5000\).
• \(1 \le n \le 100\).
• \(1 \le d_i \le K\).

• Large dataset (Test set 2 - Hidden):

• \(T = 10\).

• \(1 \le K \le 1000000\).
• \(1 \le n \le 100\).
• \(1 \le d_i \le K\).

Đ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
5 1 2 3 4 5
15
4 3 4 7 10

Case #1: 1 3 2 5 4
Case #2: 2 8 13 4

Nguồn

Google Code Jam 2008, Vòng 1B, bài Mousetrap.

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

Number Sets

Bạn bắt đầu với một dãy các số nguyên liên tiếp. Bạn muốn nhóm chúng vào các tập hợp.

Bạn được cho một khoảng và một số nguyên \(P\). Ban đầu, mỗi số trong khoảng nằm trong tập hợp riêng của nó.

Sau đó, bạn xem xét từng cặp số nguyên trong khoảng. Nếu hai số nguyên đó chia sẻ một ước nguyên tố chung ít nhất là \(P\), thì bạn hợp nhất hai tập hợp chứa hai số nguyên đó lại với nhau.

Hỏi sẽ có bao nhiêu tập hợp khác nhau sau khi kết thúc quá trình này?

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên \(C\), là số lượng bộ dữ liệu.
Mỗi bộ dữ liệu nằm trên một dòng chứa ba số nguyên cách nhau bởi khoảng trắng \(A\), \(B\), và \(P\). \(A\) và \(B\) là số nguyên đầu tiên và cuối cùng trong khoảng, và \(P\) là số được mô tả ở trên.

Dữ liệu ra

Với mỗi bộ dữ liệu, xuất một dòng chứa chuỗi "Case #X: Y" trong đó X là số thứ tự của bộ dữ liệu (bắt đầu từ 1) và Y là số lượng tập hợp.

Ràng buộc

Phân nhóm

• Tập dữ liệu nhỏ (Test set 1 - Visible): \(1 \le C \le 10\); \(1 \le A \le B \le 1000\); \(2 \le P \le B\).
• Tập dữ liệu lớn (Test set 2 - Hidden): \(1 \le C \le 100\); \(1 \le A \le B \le 10^{12}\); \(B \le A + 1000000\); \(2 \le P \le B\).

Đ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
10 20 5
10 20 3

Case #1: 9
Case #2: 7

Nguồn

Google Code Jam 2008, Vòng 1B, bài Number Sets.

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