Bài 4. Lễ hội ánh sáng (2,0 điểm)

Để chuẩn bị cho đêm hội ánh sáng bên bờ sông Hàn, Ban Tổ chức huy động một đoàn gồm n du khách quốc tế tham gia diễu hành trên các xe điện du lịch. Ban Tổ chức cần phân chia n du khách này vào các xe điện khác nhau. Để đảm bảo an toàn và quy định tổ chức, mỗi xe điện phải chở ít nhất một hành khách.

Mỗi xe điện sau khi nhận đủ hành khách sẽ được kích hoạt một hệ thống đèn LED nghệ thuật tự động. Để tạo sự độc đáo và ấn tượng, chu kì tự động đổi màu đèn (tính bằng giây) của mỗi xe được cài đặt bằng đúng số lượng hành khách ngồi trên xe đó. Ví dụ xe chở 3 khách thì cứ đúng 3 giây hệ thống đèn của xe đó lại tự động đổi màu một lần.

Đêm hội diễu hành sẽ đạt đến khoảnh khắc bùng nổ, mãn nhãn nhất khi tất cả các xe điện đồng loạt đổi màu đèn cùng lúc, tạo nên hiệu ứng ánh sáng khổng lồ lan tỏa dọc khắp tuyến phố đi bộ Bạch Đằng. Ban Tổ chức muốn khoảng thời gian từ lúc đoàn xe xuất phát cho đến lần đầu tiên tất cả các xe cùng kích hoạt đổi màu đèn đồng bộ phải là lâu nhất có thể, nhằm kéo dài sự tò mò và tạo sự phấn khích cho khán giả.

Yêu cầu: Hãy giúp Ban Tổ chức tìm phương án phân chia n du khách vào các xe điện sao cho khoảng thời gian chờ đến lúc tất cả các xe cùng đổi màu đèn đồng loạt lần đầu tiên là lớn nhất.

Dữ liệu: Đọc từ tệp văn bản SHOW.INP một dòng duy nhất chứa một số nguyên dương n là tổng số lượng du khách quốc tế tham gia diễu hành.

Kết quả: Ghi ra tệp văn bản SHOW.OUT gồm hai dòng:

- Dòng thứ nhất ghi một số nguyên duy nhất là khoảng thời gian lớn nhất (tính bằng giây) mà khán giả phải chờ để chứng kiến tất cả các xe đổi màu đồng loạt lần đầu tiên.

- Dòng thứ hai ghi số lượng hành khách trên mỗi xe điện được phân chia, các số cách nhau bởi một khoảng trắng và được in theo thứ tự tăng dần. Nếu có nhiều phương án cho cùng một kết quả tối ưu, hãy in ra phương án sử dụng ít xe điện nhất.