IOI 2015 - Ngày 1

Màn cuối của lễ khai mạc IOI 2015 đang diễn ra. Trong lễ khai mạc, mỗi đội lẽ ra được nhận một hộp quà lưu niệm từ nước chủ nhà. Tuy nhiên, các tình nguyện viên mải mê theo dõi buổi lễ đến mức quên mất quà lưu niệm. Người duy nhất còn nhớ là Aman. Là một tình nguyện viên nhiệt tình và mong muốn IOI diễn ra hoàn hảo, anh muốn chuyển hết quà cho các đội trong thời gian ngắn nhất.

Địa điểm tổ chức lễ khai mạc là một vòng tròn được chia thành \(L\) khoang giống nhau. Các khoang được đánh số liên tiếp quanh vòng tròn từ \(0\) đến \(L-1\). Với \(0 \le i \le L-2\), khoang \(i\) kề khoang \(i+1\); khoang \(0\) cũng kề khoang \(L-1\). Có \(N\) đội tại đây, mỗi đội ngồi trong một khoang. Một khoang có thể chứa số đội tùy ý; cũng có thể không có đội nào.

Có \(N\) phần quà giống nhau. Ban đầu, Aman và tất cả phần quà đều ở khoang \(0\). Aman phải phát cho mỗi đội một phần quà, rồi quay về khoang \(0\) sau khi phát phần quà cuối cùng. Lưu ý rằng có thể có đội ngồi ngay tại khoang \(0\).

Tại mọi thời điểm, Aman chỉ mang được tối đa \(K\) phần quà. Anh phải lấy quà ở khoang \(0\) và việc lấy quà không tốn thời gian. Mỗi phần quà phải được mang theo cho đến khi được trao cho một đội. Khi mang theo ít nhất một phần quà và đến khoang có đội chưa nhận quà, Aman có thể trao cho đội đó một phần quà mình đang mang. Việc trao quà cũng không tốn thời gian. Chỉ việc di chuyển mới tốn thời gian: Aman có thể đi quanh vòng tròn theo cả hai chiều; mỗi lần sang một khoang kề, theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ, mất đúng một giây, bất kể đang mang bao nhiêu phần quà.

Hãy tìm số giây ít nhất để Aman phát hết quà rồi trở về vị trí ban đầu.

Ví dụ

Có \(N=3\) đội, Aman mang được \(K=2\) phần quà, và có \(L=8\) khoang. Các đội ngồi ở các khoang \(1\), \(2\) và \(5\).

Hình minh họa một phương án tối ưu. Trong chuyến đầu, Aman lấy hai phần quà, phát một phần cho đội ở khoang \(2\), phần còn lại cho đội ở khoang \(5\), rồi trở về khoang \(0\). Chuyến này mất \(8\) giây. Trong chuyến thứ hai, anh mang phần quà còn lại đến đội ở khoang \(1\), rồi quay về khoang \(0\), mất thêm \(2\) giây. Tổng thời gian là \(10\) giây.

Chi tiết cài đặt

Cài đặt hàm sau trong C hoặc C++, sử dụng header dùng chung boxes.h:

long long delivery(int N, int K, int L, int p[]);

Trong Java, cài đặt phương thức sau trong lớp boxes:

public long delivery(int N, int K, int L, int[] p)

Tham số p trong tệp mẫu chính thức chính là mảng positions được mô tả dưới đây; tên tham số không ảnh hưởng đến giao diện.

• Hàm delivery được chương trình chấm gọi đúng một lần.
• N: số đội.
• K: số phần quà tối đa Aman có thể mang cùng lúc.
• L: số khoang tại địa điểm tổ chức lễ khai mạc.
• positions: mảng có \(N\) phần tử; positions[0], ..., positions[N-1] là số hiệu khoang của các đội. Các phần tử được sắp theo thứ tự không giảm và thuộc đoạn \([0,L-1]\).
• Hàm trả về số giây ít nhất để Aman hoàn thành việc phát quà và quay về khoang \(0\). Kết quả dùng kiểu số nguyên 64 bit.

Chỉ nộp phần cài đặt hàm, không viết main. C và C++ đều dùng #include "boxes.h"; LQDOJ cung cấp cùng tên header cho cả hai ngôn ngữ. Java dùng lớp boxes, không viết phương thức main.

Phân nhóm

Mỗi subtask được trọn số điểm nếu tất cả các test thuộc subtask đều đúng; nếu không, subtask được \(0\) điểm. Các test mẫu là pretest \(0\) điểm.

Chương trình chấm mẫu

Chương trình chấm mẫu đọc dữ liệu theo định dạng:

• Dòng \(1\): N K L.
• Dòng \(2\): positions[0] ... positions[N-1].

Chương trình in giá trị trả về của delivery. Gói đính kèm dùng các tệp boxes.in và boxes.out; bộ chấm LQDOJ đã chuyển phần đọc/ghi của grader sang đầu vào/đầu ra chuẩn, không thay đổi giao diện hàm.

Dữ liệu vào:

3 2 8
1 2 5

Kết quả:

10

Amina có sáu đồng xu, đánh số từ \(1\) đến \(6\). Cô biết trọng lượng của chúng đôi một khác nhau và muốn sắp xếp chúng theo trọng lượng. Để làm việc này, cô đã thiết kế một loại cân mới.

Cân truyền thống có hai đĩa: đặt một đồng xu lên mỗi đĩa, cân sẽ cho biết đồng nào nặng hơn. Cân của Amina phức tạp hơn, có bốn đĩa mang nhãn \(A\), \(B\), \(C\), \(D\) và bốn chế độ hoạt động, mỗi chế độ trả lời một câu hỏi khác nhau. Khi sử dụng cân, phải đặt đúng một đồng xu lên từng đĩa \(A\), \(B\), \(C\). Riêng chế độ thứ tư còn phải đặt đúng một đồng xu lên đĩa \(D\).

Bốn chế độ trả lời các câu hỏi sau:

1. Trong các đồng xu trên \(A\), \(B\), \(C\), đồng nào nặng nhất?
2. Trong các đồng xu trên \(A\), \(B\), \(C\), đồng nào nhẹ nhất?
3. Trong các đồng xu trên \(A\), \(B\), \(C\), đồng nào có trọng lượng ở giữa, tức không nặng nhất cũng không nhẹ nhất?
4. Trong các đồng xu trên \(A\), \(B\), \(C\), chỉ xét những đồng nặng hơn đồng trên \(D\). Nếu có, trả về đồng nhẹ nhất trong số đó. Nếu không có, trả về đồng nhẹ nhất trong cả ba đồng trên \(A\), \(B\), \(C\).

Hãy viết chương trình sắp xếp sáu đồng xu của Amina theo trọng lượng bằng cách gọi các phép cân. Chương trình phải giải nhiều test; mỗi test ứng với một bộ sáu đồng xu mới.

Chi tiết cài đặt

Trong C hoặc C++, cài đặt hai hàm sau trong header dùng chung scales.h:

void init(int T);
void orderCoins();

Chương trình chấm cung cấp các hàm:

void answer(int W[]);
int getMedian(int A, int B, int C);
int getHeaviest(int A, int B, int C);
int getLightest(int A, int B, int C);
int getNextLightest(int A, int B, int C, int D);

Trong Java, cài đặt các phương thức sau trong lớp scales:

public void init(int T)
public void orderCoins()

Các phương thức do chương trình chấm Java cung cấp được gọi qua grader.lib:

public static void answer(int[] W)
public static int getMedian(int A, int B, int C)
public static int getHeaviest(int A, int B, int C)
public static int getLightest(int A, int B, int C)
public static int getNextLightest(int A, int B, int C, int D)

Trong mỗi lần chạy, chương trình chấm gọi init(T) trước tiên và đúng một lần. T là số test của lần chạy, \(1 \le T \le 18\). Bạn có thể khởi tạo các biến tại đây; hàm không trả về giá trị.

Sau đó, orderCoins() được gọi đúng một lần cho mỗi test. Hàm phải tìm thứ tự đúng bằng cách gọi getHeaviest, getLightest, getMedian và/hoặc getNextLightest. Khi biết thứ tự, gọi answer(W) để báo kết quả, rồi kết thúc orderCoins. Hàm không trả về giá trị.

• answer(W): W là mảng dài \(6\). Các phần tử W[0] đến W[5] phải là các số hiệu đồng xu từ \(1\) đến \(6\), theo thứ tự từ nhẹ nhất đến nặng nhất. Chỉ được gọi hàm này từ orderCoins, đúng một lần trong mỗi test. Hàm không trả về giá trị.
• getHeaviest(A, B, C), getLightest(A, B, C), getMedian(A, B, C) tương ứng với các chế độ \(1\), \(2\), \(3\). Các đối số là số hiệu đồng xu đặt trên các đĩa tương ứng, phải là ba số nguyên phân biệt trong đoạn \([1,6]\). Mỗi hàm trả về một trong A, B, C, là số hiệu đồng xu được chọn. Chẳng hạn, getHeaviest trả về số hiệu đồng nặng nhất trong ba đồng.
• getNextLightest(A, B, C, D) tương ứng với chế độ \(4\). Bốn đối số phải là các số nguyên đôi một khác nhau trong đoạn \([1,6]\). Hàm trả về một trong A, B, C: đồng nhẹ nhất trong số những đồng nặng hơn đồng D; nếu không đồng nào nặng hơn D, trả về đồng nhẹ nhất trong cả ba.

Chỉ nộp phần cài đặt hàm, không viết main. C và C++ đều dùng #include "scales.h"; LQDOJ cung cấp cùng tên header cho cả hai ngôn ngữ. Java dùng lớp scales, không viết phương thức main. Không đọc trực tiếp dữ liệu bí mật; chỉ lấy thông tin qua các hàm cân được cung cấp.

Cách tính điểm chính thức

Bài này không chia subtask. Điểm phụ thuộc vào số lần cân, tức tổng số lần gọi getLightest, getHeaviest, getMedian và getNextLightest.

Chương trình được chạy nhiều lần, mỗi lần có nhiều test. Gọi \(r\) là số lần chạy; \(r\) cố định bởi bộ dữ liệu. Nếu chương trình sắp xếp sai các đồng xu trong bất kỳ test nào của bất kỳ lần chạy nào thì được \(0\) điểm toàn bài. Nếu mọi kết quả đều đúng, mỗi lần chạy được tính điểm riêng như sau.

Gọi \(Q\) là số nhỏ nhất sao cho có thể sắp xếp mọi bộ sáu đồng xu bằng \(Q\) lần cân trên cân của Amina. Đề thi chính thức không công bố giá trị \(Q\) để tăng tính thử thách.

Giả sử số lần cân lớn nhất trong tất cả các test của tất cả các lần chạy là \(Q+y\), với \(y\) nguyên. Xét một lần chạy cụ thể: số lần cân lớn nhất trong các test của lần chạy này là \(Q+x\), với \(x\) nguyên không âm. Nếu mọi test trong lần chạy đều dùng ít hơn \(Q\) lần cân thì đặt \(x=0\). Điểm của lần chạy là

làm tròn xuống đến hai chữ số sau dấu thập phân. Điểm toàn bài là tổng điểm các lần chạy. Đặc biệt, nếu chương trình dùng không quá \(Q\) lần cân cho mỗi test của mọi lần chạy, bạn được \(100\) điểm.

Cách tính điểm trên LQDOJ

LQDOJ chấm từng tệp độc lập và lấy điểm nhỏ nhất trong batch; checker của một tệp không biết số lần cân ở các tệp khác. Vì thế không thể tái hiện đúng phần thưởng theo từng lần chạy của công thức chính thức ở trên.

Bộ dữ liệu chính thức có \(r=40\) lần chạy tính điểm; giá trị tối ưu là \(Q=6\). Với một tệp có số lần cân lớn nhất là \(q\), đặt \(x=\max(0,q-6)\). Checker cho tệp đó hệ số

Điểm LQDOJ là \(100\) nhân hệ số nhỏ nhất trong \(40\) tệp. Nếu có bất kỳ thứ tự sai, lời gọi không hợp lệ, thiếu hoặc thừa lần gọi answer, thì toàn bài được \(0\) điểm. Các mẫu là pretest \(0\) điểm, không tham gia batch tính điểm.

Nếu mọi kết quả đúng và \(y=\max x\) trên tất cả các tệp, điểm LQDOJ bằng \(100f(y)\). Đây là cận dưới của điểm chính thức: công thức chính thức còn thưởng những lần chạy có \(x<y\), trong khi bản này dùng trường hợp xấu nhất cho tất cả các lần chạy. Hai cách cho cùng điểm khi mọi lần chạy có cùng \(x\); đặc biệt, hành vi đạt trọn \(100\) điểm là chính xác: mọi test phải đúng và dùng không quá \(6\) lần cân. Khi thực hiện lần cân thứ \(629\) trong một test, điểm theo bản điều chỉnh đã bằng \(0\), nên grader dừng ngay. Các giới hạn thời gian và bộ nhớ vẫn áp dụng.

Ví dụ

Giả sử thứ tự từ nhẹ nhất đến nặng nhất là \(3,4,6,2,1,5\).

Chương trình chấm mẫu

• Dòng \(1\): số test T.
• Mỗi dòng từ \(2\) đến \(T+1\): sáu số phân biệt từ \(1\) đến \(6\), là thứ tự các đồng xu từ nhẹ nhất đến nặng nhất.

Ví dụ với hai test có thứ tự \(1,2,3,4,5,6\) và \(3,4,6,2,1,5\):

2
1 2 3 4 5 6
3 4 6 2 1 5

Đề chính thức mô tả chương trình chấm mẫu in mảng được truyền cho answer. Mã grader trong gói chính thức còn in số lần cân sau mỗi mảng. Grader trên LQDOJ giữ định dạng gồm sáu số hiệu đồng xu, rồi số lần cân, và dùng đầu vào/đầu ra chuẩn thay cho các tệp scales.in, scales.out.

Một lớp có \(N\) sinh viên, đánh số từ \(0\) đến \(N-1\). Mỗi ngày, giáo viên giao một số đề tài cho lớp. Mỗi đề tài phải được một đội sinh viên hoàn thành ngay trong ngày đó. Các đề tài có thể có độ khó khác nhau. Với mỗi đề tài, giáo viên biết chính xác số sinh viên cần có trong đội thực hiện đề tài, gọi là kích thước đội.

Các sinh viên có thể thích những kích thước đội khác nhau. Cụ thể, sinh viên \(i\) chỉ có thể được phân vào đội có kích thước từ \(A[i]\) đến \(B[i]\), kể cả hai đầu mút. Trong một ngày, mỗi sinh viên được phân vào nhiều nhất một đội; có thể có sinh viên không thuộc đội nào. Mỗi đội thực hiện một đề tài.

Giáo viên đã chọn các đề tài cho từng ngày trong \(Q\) ngày sắp tới. Với mỗi ngày, hãy xác định có thể phân sinh viên vào các đội sao cho mỗi đề tài có một đội thực hiện hay không.

Ví dụ

Có \(N=4\) sinh viên và \(Q=2\) ngày. Giới hạn kích thước đội của các sinh viên là:

Ngày đầu có \(M=2\) đề tài, cần các đội có kích thước \(K[0]=1\) và \(K[1]=3\). Có thể phân sinh viên \(0\) vào đội một người và ba sinh viên còn lại vào đội ba người.

Ngày thứ hai cũng có \(M=2\) đề tài nhưng cần \(K[0]=1\) và \(K[1]=1\). Không thể lập đủ các đội vì chỉ một sinh viên có thể làm việc trong đội một người.

Chi tiết cài đặt

Cho thông tin về các sinh viên qua \(N\), \(A\), \(B\) và \(Q\) câu hỏi, mỗi câu hỏi ứng với một ngày. Mỗi câu hỏi gồm số đề tài \(M\) và mảng \(K\) có \(M\) phần tử chứa kích thước đội cần cho từng đề tài. Với mỗi câu hỏi, chương trình phải trả lời có thể thành lập tất cả các đội hay không.

Trong C hoặc C++, cài đặt các hàm trong header dùng chung teams.h:

void init(int N, int A[], int B[]);
int can(int M, int K[]);

Trong Java, cài đặt các phương thức sau trong lớp teams:

public void init(int N, int[] A, int[] B)
public int can(int M, int[] K)

Hàm init(N, A, B) được gọi trước tiên và đúng một lần:

• N: số sinh viên.
• A: mảng có \(N\) phần tử; A[i] là kích thước đội nhỏ nhất mà sinh viên \(i\) có thể tham gia.
• B: mảng có \(N\) phần tử; B[i] là kích thước đội lớn nhất mà sinh viên \(i\) có thể tham gia.
• Với mọi \(0 \le i < N\), có \(1 \le A[i] \le B[i] \le N\).
• Hàm không trả về giá trị.

Sau một lần gọi init, chương trình chấm gọi can(M, K) liên tiếp \(Q\) lần, mỗi lần cho một ngày:

• M: số đề tài trong ngày đó, \(1 \le M \le N\).
• K: mảng có \(M\) phần tử chứa kích thước đội cần cho từng đề tài; \(1 \le K[i] \le N\) với \(0 \le i < M\).
• Trả về \(1\) nếu có thể thành lập tất cả các đội theo yêu cầu; ngược lại trả về \(0\).
• Tổng các giá trị K[i] có thể lớn hơn \(N\).

Các ngày độc lập: việc phân đội ở một ngày không làm mất sinh viên cho những ngày khác. Chỉ nộp phần cài đặt hàm, không viết main. C và C++ đều dùng #include "teams.h"; LQDOJ cung cấp cùng tên header cho cả hai ngôn ngữ. Java dùng lớp teams, không viết phương thức main.

Phân nhóm

Gọi \(S\) là tổng các giá trị M trong tất cả các lần gọi can(M, K). Mỗi subtask được trọn điểm nếu tất cả test của subtask đều đúng, nếu không được \(0\) điểm. Test mẫu là pretest \(0\) điểm.

Chương trình chấm mẫu

Dữ liệu được đọc theo định dạng:

• Dòng \(1\): N.
• Các dòng \(2,\ldots,N+1\): A[i] B[i] lần lượt với \(i=0,\ldots,N-1\).
• Dòng \(N+2\): Q.
• Các dòng \(N+3,\ldots,N+Q+2\): M K[0] K[1] ... K[M-1].

Với mỗi câu hỏi, chương trình chấm in giá trị trả về của can trên một dòng. Gói đính kèm dùng teams.in và teams.out; grader trên LQDOJ dùng đầu vào/đầu ra chuẩn, giữ nguyên giao diện hàm.

Dữ liệu mẫu trong gói chính thức (cùng tình huống ví dụ, với thứ tự sinh viên khác):

4
2 4
1 2
2 3
2 3
2
2 1 3
2 1 1

Kết quả:

1
0