Google Code Jam 2020 - Vestigium
Xem PDFVestigium
Vestigium có nghĩa là “vết” (trace) trong tiếng Latinh. Trong bài toán này, chúng ta làm việc với các hình vuông Latin và vết của ma trận.
Vết của một ma trận vuông là tổng các giá trị trên đường chéo chính (đường chéo chạy từ góc trên bên trái đến góc dưới bên phải).
Một ma trận vuông kích thước \(N \times N\) là một hình vuông Latin nếu mỗi ô chứa một trong \(N\) giá trị khác nhau và không có giá trị nào xuất hiện lặp lại trong cùng một hàng hoặc cùng một cột. Trong bài toán này, ta chỉ xét các “hình vuông Latin tự nhiên”, trong đó \(N\) giá trị là các số nguyên từ \(1\) đến \(N\).
Cho một ma trận chỉ chứa các số nguyên từ \(1\) đến \(N\), ta muốn tính vết của nó và kiểm tra xem nó có phải là một hình vuông Latin tự nhiên hay không. Để cung cấp thêm thông tin, thay vì chỉ cho biết ma trận có phải là một hình vuông Latin tự nhiên hay không, hãy tính số hàng và số cột có chứa các giá trị lặp lại.
Dữ liệu vào
Dòng đầu tiên của dữ liệu vào chứa số lượng bộ test \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa một số nguyên duy nhất \(N\): kích thước của ma trận cần xét. Sau đó là \(N\) dòng; dòng thứ \(i\) trong số đó chứa \(N\) số nguyên \(M_{i,1}, M_{i,2}, \ldots, M_{i,N}\). \(M_{i,j}\) là số nguyên nằm ở hàng thứ \(i\) và cột thứ \(j\) của ma trận.
Dữ liệu ra
Với mỗi bộ test, in ra một dòng có dạng Case #x: k r c, trong đó x là số thứ tự của bộ test (bắt đầu từ \(1\)), k là vết của ma trận, r là số hàng của ma trận có chứa phần tử lặp lại và c là số cột của ma trận có chứa phần tử lặp lại.
Ràng buộc
Phân nhóm
Test Set 1 (Phán quyết hiển thị)
- \(1 \le T \le 100\).
- \(2 \le N \le 100\).
- \(1 \le M_{i,j} \le N\) với mọi \(i, j\).
Đ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.
| Phân nhóm | Điểm Google Code Jam | Tỷ lệ điểm của bài |
|---|---|---|
| Test Set 1 | 7/7 | 100% |
Ví dụ
Ví dụ 1
Input
3
4
1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1
4
2 2 2 2
2 3 2 3
2 2 2 3
2 2 2 2
3
2 1 3
1 3 2
1 2 3Output
Case #1: 4 0 0
Case #2: 9 4 4
Case #3: 8 0 2Giải thích
Giải thích ví dụ
Trong trường hợp mẫu số 1, dữ liệu vào là một hình vuông Latin tự nhiên, nghĩa là không có hàng hoặc cột nào chứa phần tử lặp lại. Cả bốn giá trị trên đường chéo chính đều bằng \(1\), vì vậy vết (tổng của chúng) bằng \(4\).
Trong trường hợp mẫu số 2, tất cả các hàng và các cột đều chứa phần tử lặp lại. Lưu ý rằng mỗi hàng hoặc cột có phần tử lặp lại chỉ được tính một lần, bất kể có bao nhiêu phần tử bị lặp hoặc chúng lặp lại bao nhiêu lần trong hàng hay cột đó. Ngoài ra, hãy lưu ý rằng một số số nguyên trong đoạn từ \(1\) đến \(N\) có thể không xuất hiện trong dữ liệu vào.
Trong trường hợp mẫu số 3, cột ngoài cùng bên trái và cột ngoài cùng bên phải có chứa phần tử lặp lại.
Nguồn
Google Code Jam 2020, Vòng loại, bài Vestigium.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.
Kỳ thi:
- Google Code Jam 2020 - Qualification Round (4 Tháng tư, 2020)
Bình luận