3. Google Code Jam 2016 - Slides!
Gooli là một công ty khổng lồ sở hữu \(B\) tòa nhà trong một vùng đồi núi. Các tòa nhà được đánh số từ 1 đến \(B\).
Tổng giám đốc muốn xây một hệ thống cầu trượt giữa các tòa nhà để đi từ văn phòng ở tòa nhà 1 tới quán cà phê yêu thích ở tòa nhà \(B\). Cầu trượt dĩ nhiên chỉ đi một chiều, nhưng các tòa nhà cao và có thang máy, nên một cầu trượt có thể bắt đầu ở bất kỳ tòa nhà nào, kết thúc ở bất kỳ tòa nhà nào khác và đi theo một trong hai hướng. Cụ thể, với hai tòa nhà \(x,y\), có thể xây không quá một cầu từ \(x\) tới \(y\) và không quá một cầu từ \(y\) tới \(x\). Ngoại lệ là không cầu trượt nào được xuất phát từ tòa nhà \(B\), vì khi đã tới đó, tổng giám đốc không cần trượt tiếp.
Để kỷ niệm Gooli vừa tròn đúng \(M\) mili-giây tuổi, thiết kế phải bảo đảm tổng giám đốc có đúng \(M\) cách khác nhau để đi từ tòa nhà 1 tới tòa nhà \(B\) bằng các cầu trượt mới. Một cách là một dãy tòa nhà bắt đầu bằng 1, kết thúc bằng \(B\), và giữa mọi cặp tòa nhà liên tiếp \(x,y\) đều có cầu trượt từ \(x\) tới \(y\). Lưu ý rằng tổng giám đốc không yêu cầu mọi tòa nhà phải đi tới được mọi tòa nhà khác.
Bạn có thể đưa ra một hệ thống gồm ít nhất một cầu trượt thỏa yêu cầu, hay xác định rằng điều đó là không thể?
Dữ liệu vào
Dòng đầu tiên chứa số bộ test \(T\). Mỗi bộ test là một dòng chứa hai số nguyên \(B\) và \(M\) như mô tả ở trên.
Dữ liệu ra
Với mỗi bộ test, in một dòng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y là POSSIBLE hoặc IMPOSSIBLE tùy theo yêu cầu có thể được đáp ứng hay không. Nếu có thể, in thêm \(B\) dòng, mỗi dòng gồm \(B\) ký tự, tạo thành ma trận mô tả một cách xây cầu hợp lệ. Ký tự thứ \(j\) của dòng thứ \(i\) (đều đánh số từ 1) là 1 nếu cần xây cầu từ tòa nhà \(i\) tới tòa nhà \(j\), và là 0 nếu không. Ký tự thứ \(i\) trên dòng thứ \(i\) luôn phải là 0, và mọi ký tự ở dòng cuối đều phải là 0.
Nếu có nhiều lời giải, bạn có thể in bất kỳ lời giải nào.
Ràng buộc
- \(1 \le T \le 100\).
Phân nhóm
- Test Set 1 (Hiển thị): \(2 \le B \le 6\), \(1 \le M \le 20\).
- Test Set 2 (Ẩn): \(2 \le B \le 50\), \(1 \le M \le 10^{18}\).
Đ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 | 13/34 | 38,24% |
| Test Set 2 | 21/34 | 61,76% |
Ví dụ
Ví dụ 1
Input
3
5 4
2 1
4 20Output
Case #1: POSSIBLE
01001
00110
00001
00101
00000
Case #2: POSSIBLE
01
00
Case #3: IMPOSSIBLEGiải thích
Đầu ra mẫu cho thấy một cách đáp ứng yêu cầu ở mỗi bộ test; có thể tồn tại các đáp án hợp lệ khác.
Hình sau minh họa đáp án mẫu cho bộ test số 1:
Bốn cách đi từ tòa nhà 1 tới tòa nhà 5 là:
- 1 tới 5;
- 1 tới 2 tới 3 tới 5;
- 1 tới 2 tới 4 tới 5;
- 1 tới 2 tới 4 tới 3 tới 5.
Trong bộ test số 3, xây các cầu \(1\to2\), \(2\to3\), \(3\to1\) và \(1\to4\) sẽ tạo ra vô hạn cách tới tòa nhà 4: đi thẳng tới 4, đi quanh chu trình một lần rồi tới 4, đi quanh hai lần rồi tới 4, v.v. Nhưng tổng giám đốc yêu cầu đúng 20 cách.
Nguồn
Google Code Jam 2016, Vòng 1C, bài Slides!.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.