1. Google Code Jam 2020 - Pascal Walk
Pascal Walk
Đề bài
Tam giác Pascal gồm vô hạn hàng, mỗi hàng chứa số lượng số nguyên tăng dần, được sắp xếp thành hình tam giác.
Ta ký hiệu \((r, k)\) là vị trí thứ \(k\) tính từ trái sang trong hàng thứ \(r\), trong đó cả \(r\) và \(k\) đều được đánh số bắt đầu từ 1. Khi đó, tam giác Pascal được xác định bởi các quy tắc sau:
- Hàng thứ \(r\) chứa \(r\) vị trí \((r, 1), (r, 2), \ldots, (r, r)\).
- Các số tại vị trí \((r, 1)\) và \((r, r)\) đều bằng 1 với mọi \(r\).
- Số tại vị trí \((r, k)\) bằng tổng của các số tại \((r - 1, k - 1)\) và \((r - 1, k)\) với mọi \(2 \le k \le r - 1\).
Năm hàng đầu tiên của tam giác Pascal trông như sau:
Trong bài này, một đường đi Pascal là một dãy gồm \(S\) vị trí \((r_1,k_1),(r_2,k_2),\ldots,(r_S,k_S)\) trong tam giác Pascal, thỏa mãn các điều kiện sau:
- \(r_1=1\) và \(k_1=1\).
- Mỗi vị trí tiếp theo phải nằm trong tam giác và kề vị trí trước theo một trong sáu hướng. Cụ thể, với mọi \(i \ge 1\), \((r_{i+1},k_{i+1})\) phải là một trong các vị trí sau nếu vị trí đó nằm trong tam giác: \((r_i-1,k_i-1)\), \((r_i-1,k_i)\), \((r_i,k_i-1)\), \((r_i,k_i+1)\), \((r_i+1,k_i)\) hoặc \((r_i+1,k_i+1)\).
- Không vị trí nào được lặp lại trong dãy. Tức là với mọi \(i \ne j\), phải có \(r_i \ne r_j\) hoặc \(k_i \ne k_j\), hoặc cả hai.
Hãy tìm một đường đi Pascal bất kỳ gồm \(S \le 500\) vị trí sao cho tổng các số tại tất cả vị trí mà đường đi ghé qua bằng đúng \(N\). Đề bài bảo đảm rằng với mọi \(N\), luôn tồn tại ít nhất một đường đi như vậy.
Dữ liệu vào
Dòng đầu tiên chứa số lượng bộ test \(T\). Sau đó là \(T\) bộ test. Mỗi bộ test gồm một dòng duy nhất chứa một số nguyên \(N\).
Dữ liệu ra
Với mỗi bộ test, trước tiên in một dòng có dạng Case #x:, trong đó x là số thứ tự bộ test, bắt đầu từ 1. Sau đó in đường đi Pascal đề xuất có độ dài \(S \le 500\) bằng \(S\) dòng tiếp theo. Dòng thứ \(i\) phải có dạng r_i k_i, trong đó \((r_i,k_i)\) là vị trí thứ \(i\) trên đường đi. Chẳng hạn, dòng đầu tiên phải là 1 1, vì vị trí đầu tiên của mọi đường đi hợp lệ đều là \((1,1)\).
Tổng các số tại \(S\) vị trí của đường đi đề xuất phải bằng đúng \(N\).
Ràng buộc
- \(1 \le \mathbf{T} \le 100\).
Phân nhóm
Test Set 1 (phản hồi kết quả hiển thị)
- \(1 \le \mathbf{N} \le 501\).
Test Set 2 (phản hồi kết quả hiển thị)
- \(1 \le \mathbf{N} \le 1000\).
Test Set 3 (phản hồi kết quả ẩn)
- \(1 \le \mathbf{N} \le 10^9\).
Đ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 | 3/35 | 8,57% |
| Test Set 2 | 11/35 | 31,43% |
| Test Set 3 | 21/35 | 60% |
Ví dụ
Ví dụ 1
Input
3
1
4
19Output
Case #1:
1 1
Case #2:
1 1
2 1
2 2
3 3
Case #3:
1 1
2 2
3 2
4 3
5 3
5 2
4 1
3 1Giải thích
Trong trường hợp mẫu số 1, ta chỉ cần vị trí bắt đầu.
Trong trường hợp mẫu số 2, mặc dù tồn tại một đường đi ngắn hơn, đường đi không cần có độ dài nhỏ nhất, miễn là nó dùng không quá 500 vị trí.
Hình sau minh họa lời giải của chúng tôi cho trường hợp mẫu số 3:
Nguồn
Google Code Jam 2020, Vòng 1A, bài Pascal Walk.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.