Google Code Jam 2022 - Squary
Xem PDFPhép cộng và phép bình phương không có tính giao hoán theo nghĩa sau: bình phương của tổng mọi phần tử trong một danh sách số nguyên không nhất thiết bằng tổng bình phương của chính các phần tử ấy. Tuy nhiên, đẳng thức này đúng với một số danh sách. Chẳng hạn, danh sách \([3,-2,6]\) thỏa mãn
\((3+(-2)+6)^2=49=3^2+(-2)^2+6^2\). Ta gọi những danh sách như vậy là squary.
Cho một danh sách các số nguyên tương đối nhỏ, không nhất thiết đã là squary, hãy xác định liệu có thể thêm ít nhất \(1\) và nhiều nhất \(K\) phần tử để danh sách cuối cùng trở thành squary hay không. Mỗi phần tử được thêm phải là một số nguyên trong đoạn \([-10^{18},10^{18}]\); các phần tử thêm vào không cần khác nhau, cũng không cần khác các phần tử ban đầu.
Dữ liệu vào
Dòng đầu chứa số lượng bộ test \(T\). Mỗi bộ test gồm hai dòng. Dòng đầu chứa hai số nguyên \(N\) và \(K\), lần lượt là số phần tử của danh sách ban đầu và số phần tử tối đa được phép thêm. Dòng thứ hai chứa \(N\) số nguyên \(E_1,E_2,\ldots,E_N\), là các phần tử của danh sách ban đầu.
Dữ liệu ra
Với mỗi bộ test, in một dòng theo dạng Case #x: y, trong đó \(x\) là số thứ tự bộ test, bắt đầu từ \(1\).
Nếu có thể thêm từ \(1\) đến \(K\) phần tử, mỗi phần tử thuộc \([-10^{18},10^{18}]\), để bình phương tổng các phần tử bằng tổng bình phương các phần tử, thì \(y\) phải là \(z_1\ z_2\ \ldots\ z_r\), với \(1\le r\le K\), trong đó các \(z_i\) là những phần tử được thêm. Nếu không thể, \(y\) phải là IMPOSSIBLE.
Ràng buộc
- \(1\le T\le100\).
- \(1\le N\le1000\).
- \(-1000\le E_i\le1000\) với mọi \(i\).
Phân nhóm
- Test Set 1 (phán quyết hiển thị): \(K=1\).
- Test Set 2 (phán quyết hiển thị): \(2\le K\le1000\).
Đ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 | 9/31 | 29,03% |
| Test Set 2 | 22/31 | 70,97% |
Ví dụ
Lưu ý: phía dưới còn có các ví dụ bổ sung không được dùng để chạy bài nộp.
Ví dụ 1
Input
4
2 1
-2 6
2 1
-10 10
1 1
0
3 1
2 -2 2Output
Case #1: 3
Case #2: IMPOSSIBLE
Case #3: -1000000000000000000
Case #4: 2Giải thích
Trong test mẫu số 1, sau khi thêm \(3\), ta thu được danh sách ví dụ đã nêu trong đề.
Trong test mẫu số 2, ta buộc phải thêm đúng một phần tử. Gọi phần tử đó là \(x\). Tổng của toàn bộ danh sách bằng \(x\), nên bình phương tổng bằng \(x^2\). Trong khi đó, tổng bình phương các phần tử là \(x^2+10^2+(-10)^2=x^2+200\ne x^2\), vì vậy test này là bất khả thi.
Trong test mẫu số 3, mọi số nguyên thuộc đoạn \([-10^{18},10^{18}]\) đều là đáp án hợp lệ.
Trong test mẫu số 4, dữ liệu vào có thể chứa các phần tử trùng nhau, và ta cũng được phép tạo thêm phần tử trùng bằng những số mình chọn thêm.
Ví dụ bổ sung — Test Set 2
Ví dụ bổ sung sau thỏa các giới hạn của Test Set 2 và sẽ không được chạy với bài nộp.
Input
3
3 10
-2 3 6
6 2
-2 2 1 -2 4 -1
1 12
-5Output
Case #1: 0
Case #2: -1 15
Case #3: 1 1 1 1 1 1 1 1 1 1 1Giải thích
Trong test số 1 của ví dụ bổ sung, danh sách đầu vào chính là danh sách ví dụ trong đề và vốn đã là squary, nhưng ta vẫn phải thêm ít nhất một phần tử. Thêm \(0\) sẽ giữ cho danh sách là squary.
Trong test số 3 của ví dụ bổ sung, đầu ra trình bày một trong nhiều đáp án hợp lệ. Lưu ý rằng ta được phép thêm ít hơn \(K\) phần tử: ở đây \(K=12\) nhưng ta chỉ thêm \(11\) phần tử.
Nguồn
Google Code Jam 2022, Vòng 1C, bài Squary.
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 2022 - Round 1C (30 Tháng tư, 2022)
Bình luận