Lịch làm việc
Đề bài
Mô tả
Viện Kết hợp Sản phẩm Sáng tạo (ICPC) luôn tìm những cách mới lạ để kết hợp các sản phẩm hay công nghệ tưởng như chẳng liên quan gì đến nhau, mở ra thị trường mới và tạo thêm việc làm. (Ví dụ, thành công gần đây nhất của họ là "hairbachi", một chiếc máy sấy tóc có gắn mặt bếp nướng hibachi để chuẩn bị bữa ăn nóng khi đang di chuyển.) Công ty có nhóm, mỗi nhóm người, mỗi nhóm nghiên cứu một sản phẩm riêng, sau đó thành viên của các nhóm khác nhau gặp nhau để tìm cách kết hợp các sản phẩm.
Trong đại dịch, ban lãnh đạo ICPC sắp xếp lịch của mọi người sao cho không bao giờ có quá người cùng ở văn phòng, và mọi việc diễn ra suôn sẻ đến mức họ vẫn giữ cách làm này khi cuộc sống trở lại bình thường. Cách làm như sau. Đánh số các nhóm bằng các số nguyên từ đến , hai người của nhóm thứ là và với mọi từ đến .
Mỗi tuần, mỗi nhóm có đúng một người được đến văn phòng, người còn lại phải ở nhà. Hai người và hiểu nhau rất rõ và làm việc hiệu quả dù không gặp mặt, nên thành viên cùng một nhóm không cần gặp nhau ở văn phòng. Tuy nhiên, sự cách biệt giữa thành viên của các nhóm khác nhau vẫn là một vấn đề.
Mỗi cặp nhóm và với thỉnh thoảng phải làm việc cùng nhau. Với số tuần cho trước và hai người cố định và , gọi là các tuần mà hai người này cùng có mặt ở văn phòng. Độ cách biệt của hai người đó là giá trị lớn nhất trong , hoặc vô cùng nếu hai người đó không bao giờ gặp nhau. Độ cách biệt của cả công ty là độ cách biệt lớn nhất trên mọi cách chọn , , và .
Bạn được giao nhiệm vụ tìm một lịch làm việc theo tuần cho tuần sao cho độ cách biệt của cả công ty nhỏ nhất.
Dữ liệu vào
Một dòng duy nhất chứa hai số nguyên () và (): số nhóm và số tuần cần lập lịch.
Dữ liệu ra
In ra một dòng chứa hoặc một số nguyên là độ cách biệt nhỏ nhất có thể đạt được với nhóm, hoặc từ infinity nếu không có lịch nào bảo đảm mọi cặp người thuộc hai nhóm khác nhau đều gặp được nhau.
Nếu độ cách biệt hữu hạn, in tiếp dòng mô tả một lịch đạt được độ cách biệt đó. Dòng thứ của lịch là một xâu độ dài chỉ gồm các ký tự 1 và 2, ký tự thứ cho biết thành viên nào của nhóm đến văn phòng vào tuần . Nếu có nhiều lịch thỏa mãn, in ra lịch bất kỳ.
Ràng buộc
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 6 | 4 11 12 21 22 11 12 |
Bốn cặp người , gặp nhau lần lượt ở tuần và (cặp ), tuần và (cặp ), tuần (cặp ) và tuần (cặp ). Chẳng hạn cặp có độ cách biệt . Với nhóm không thể đạt độ cách biệt . |
| 2 1 | infinity | Chỉ có một tuần nên trong bốn cặp người chỉ có một cặp gặp được nhau. |
Bình luận