IOI 2013 - Ngày 1

Câu chuyện xảy ra từ rất lâu, khi Trái Đất mới hình thành và IOI còn chưa có trong mơ.

Serpent sống trong một vùng đất có \(N\) hố nước, được đánh số từ \(0\) đến \(N-1\). Có \(M\) đường mòn hai chiều nối các cặp hố nước để Serpent đi dạo. Giữa mỗi cặp hố nước có nhiều nhất một dãy đường mòn kết nối chúng, trực tiếp hoặc gián tiếp; một số cặp có thể hoàn toàn không được kết nối. Do đó, \(M \le N-1\). Mỗi đường mòn có một số ngày cần thiết để Serpent đi qua, và thời gian này có thể khác nhau giữa các đường mòn.

Kangaroo, bạn của Serpent, muốn xây dựng thêm đúng \(N-M-1\) đường mòn để Serpent có thể đi lại giữa mọi cặp hố nước. Kangaroo có thể nối bất kỳ cặp hố nước nào; mỗi đường mòn mới đều cần \(L\) ngày để đi qua.

Kangaroo muốn xây dựng các đường mòn mới sao cho thời gian đi lại lớn nhất giữa hai hố nước bất kỳ là nhỏ nhất có thể. Hãy xác định thời gian lớn nhất đó sau khi xây dựng tối ưu.

Cài đặt

Bạn cần nộp một tệp cài đặt hàm C/C++ sau và phải dùng #include "dreaming.h":

int travelTime(int N, int M, int L,
        int A[], int B[], int T[]);

Dữ liệu vào

Các tham số N, M, L lần lượt là số hố nước, số đường mòn đã có và số ngày cần để đi qua mỗi đường mòn mới. Các mảng A, B, T có độ dài \(M\), mô tả các đường mòn đã có. Với \(0 \le i < M\), đường mòn có chỉ số \(i\) nối A[i] với B[i] và cần T[i] ngày để đi qua theo một trong hai chiều.

Dữ liệu ra

Hàm travelTime trả về thời gian đi lại lớn nhất giữa mọi cặp hố nước, tính bằng ngày, sau khi thêm \(N-M-1\) đường mòn để tất cả hố nước được kết nối và thời gian lớn nhất này nhỏ nhất có thể.

Ràng buộc

• Giới hạn thời gian: 1 giây.
• Giới hạn bộ nhớ: 64 MiB.
• \(1 \le N \le 100\,000\).
• \(0 \le M \le N-1\).
• \(0 \le A[i], B[i] \le N-1\) với \(0 \le i < M\).
• \(1 \le T[i] \le 10\,000\) với \(0 \le i < M\).
• \(1 \le L \le 10\,000\).

Phân nhóm

Mỗi nhóm tuân theo các ràng buộc chung và các điều kiện bổ sung sau.

Trình chấm mẫu

Trình chấm mẫu đọc tệp dreaming.in theo định dạng:

• Dòng 1: N M L.
• \(M\) dòng tiếp theo: dòng ứng với chỉ số \(i\) chứa A[i] B[i] T[i], theo thứ tự \(i=0,\ldots,M-1\).

Ví dụ

12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3

18

Bạn sắp thi môn Lịch sử Nghệ thuật, nhưng ở trường bạn quan tâm đến tin học hơn các môn nghệ thuật! Bạn cần viết một chương trình để làm bài cho mình.

Bài kiểm tra gồm một số bức tranh. Mỗi bức thuộc một trong bốn kiểu, được đánh số \(1\), \(2\), \(3\), \(4\).

Kiểu 1 gồm các bức tranh trừu tượng. Ví dụ:

Kiểu 2 gồm các bức tranh ấn tượng về phong cảnh. Ví dụ:

Kiểu 3 gồm các bức tranh biểu hiện hành động. Ví dụ:

Kiểu 4 gồm các bức tranh các dải màu sắc. Ví dụ:

Nhiệm vụ của bạn là xác định kiểu của một bức tranh từ ảnh số của bức tranh đó.

Ban giám khảo IOI đã thu thập nhiều ảnh cho mỗi kiểu. Chín ảnh của mỗi kiểu được chọn ngẫu nhiên và cung cấp trên máy tính cùng tài liệu bài toán, để bạn xem xét bằng tay và thử nghiệm. Những ảnh còn lại được dùng khi chấm chương trình của bạn.

Cài đặt

Bạn cần nộp một tệp cài đặt hàm C/C++ sau và phải dùng #include "artclass.h":

int style(int H, int W,
        int R[500][500], int G[500][500], int B[500][500]);

Dữ liệu vào

Ảnh là một lưới \(H \times W\) điểm ảnh. H là số hàng, W là số cột. Các hàng được đánh số từ \(0\) đến \(H-1\) từ trên xuống dưới; các cột được đánh số từ \(0\) đến \(W-1\) từ trái sang phải.

Các mảng hai chiều R, G, B mô tả lần lượt lượng màu đỏ, xanh lá cây và xanh da trời của mỗi điểm ảnh. Phần dữ liệu được sử dụng của mỗi mảng có kích thước \(H \times W\). Các phần tử R[i][j], G[i][j], B[i][j] ứng với điểm ảnh tại hàng \(i\), cột \(j\), và là các số nguyên từ \(0\) đến \(255\), bao gồm cả hai đầu mút. Giá trị \(0\) nghĩa là không có thành phần màu đó; \(255\) nghĩa là lượng tối đa.

Dữ liệu ra

Hàm style trả về kiểu của bức ảnh: một trong các số nguyên \(1\), \(2\), \(3\), \(4\) theo mô tả trên.

Ràng buộc

• Giới hạn thời gian: 5 giây.
• Giới hạn bộ nhớ: 64 MiB.
• \(100 \le H \le 500\).
• \(100 \le W \le 500\).
• \(0 \le R[i][j], G[i][j], B[i][j] \le 255\) với \(0 \le i < H\), \(0 \le j < W\).

Phân nhóm

Bài này không có nhóm con. Điểm được tính theo tỷ lệ ảnh mà chương trình phân loại đúng. Gọi \(P\) là phần trăm số ảnh được phân loại đúng, với \(0 \le P \le 100\). Điểm là:

Như vậy, khi \(25 \le P < 50\), điểm tăng tuyến tính từ \(0\) đến \(10\); khi \(50 \le P < 90\), điểm tăng tuyến tính từ \(10\) đến \(100\). Trong hai khoảng này, kết quả được làm tròn xuống số nguyên gần nhất.

Thực nghiệm

Trình chấm mẫu đọc ảnh từ tệp artclass.jpg. Tệp này bắt buộc phải chứa một ảnh định dạng JPEG.

Bạn được phép dùng mọi ứng dụng xử lý đồ họa trên máy tính để tìm hiểu các bức ảnh, nhưng không bắt buộc phải dùng chúng để giải bài. Các ứng dụng này nằm trong menu Applications > Graphics.

Một đàn gấu túi bị biến đổi gien tràn vào thành phố Brisbane. Bạn phải đưa mọi người đi lánh nạn đến nơi an toàn.

Đường phố Brisbane được bố trí trên một lưới ô vuông lớn. Có \(R\) đường ngang chạy từ đông sang tây, được đánh số từ \(0\) đến \(R-1\) theo thứ tự từ bắc xuống nam, và \(C\) đường dọc chạy từ bắc xuống nam, được đánh số từ \(0\) đến \(C-1\) theo thứ tự từ tây sang đông.

Gấu túi xâm chiếm từ phía bắc, còn mọi người chạy trốn về phía nam. Trên đường ngang, mọi người có thể đi theo cả hai hướng. Trên đường dọc, họ chỉ được đi về phía nam.

Nút giao giữa đường ngang \(P\) và đường dọc \(Q\) được ký hiệu là \((P,Q)\). Mỗi đoạn đường nối hai nút giao kề nhau có một số gấu túi; số lượng này có thể thay đổi theo thời gian. Bạn cần hướng dẫn từng người đi từ một nút giao cho trước trên đường ngang \(0\) đến một nút giao cho trước trên đường ngang \(R-1\), sao cho tổng số gấu túi trên các đoạn đường họ đi qua nhỏ nhất có thể.

Ban đầu, bạn được cho kích thước lưới và số gấu túi trên mỗi đoạn đường. Sau đó có một chuỗi \(E\) sự kiện theo thứ tự. Một sự kiện thay đổi cập nhật số gấu túi trên một đoạn đường. Một sự kiện chạy trốn cho biết một người đến một nút giao trên đường ngang \(0\) và yêu cầu tìm số gấu túi nhỏ nhất người đó phải đi qua để đến một nút giao cho trước trên đường ngang \(R-1\).

Cài đặt

Nộp một tệp cài đặt các hàm C/C++ sau và dùng #include "wombats.h":

void init(int R, int C, int H[5000][200], int V[5000][200]);
void changeH(int P, int Q, int W);
void changeV(int P, int Q, int W);
int escape(int V1, int V2);

Dữ liệu vào

init(R, C, H, V) cung cấp bản đồ ban đầu và cho phép khởi tạo các biến toàn cục, cấu trúc dữ liệu. Hàm này được gọi đúng một lần, trước mọi lời gọi changeH, changeV hoặc escape. R là số đường ngang và C là số đường dọc. Phần dữ liệu được sử dụng của H có kích thước \(R \times (C-1)\): H[P][Q] là số gấu túi trên đoạn ngang từ \((P,Q)\) đến \((P,Q+1)\). Phần dữ liệu được sử dụng của V có kích thước \((R-1) \times C\): V[P][Q] là số gấu túi trên đoạn dọc từ \((P,Q)\) đến \((P+1,Q)\).

changeH(P, Q, W) được gọi khi số gấu túi trên đoạn ngang từ \((P,Q)\) đến \((P,Q+1)\) thay đổi thành W. Các tham số thỏa mãn \(0 \le P \le R-1\), \(0 \le Q \le C-2\), \(0 \le W \le 1\,000\).

changeV(P, Q, W) được gọi khi số gấu túi trên đoạn dọc từ \((P,Q)\) đến \((P+1,Q)\) thay đổi thành W. Các tham số thỏa mãn \(0 \le P \le R-2\), \(0 \le Q \le C-1\), \(0 \le W \le 1\,000\).

escape(V1, V2) mô tả một người chạy từ \((0,V1)\) đến \((R-1,V2)\), với \(0 \le V1,V2 \le C-1\).

Dữ liệu ra

Mỗi lời gọi escape phải trả về tổng số gấu túi nhỏ nhất có thể gặp trên một đường đi hợp lệ giữa hai nút giao được yêu cầu, xét các thay đổi đã xảy ra. Các hàm init, changeH, changeV không trả về giá trị.

Ràng buộc

• Giới hạn thời gian: 20 giây.
• Giới hạn bộ nhớ: 256 MiB.
• \(2 \le R \le 5\,000\).
• \(1 \le C \le 200\).
• Có tổng cộng không quá \(500\) lời gọi changeH và changeV.
• Có không quá \(200\,000\) lời gọi escape.
• Số gấu túi trên mỗi đoạn đường tại mọi thời điểm nằm trong khoảng từ \(0\) đến \(1\,000\).

Phân nhóm

Mỗi nhóm tuân theo các ràng buộc chung và các điều kiện bổ sung sau.

Trình chấm mẫu

Trình chấm mẫu đọc tệp wombats.in:

• Dòng 1: R C.
• Dòng \(2\) đến \(R+1\): mỗi dòng chứa một hàng của H, lần lượt từ H[0][0] ... H[0][C-2] đến H[R-1][0] ... H[R-1][C-2].
• Dòng \(R+2\) đến \(2R\): mỗi dòng chứa một hàng của V, lần lượt từ V[0][0] ... V[0][C-1] đến V[R-2][0] ... V[R-2][C-1].
• Dòng tiếp theo: E.
• \(E\) dòng tiếp theo: mỗi dòng mô tả một sự kiện, theo đúng thứ tự xảy ra.

Nếu \(C=1\), không cần các dòng trống dành cho H (các dòng \(2\) đến \(R+1\) trong định dạng trên).

Các sự kiện có định dạng 1 P Q W cho changeH(P, Q, W), 2 P Q W cho changeV(P, Q, W), và 3 V1 V2 cho escape(V1, V2).

Ví dụ

3 4
0 2 5
7 1 1
0 4 0
0 0 0 2
0 3 4 7
5
3 2 1
3 3 3
2 0 0 5
1 1 1 6
3 2 1

2
7
5