trang chủ / đề bài / icpcwf23_b

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ó n nhóm, mỗi nhóm 2 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á n 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ừ 1 đến n, hai người của nhóm thứ i là (i,1) và (i,2) với mọi i từ 1 đến 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 (i,1) và (i,2) 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 i và j với i≠j thỉnh thoảng phải làm việc cùng nhau. Với số tuần w cho trước và hai người cố định (i,a) và (j,b), gọi w1<w2<…<wk 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 {w1,w2−w1,w3−w2,…,wk−wk−1,w+1−wk}, 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 i, j, a và b.

Bạn được giao nhiệm vụ tìm một lịch làm việc theo tuần cho w 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 n (2≤n≤104) và w (1≤w≤52): 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 n 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 w dòng mô tả một lịch đạt được độ cách biệt đó. Dòng thứ j của lịch là một xâu độ dài n chỉ gồm các ký tự 1 và 2, ký tự thứ i cho biết thành viên nào của nhóm i đến văn phòng vào tuần j. Nếu có nhiều lịch thỏa mãn, in ra lịch bất kỳ.

Ràng buộc

  • 2≤n≤104.
  • 1≤w≤52.

Ví dụ

Input Output Giải thích
2 6 4
11
12
21
22
11
12
Bốn cặp người (1,a), (2,b) gặp nhau lần lượt ở tuần 1 và 5 (cặp a=b=1), tuần 2 và 6 (cặp a=1,b=2), tuần 3 (cặp a=2,b=1) và tuần 4 (cặp a=b=2). Chẳng hạn cặp a=2,b=1 có độ cách biệt max(3,7−3)=4. Với 2 nhóm không thể đạt độ cách biệt 3.
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

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0