{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eCông ty BigData Inc. là một tập đoàn có \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e trung tâm dữ liệu được đánh chỉ mục từ \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e đến \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e được đặt tại khắp nơi trên thế giới. Những trung tâm dữ liệu này cung cấp lưu trữ cho dữ liệu của khách hàng (bạn có thể hiểu rằng dữ liệu của khách hàng thực sự lớn!).\u003c/p\u003e\u003cp\u003eTính năng chính của dịch vụ do BigData Inc. cung cấp là đảm bảo sẵn có ngay cả khi có bất kỳ trục trặc nào xảy ra tại bất kỳ trung tâm dữ liệu nào. Điều này được đảm bảo bằng cách sử dụng \u003cspan class\u003d\"tex-font-style-it\"\u003esao chép hai chiều\u003c/span\u003e. Sao chép hai chiều là một phương pháp lưu trữ dữ liệu trong đó mỗi phần dữ liệu được biểu diễn bằng hai bản sao giống hệt nhau được lưu trữ tại hai trung tâm dữ liệu khác nhau.\u003c/p\u003e\u003cp\u003eĐối với mỗi trong \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e khách hàng của công ty, hãy ký hiệu chỉ số của hai trung tâm dữ liệu khác nhau lưu trữ dữ liệu của khách hàng này là \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e, 1\u003c/sub\u003e\u003c/span\u003e và \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e, 2\u003c/sub\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eĐể giữ cho trung tâm dữ liệu hoạt động và an toàn, phần mềm chạy trên máy tính trung tâm dữ liệu được cập nhật thường xuyên. Chu kỳ phát hành của BigData Inc. là một ngày có nghĩa là phiên bản mới của phần mềm được triển khai lên các máy tính trung tâm dữ liệu mỗi ngày.\u003c/p\u003e\u003cp\u003eViệc cập nhật phần mềm trung tâm dữ liệu là một quá trình lâu dài không đơn giản, đó là lý do tại sao có một khung thời gian đặc biệt kéo dài một giờ được dành cho bảo dưỡng trung tâm dữ liệu. Trong thời gian bảo dưỡng, các máy tính trung tâm dữ liệu đang cài đặt cập nhật phần mềm, và do đó chúng có thể không sẵn có. Xem xét ngày chính xác là \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eh\u003c/i\u003e\u003c/span\u003e giờ. Đối với mỗi trung tâm dữ liệu có một số nguyên \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e0 ≤ \u003ci\u003eu\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003eh\u003c/i\u003e - 1\u003c/span\u003e) xác định chỉ số của một giờ trong ngày, trong đó trung tâm dữ liệu \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003e không sẵn có do bảo dưỡng.\u003c/p\u003e\u003cp\u003eTổng hợp tất cả những điều trên, điều kiện \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e, 1\u003c/sub\u003e\u003c/sub\u003e ≠ \u003ci\u003eu\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e, 2\u003c/sub\u003e\u003c/sub\u003e\u003c/span\u003e nên được thực hiện đối với mỗi khách hàng, nếu không dữ liệu của anh ta có thể không sẵn có trong khi các trung tâm dữ liệu lưu trữ nó đang được bảo dưỡng.\u003c/p\u003e\u003cp\u003eDo thay đổi múi giờ đôi khi xảy ra ở các thành phố khác nhau trên thế giới, thời gian bảo dưỡng tại một số trung tâm dữ liệu có thể thay đổi một giờ đôi khi. Công ty cần chuẩn bị cho tình huống như vậy, đó là lý do tại sao họ quyết định tiến hành một thí nghiệm, chọn một tập hợp không rỗng của trung tâm dữ liệu, và dời thời gian bảo dưỡng cho chúng muộn một giờ (tức là nếu \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e \u003d \u003ci\u003eh\u003c/i\u003e - 1\u003c/span\u003e, thì giờ bảo dưỡng mới sẽ trở thành \u003cspan class\u003d\"tex-span\"\u003e0\u003c/span\u003e, nếu không thì sẽ trở thành \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e + 1\u003c/span\u003e). Tuy nhiên, thí nghiệm như vậy không được phép phá vỡ các cam kết sẵn có, có nghĩa là dữ liệu của bất kỳ khách hàng nào vẫn phải sẵn có trong bất kỳ giờ nào trong một ngày sau khi thời gian bảo dưỡng trung tâm dữ liệu đã thay đổi.\u003c/p\u003e\u003cp\u003eMột thí nghiệm như vậy sẽ cung cấp thông tin hữu ích, nhưng thay đổi thời gian cập nhật là một quy trình tương đối đắt đỏ, đó là lý do tại sao công ty đã yêu cầu bạn tìm ra số trung tâm dữ liệu tối thiểu cần phải được bao gồm trong một thí nghiệm để duy trì các cam kết sẵn có về sự sẵn có của dữ liệu.\u003c/p\u003e"}},{"title":"Nhập","value":{"format":"HTML","content":"\u003cp\u003eDòng đầu tiên của đầu vào chứa ba số nguyên \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e và \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eh\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e2 ≤ \u003ci\u003en\u003c/i\u003e ≤ 100 000\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003em\u003c/i\u003e ≤ 100 000\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e2 ≤ \u003ci\u003eh\u003c/i\u003e ≤ 100 000\u003c/span\u003e), số lượng trung tâm dữ liệu của công ty, số lượng khách hàng và độ dài của ngày được đo bằng giờ.\u003c/p\u003e\u003cp\u003eDòng thứ hai của đầu vào chứa \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e số nguyên \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003eu\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003eu\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e0 ≤ \u003ci\u003eu\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e \u0026lt; \u003ci\u003eh\u003c/i\u003e\u003c/span\u003e), số thứ \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003e trong những số này là chỉ số của một giờ bảo dưỡng cho trung tâm dữ liệu \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eMỗi trong \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e dòng tiếp theo chứa hai số nguyên \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e, 1\u003c/sub\u003e\u003c/span\u003e và \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e, 2\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e, 1\u003c/sub\u003e, \u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e, 2\u003c/sub\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e, 1\u003c/sub\u003e ≠ \u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e, 2\u003c/sub\u003e\u003c/span\u003e), xác định chỉ số của trung tâm dữ liệu chứa dữ liệu của khách hàng \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eĐảm bảo rằng lịch trình bảo dưỡng cung cấp cho phép mỗi khách hàng truy cập ít nhất một bản sao của dữ liệu của anh ta vào bất kỳ thời điểm nào trong ngày.\u003c/p\u003e"}},{"title":"Xuất","value":{"format":"HTML","content":"\u003cp\u003eTrong dòng đầu tiên in ra số trung tâm dữ liệu tối thiểu có thể (\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e) cần phải được bao gồm trong một thí nghiệm để duy trì dữ liệu sẵn có cho bất kỳ khách hàng nào.\u003c/p\u003e\u003cp\u003eTrong dòng thứ hai in ra \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e số nguyên phân biệt \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e), các chỉ số của trung tâm dữ liệu mà thời gian bảo dưỡng sẽ được dời muộn một giờ. Các chỉ số trung tâm dữ liệu có thể được in ra theo bất kỳ thứ tự nào.\u003c/p\u003e\u003cp\u003eNếu có nhiều câu trả lời có thể, được phép in ra bất kỳ câu trả lời nào. Đảm bảo rằng có ít nhất một lựa chọn hợp lệ của trung tâm dữ liệu.\u003c/p\u003e"}},{"title":"Ví dụ 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 3 5\n4 4 0\n1 3\n3 2\n3 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n3 \u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Ví dụ 2","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 5 4\n2 1 0 3\n4 3\n3 2\n1 2\n1 4\n1 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\n1 2 3 4 \u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Ghi chú","value":{"format":"HTML","content":"\u003cp\u003eXem xét ví dụ thử đầu tiên. Câu trả lời được cung cấp là cách duy nhất để tiến hành một thí nghiệm liên quan đến trung tâm dữ liệu duy nhất. Trong kịch bản như vậy, trung tâm dữ liệu thứ ba có bảo dưỡng vào giờ 1, và không có hai trung tâm dữ liệu lưu trữ thông tin của cùng một khách hàng có bảo dưỡng vào cùng một giờ.\u003c/p\u003e\u003cp\u003eNgược lại, ví dụ, nếu chúng ta dời thời gian bảo dưỡng một giờ muộn cho trung tâm dữ liệu đầu tiên, thì dữ liệu của khách hàng 1 và 3 sẽ không sẵn có vào giờ 0.\u003c/p\u003e"}}]}