IOI 2002 - Ngày 2

Có \(N\) công việc cần thực hiện trên một máy theo thứ tự từ \(1\) đến \(N\). Bạn chia dãy công việc thành các lô không rỗng; mỗi lô gồm một đoạn công việc liên tiếp. Máy xử lý các lô theo thứ tự của chúng.

Máy bắt đầu hoạt động tại thời điểm \(0\). Trước khi xử lý mỗi lô, máy cần một khoảng thời gian chuẩn bị bằng \(S\), rồi xử lý lần lượt các công việc trong lô. Công việc \(i\) cần thời gian xử lý \(T_i\). Ngay khi toàn bộ lô đã xử lý xong, máy đưa ra đồng thời kết quả của tất cả công việc trong lô. Vì vậy, nếu lô gồm các công việc \(x,x+1,\ldots,x+k\) bắt đầu tại thời điểm \(t\), thời điểm đưa ra kết quả của mỗi công việc trong lô là \(t+S+T_x+T_{x+1}+\cdots+T_{x+k}\). Gọi thời điểm đưa ra kết quả của công việc \(i\) là \(O_i\). Công việc này có hệ số chi phí \(F_i\) và chi phí \(O_iF_i\).

Hãy tìm cách chia lô để tổng chi phí của tất cả công việc nhỏ nhất.

Dữ liệu vào

• Dòng đầu chứa \(N\), với \(1\le N\le 10000\).
• Dòng thứ hai chứa \(S\), với \(0\le S\le 50\).
• Mỗi dòng trong \(N\) dòng tiếp theo chứa \(T_i,F_i\) của công việc \(i\), với \(1\le T_i,F_i\le 100\).

Trong mỗi bộ kiểm tra, tổng chi phí của bất kỳ cách chia lô nào cũng không vượt quá \(2^{31}-1\).

Dữ liệu ra

In một số nguyên là tổng chi phí nhỏ nhất.

Chấm điểm

Có 20 bộ kiểm tra, mỗi bộ tương ứng 5 điểm trong thang điểm gốc 100. Một bộ kiểm tra chỉ được điểm khi kết quả đúng và chương trình chạy trong giới hạn thời gian; ngược lại được 0 điểm.

Ví dụ

2
50
100 100
100 100

45000

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

153

Nguồn

Đề gốc IOI 2002. Tài liệu kỳ thi.

Thành phố Yong-In dự định xây dựng một mạng xe buýt với \(N\) bến, mỗi bến nằm ở một góc phố. Yong-In là một thành phố hiện đại, có bản đồ dạng lưới gồm các khu phố hình vuông bằng nhau. Khoảng cách giữa hai bến là độ dài đường đi ngắn nhất dọc theo các con đường. Do đó, khoảng cách giữa hai bến có tọa độ \((x_1,y_1)\) và \((x_2,y_2)\) được tính bằng \(|x_1-x_2|+|y_1-y_2|\).

Thành phố muốn thiết lập mạng tuyến xe như sau:

• Chọn hai bến khác nhau làm hai bến trung tâm \(H_1,H_2\) và nối trực tiếp chúng với nhau.
• Nối mỗi bến còn lại với đúng một trong hai bến trung tâm.
• Không có tuyến nối trực tiếp nào khác.

Độ dài mỗi tuyến nối trực tiếp bằng khoảng cách giữa hai đầu mút. Để đi giữa hai bến, hành khách sử dụng đường đi duy nhất trong mạng đã thiết lập; độ dài hành trình là tổng độ dài các tuyến trên đường đi đó.

Nếu hai bến \(A,B\) cùng nối với bến trung tâm \(H_1\), hành trình đi từ \(A\) qua \(H_1\) đến \(B\). Nếu \(A\) nối với \(H_1\) còn \(B\) nối với \(H_2\), hành trình đi từ \(A\) qua \(H_1\), rồi \(H_2\) và cuối cùng đến \(B\).

Nhà chức trách Yong-In muốn mọi người dân có thể đến mọi nơi trong thành phố nhanh nhất có thể. Vì vậy, họ muốn chọn hai bến trung tâm và cách nối các bến sao cho hành trình dài nhất giữa hai bến bất kỳ ngắn nhất có thể.

Với mỗi cách chọn hai bến trung tâm và phân các bến còn lại cho chúng, xét hành trình dài nhất giữa một cặp bến bất kỳ. Hãy tìm giá trị nhỏ nhất có thể của độ dài hành trình dài nhất này.

Dữ liệu vào

• Dòng đầu chứa \(N\), với \(2\le N\le 500\).
• Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên \(x,y\) là tọa độ của một bến, với \(1\le x,y\le 5000\).
• Không có hai bến nào cùng vị trí.

Dữ liệu ra

In một số nguyên dương: giá trị nhỏ nhất của độ dài hành trình dài nhất.

Chấm điểm

Có 20 bộ kiểm tra, mỗi bộ tương ứng 5 điểm trong thang điểm gốc 100. Một bộ kiểm tra chỉ được điểm khi kết quả đúng và chương trình chạy trong giới hạn thời gian; ngược lại được 0 điểm.

Ví dụ

6
1 7
16 6
12 4
4 4
1 1
11 1

20

7
7 9
10 9
5 3
1 1
7 2
15 6
17 7

25

Nguồn

Đề gốc IOI 2002. Tài liệu kỳ thi.

Trên lưới vuông \(N\times N\) có hai thanh: một thanh nằm ngang và một thanh thẳng đứng. Mỗi thanh chiếm một dãy ô liên tiếp và có độ dài ít nhất hai ô. Hai thanh có thể dài bằng nhau hoặc khác nhau, và có thể giao nhau tại một ô. Hàng được đánh số từ trên xuống, cột từ trái sang phải, bắt đầu từ \(1\).

Bạn không nhìn thấy các thanh. Bạn có thể hỏi xem một hình chữ nhật trên lưới có chứa ít nhất một ô thuộc một trong hai thanh hay không. Hãy xác định vị trí hai thanh bằng ít câu hỏi nhất có thể.

Trong trường hợp có nhiều cách mô tả cùng tập ô bị chiếm, phải kéo dài mỗi thanh hết mức có thể mà không thay đổi tập ô đó. Chẳng hạn, trong hình, thanh ngang nằm ở hàng 4, từ cột 3 đến cột 8; thanh dọc nằm ở cột 4, từ hàng 4 đến hàng 9, không phải chỉ từ hàng 5 đến hàng 9.

Giao diện thư viện

Đây là bài tương tác qua thư viện. Nộp một tệp C++ định nghĩa hàm void solve_rods(), không định nghĩa main; bộ chấm gọi hàm này. Chương trình không đọc hay ghi tệp, cũng không đọc đầu vào chuẩn hay ghi đầu ra chuẩn. Khai báo #include "crectlib.h" và sử dụng:

int gridsize();
int rect(int a, int b, int c, int d);
void report(int r1, int c1, int r2, int c2,
            int p1, int q1, int p2, int q2);

• Gọi gridsize() ở đầu chương trình để lấy \(N\), với \(5\le N\le10000\).
• rect(a,b,c,d) xét hình chữ nhật gồm các hàng \(a\) đến \(b\) và các cột \(c\) đến \(d\), kể cả biên. Hàm trả về \(1\) nếu hình chữ nhật chứa ít nhất một ô của một thanh, ngược lại trả về \(0\). Phải có \(1\le a\le b\le N\) và \(1\le c\le d\le N\).
• Gọi report đúng một lần để báo đáp án. Hàm này kết thúc chương trình. Bốn tham số đầu là hai đầu mút thanh ngang, theo thứ tự từ trái sang phải; bốn tham số sau là hai đầu mút thanh dọc, theo thứ tự từ trên xuống dưới. Do đó \(r_1=r_2\), \(c_1<c_2\), \(p_1<p_2\) và \(q_1=q_2\).

Vùng tô xám trong hình là hình chữ nhật \([a,b]\times[c,d]\), gồm các hàng từ \(a\) đến \(b\) và các cột từ \(c\) đến \(d\). Trong hình, rect(3,8,3,6) trả về \(1\) vì vùng này chứa ô thuộc các thanh.

Phải gọi rect ít nhất 2 lần và nhiều nhất 400 lần trước khi gọi report, đúng như yêu cầu của đề gốc. Một câu hỏi không hợp lệ hoặc vượt giới hạn số lần gọi làm chương trình kết thúc. Nếu các tham số của report không thỏa mãn điều kiện về đầu mút đã nêu, thư viện gốc thông báo lỗi trên đầu ra chuẩn.

Giao diện FreePascal trong kỳ thi gốc dùng uses prectlib; và các khai báo tương ứng:

function gridsize: LongInt;
function rect(a, b, c, d: LongInt): LongInt;
procedure report(r1, c1, r2, c2, p1, q1, p2, q2: LongInt);

Trong môi trường thi gốc, các lệnh biên dịch là fpc -So -O2 -XS rods.pas, gcc -O2 -static rods.c crectlib.o -lm hoặc g++ -O2 -static rods.cpp crectlib.o -lm. Với RHIDE, thêm crectlib.o vào mục Options -> Linker. Các tệp crodstool.c và prodstool.pas minh họa cách gọi thư viện.

Dữ liệu thử thư viện

Thư viện thử nghiệm gốc đọc tệp rods.in do bạn tạo, có ba dòng:

• Dòng đầu chứa \(N\).
• Dòng thứ hai chứa \(r_1,c_1,r_2,c_2\) mô tả thanh ngang.
• Dòng thứ ba chứa \(p_1,q_1,p_2,q_2\) mô tả thanh dọc.

Thư viện ghi vào rods.out: dòng đầu là số lần gọi rect, hai dòng tiếp theo là hai thanh mà chương trình báo cáo, theo cùng định dạng tọa độ. Tệp rods.log ghi các lời gọi; một câu hỏi được ghi theo dạng k : rect(a,b,c,d) = ans, với k là số thứ tự câu hỏi và ans là câu trả lời. Lỗi được ghi trong rods.out.

Chấm điểm

Có 20 bộ kiểm tra. Nếu vị trí báo cáo sai hoặc chương trình vi phạm điều kiện của giao diện, bộ kiểm tra được 0 điểm. Nếu đáp án đúng, điểm trong thang điểm gốc phụ thuộc số lần gọi rect:

Ví dụ

9
4 3 4 8
4 4 9 4

20
4 3 4 8
4 4 9 4

Nguồn

Đề gốc IOI 2002. Tài liệu kỳ thi.