IOI 2019 - Ngày 2

Azerbaijan nổi tiếng về thảm. Là một nhà thiết kế thảm bậc thầy, bạn muốn tạo ra một thiết kế mới bằng cách vẽ một đường gấp khúc. Một đường gấp khúc là một dãy gồm \(t\) đoạn thẳng trên mặt phẳng hai chiều, được xác định bởi một dãy \(t+1\) điểm \(p_0, \ldots, p_t\) như sau: với mỗi \(0 \leq j \leq t-1\), có một đoạn thẳng nối điểm \(p_j\) với điểm \(p_{j+1}\).

Để thực hiện thiết kế mới, bạn đã đánh dấu \(n\) dấu chấm trên mặt phẳng hai chiều. Tọa độ của dấu chấm \(i\) (\(1 \leq i \leq n\)) là \((x[i], y[i])\). Không có hai dấu chấm nào có cùng tọa độ \(x\) hoặc cùng tọa độ \(y\).

Bây giờ bạn muốn tìm một dãy các điểm \((sx[0], sy[0]), (sx[1], sy[1]), \ldots, (sx[k], sy[k])\) xác định một đường gấp khúc thỏa mãn:

• Bắt đầu từ \((0, 0)\) (nghĩa là \(sx[0] = 0\) và \(sy[0] = 0\)).
• Chứa tất cả các dấu chấm (không nhất thiết phải tại các điểm đầu mút của các đoạn).
• Chỉ bao gồm các đoạn ngang hoặc dọc (hai điểm liên tiếp xác định đường gấp khúc có tọa độ \(x\) hoặc tọa độ \(y\) bằng nhau).

Đường gấp khúc được phép tự cắt hoặc chồng lên chính nó theo bất kỳ cách nào. Cụ thể, mỗi điểm trên mặt phẳng có thể thuộc vào một số lượng tùy ý các đoạn của đường gấp khúc.

Đây là bài toán chỉ nộp kết quả đầu ra (output-only) với cách tính điểm một phần. Bạn được cho \(10\) tệp đầu vào xác định vị trí của các dấu chấm. Đối với mỗi tệp đầu vào, bạn cần nộp một tệp đầu ra mô tả một đường gấp khúc thỏa mãn các yêu cầu. Đối với mỗi tệp đầu ra mô tả một đường gấp khúc hợp lệ, điểm của bạn phụ thuộc vào số đoạn trong đường gấp khúc (xem phần Cách tính điểm bên dưới).

Bạn không nộp mã nguồn cho bài toán này.

Khuôn dạng dữ liệu vào

Mỗi tệp dữ liệu vào có khuôn dạng sau:

• Dòng \(1\): \(n\).
• Dòng \(1+i\) (với \(1 \leq i \leq n\)): \(x[i]\; y[i]\).

Khuôn dạng kết quả ra

Mỗi tệp kết quả ra phải có khuôn dạng sau:

• Dòng \(1\): \(k\) — số đoạn của đường gấp khúc.
• Dòng \(1+j\) (với \(1 \leq j \leq k\)): \(sx[j]\; sy[j]\).

Chú ý rằng dòng thứ hai phải chứa \(sx[1]\) và \(sy[1]\) (nghĩa là kết quả ra không chứa \(sx[0]\) và \(sy[0]\)). Mỗi \(sx[j]\) và \(sy[j]\) phải là số nguyên.

Ví dụ

4
2 1
3 3
4 4
5 2

6
2 0
2 3
5 3
5 2
4 2
4 4

Các ràng buộc

• \(1 \leq n \leq 100\,000\).
• \(1 \leq x[i], y[i] \leq 10^9\).
• Tất cả các giá trị của \(x[i]\) và \(y[i]\) đều là số nguyên.
• Không có hai dấu chấm nào có cùng tọa độ \(x\) hoặc cùng tọa độ \(y\), nghĩa là \(x[i_1] \neq x[i_2]\) và \(y[i_1] \neq y[i_2]\) với \(i_1 \neq i_2\).
• \(-2 \cdot 10^9 \leq sx[j], sy[j] \leq 2 \cdot 10^9\).
• Kích thước của mỗi tệp được nộp (tệp kết quả đầu ra hoặc tệp nén ZIP) không được vượt quá 15 MB.

Cách tính điểm

Có \(10\) trường hợp kiểm thử được tính điểm, đánh số từ 01 đến 10. Mỗi trường hợp có điểm tối đa là \(10\), tổng cộng \(100\) điểm. Ví dụ 00 có \(0\) điểm.

Bạn nhận \(0\) điểm cho một trường hợp kiểm thử nếu kết quả đầu ra không xác định một đường gấp khúc thỏa mãn các yêu cầu. Ngược lại, điểm số được xác định bằng một dãy giảm \(c_1, \ldots, c_{10}\), thay đổi theo từng trường hợp kiểm thử.

Giả sử lời giải của bạn là một đường gấp khúc hợp lệ gồm \(k\) đoạn. Khi đó, bạn nhận được:

• \(i\) điểm, nếu \(k = c_i\) (với \(1 \leq i \leq 10\)).
• \(i + \dfrac{c_i - k}{c_i - c_{i+1}}\) điểm, nếu \(c_{i+1} < k < c_i\) (với \(1 \leq i \leq 9\)).
• \(0\) điểm, nếu \(k > c_1\).
• \(10\) điểm, nếu \(k < c_{10}\).

Dãy \(c_1, \ldots, c_{10}\) cho từng trường hợp kiểm thử được cho trong bảng sau. Các trường hợp từ 07 đến 10 dùng chung cột cuối.

Trình hiển thị

Gói đính kèm của bài toán có chương trình vis.py cho phép trực quan hóa các tệp đầu vào và đầu ra.

Để trực quan hóa một tệp đầu vào, sử dụng lệnh:

python vis.py [input file]

Bạn cũng có thể trực quan hóa lời giải của mình cho một tệp đầu vào bằng lệnh sau. Do các giới hạn kỹ thuật, trình hiển thị được cung cấp chỉ hiển thị \(1000\) đoạn đầu tiên của tệp kết quả đầu ra.

python vis.py [input file] --solution [output file]

Ví dụ:

python vis.py examples/00.in --solution examples/00.out

Nguồn: Đề thi chính thức IOI 2019, ngày thi thứ hai, bài Broken Line (line); bản tiếng Việt và bản Markdown của ban tổ chức, đối chiếu với gói đính kèm và bộ chấm chính thức.

Bạn đang cài đặt một chương trình thị giác cho một con robot. Mỗi lần camera của robot chụp một bức ảnh, bức ảnh được lưu dưới dạng ảnh đen trắng trong bộ nhớ của robot. Mỗi ảnh là một lưới điểm ảnh kích thước \(H \times W\), với các hàng được đánh số từ \(0\) đến \(H-1\) và các cột được đánh số từ \(0\) đến \(W-1\). Có chính xác hai điểm ảnh đen trong mỗi bức ảnh; tất cả các điểm ảnh còn lại đều màu trắng.

Robot có thể xử lý mỗi bức ảnh bằng một chương trình gồm các lệnh đơn giản. Bạn được cung cấp các giá trị \(H\), \(W\) và một số nguyên dương \(K\). Nhiệm vụ của bạn là viết một thủ tục tạo ra chương trình cho robot để, với bất kỳ bức ảnh nào, xác định xem khoảng cách giữa hai điểm ảnh đen có bằng chính xác \(K\) hay không.

Khoảng cách giữa điểm ảnh ở hàng \(r_1\), cột \(c_1\) và điểm ảnh ở hàng \(r_2\), cột \(c_2\) là

Trong công thức này, \(|x|\) biểu thị giá trị tuyệt đối của \(x\), bằng \(x\) nếu \(x \geq 0\) và bằng \(-x\) nếu \(x<0\).

Sau đây là cách thức hoạt động của robot.

Bộ nhớ của robot là một mảng đủ lớn gồm các ô nhớ được đánh số bắt đầu từ \(0\). Mỗi ô lưu trữ \(0\) hoặc \(1\); một khi đã được thiết lập, giá trị của ô không thay đổi nữa. Bức ảnh được lưu lần lượt theo từng hàng trong các ô từ \(0\) đến \(H \cdot W-1\). Hàng đầu tiên được lưu trong các ô từ \(0\) đến \(W-1\), còn hàng cuối cùng được lưu trong các ô từ \((H-1)\cdot W\) đến \(H\cdot W-1\). Cụ thể, ô \(i\cdot W+j\) có giá trị \(1\) nếu điểm ảnh ở hàng \(i\), cột \(j\) là màu đen, và có giá trị \(0\) nếu điểm ảnh đó là màu trắng.

Chương trình của robot là một dãy lệnh, được đánh số bằng các số nguyên liên tiếp bắt đầu từ \(0\). Khi chương trình chạy, các lệnh được thực hiện lần lượt. Mỗi lệnh đọc giá trị của một hoặc nhiều ô nhớ (gọi là dữ liệu đầu vào của lệnh) và tạo ra một giá trị duy nhất bằng \(0\) hoặc \(1\) (gọi là dữ liệu đầu ra của lệnh). Đầu ra của lệnh \(i\) được lưu trong ô \(H\cdot W+i\). Đầu vào của lệnh \(i\) chỉ có thể lấy từ các ô lưu điểm ảnh hoặc đầu ra của các lệnh trước đó, tức là các ô từ \(0\) đến \(H\cdot W+i-1\).

Có bốn loại lệnh:

Đầu ra của lệnh cuối cùng trong chương trình phải bằng \(1\) nếu khoảng cách giữa hai điểm ảnh đen bằng chính xác \(K\), và bằng \(0\) trong trường hợp ngược lại.

Chi tiết cài đặt

Bạn cần viết tệp vision.cpp, khai báo #include "vision.h" và cài đặt thủ tục sau. Trình chấm cung cấp hàm main.

void construct_network(int H, int W, int K);

• \(H\), \(W\): các chiều của mỗi bức ảnh được camera của robot chụp.
• \(K\): một số nguyên dương.
• Thủ tục này phải tạo ra chương trình cho robot để xác định, với bất kỳ bức ảnh nào được camera chụp, liệu khoảng cách giữa hai điểm ảnh đen có bằng chính xác \(K\) hay không.

Chương trình của robot ban đầu rỗng. Thủ tục construct_network phải gọi một hoặc nhiều hàm sau để thêm các lệnh vào cuối chương trình. Trong C++, các hàm được khai báo trong vision.h như sau:

int add_not(int N);
int add_and(std::vector<int> Ns);
int add_or(std::vector<int> Ns);
int add_xor(std::vector<int> Ns);

• Các hàm lần lượt thêm một lệnh NOT, AND, OR hoặc XOR.
• N (đối với add_not) là chỉ số ô nhớ mà lệnh NOT vừa thêm sẽ đọc làm đầu vào.
• Ns (đối với add_and, add_or, add_xor) là mảng chứa các chỉ số ô nhớ mà lệnh tương ứng vừa thêm sẽ đọc làm đầu vào.
• Mỗi hàm trả về chỉ số ô nhớ lưu đầu ra của lệnh vừa thêm. Các lời gọi liên tiếp đến những hàm này trả về các số nguyên liên tiếp bắt đầu từ \(H\cdot W\).

Chương trình của robot được có tối đa \(10\,000\) lệnh. Tổng số giá trị đầu vào mà tất cả các lệnh đọc được không vượt quá \(1\,000\,000\). Nói cách khác, tổng độ dài các mảng Ns trong mọi lời gọi add_and, add_or, add_xor, cộng với số lần gọi add_not, không được vượt quá \(1\,000\,000\).

Sau khi thêm lệnh cuối cùng, thủ tục construct_network phải kết thúc và trả quyền điều khiển cho trình chấm. Chương trình của robot sau đó được chạy trên một số bức ảnh. Bài nộp vượt qua một trường hợp kiểm thử nếu, với mỗi bức ảnh được kiểm tra, đầu ra của lệnh cuối cùng bằng \(1\) khi và chỉ khi khoảng cách giữa hai điểm ảnh đen bằng \(K\).

Quá trình chấm có thể trả về một trong các thông báo lỗi sau:

Ví dụ

Giả sử \(H=2\), \(W=3\), \(K=3\). Chỉ có hai bức ảnh mà khoảng cách giữa hai điểm ảnh đen bằng \(3\).

• Trường hợp 1: các điểm ảnh đen có chỉ số ô nhớ \(0\) và \(5\).
• Trường hợp 2: các điểm ảnh đen có chỉ số ô nhớ \(2\) và \(3\).

Một cách xây dựng chương trình cho robot là thực hiện lần lượt các lời gọi sau (viết theo cú pháp C++):

1. add_and({0, 5}): thêm lệnh có đầu ra bằng \(1\) khi và chỉ khi trường hợp thứ nhất xảy ra. Đầu ra được lưu trong ô \(6\).
2. add_and({2, 3}): thêm lệnh có đầu ra bằng \(1\) khi và chỉ khi trường hợp thứ hai xảy ra. Đầu ra được lưu trong ô \(7\).
3. add_or({6, 7}): thêm lệnh có đầu ra bằng \(1\) khi và chỉ khi một trong hai trường hợp trên xảy ra. Đây là lệnh cuối cùng của chương trình; đầu ra được lưu trong ô \(8\).

Các ràng buộc

• \(1 \leq H \leq 200\).
• \(1 \leq W \leq 200\).
• \(2 \leq H\cdot W\).
• \(1 \leq K \leq H+W-2\).

Giới hạn thời gian: \(1\) giây. Giới hạn bộ nhớ: \(1024\) MiB.

Các subtasks

Điểm của bài là tổng điểm các subtask vượt qua. Để nhận điểm của một subtask, bài nộp phải vượt qua tất cả các trường hợp kiểm thử của subtask đó. Nhóm kiểm thử mẫu có \(0\) điểm.

Trình chấm mẫu

Trình chấm mẫu trong gói đính kèm đọc dữ liệu đầu vào theo định dạng sau:

• Dòng \(1\): \(H\;W\;K\).
• Dòng \(2+i\) (\(i\geq 0\)): \(r_1[i]\;c_1[i]\;r_2[i]\;c_2[i]\).
• Dòng cuối cùng: \(-1\).

Mỗi dòng, trừ dòng đầu tiên và dòng cuối cùng, biểu diễn một bức ảnh có hai điểm ảnh đen. Gọi bức ảnh được mô tả ở dòng \(2+i\) là bức ảnh \(i\). Một điểm ảnh đen nằm ở hàng \(r_1[i]\), cột \(c_1[i]\); điểm ảnh đen còn lại nằm ở hàng \(r_2[i]\), cột \(c_2[i]\).

Trước tiên, trình chấm mẫu gọi construct_network(H, W, K). Nếu construct_network vi phạm một ràng buộc được mô tả trong đề, trình chấm mẫu in một trong các thông báo lỗi liệt kê ở cuối phần Chi tiết cài đặt rồi thoát.

Nếu không có lỗi, trình chấm mẫu tạo ra hai kết quả đầu ra.

Thứ nhất, trình chấm mẫu in đầu ra của chương trình robot theo định dạng:

• Dòng \(1+i\) (\(i\geq 0\)): đầu ra của lệnh cuối cùng trong chương trình robot đối với bức ảnh \(i\) (\(1\) hoặc \(0\)).

Thứ hai, trình chấm mẫu ghi tệp log.txt trong thư mục hiện tại theo định dạng:

• Dòng \(1+i\) (\(i\geq 0\)): \(m[i][0]\;m[i][1]\;\ldots\;m[i][c-1]\).

Dãy trên dòng \(1+i\) mô tả các giá trị trong bộ nhớ robot sau khi chương trình chạy với bức ảnh \(i\) làm đầu vào. Cụ thể, \(m[i][j]\) là giá trị của ô nhớ \(j\). Độ dài \(c\) của dãy bằng \(H\cdot W\) cộng với số lệnh trong chương trình robot.

Trong trình chấm mẫu được cung cấp, nếu một dòng mô tả ảnh có tọa độ nằm ngoài ảnh hoặc hai điểm ảnh trùng nhau, trình chấm in \(-1\) và ghi \(-1\) vào dòng tương ứng của log.txt, rồi tiếp tục đọc ảnh tiếp theo. Dòng chỉ chứa \(-1\) vẫn là dấu kết thúc dữ liệu đầu vào.

Dữ liệu mẫu trong gói đính kèm

Dữ liệu vào (examples/01.in):

2 3 3
0 0 0 1
0 0 0 2
0 0 1 0
0 0 1 1
0 0 1 2
0 1 0 2
0 1 1 0
0 1 1 1
0 1 1 2
0 2 1 0
0 2 1 1
0 2 1 2
1 0 1 1
1 0 1 2
1 1 1 2
-1

Dữ liệu ra của một chương trình robot đúng (examples/01.out):

0
0
0
0
1
0
0
0
0
1
0
0
0
0
0

Mẫu này liệt kê tất cả \(15\) cách chọn hai điểm ảnh đen trong ảnh \(2\times 3\). Chỉ ảnh thứ \(5\) và ảnh thứ \(10\) trong danh sách có khoảng cách giữa hai điểm ảnh đen bằng \(3\), tương ứng với hai trường hợp trong phần Ví dụ. Nội dung log.txt phụ thuộc vào chương trình robot mà bạn xây dựng.

Nguồn: Đề chính thức IOI 2019, ngày thi 2, bài Vision Program (vision), bản tiếng Việt; đối chiếu với bản Markdown, gói đính kèm và dữ liệu chấm do ban tổ chức cung cấp.

Kenan đã vẽ một sơ đồ các tòa nhà và các đường đi bộ trên cao dọc theo một bên của đại lộ chính ở Baku. Có \(n\) tòa nhà được đánh số từ \(0\) đến \(n-1\) và \(m\) đường đi bộ trên cao được đánh số từ \(0\) đến \(m-1\). Sơ đồ được vẽ trên một mặt phẳng hai chiều, trong đó các tòa nhà là các đoạn thẳng đứng, còn các đường đi bộ trên cao là các đoạn thẳng nằm ngang.

Đáy của tòa nhà \(i\) (\(0 \leq i \leq n-1\)) nằm tại điểm \((x[i], 0)\) và tòa nhà có chiều cao \(h[i]\). Do đó, tòa nhà được biểu diễn bởi đoạn thẳng nối hai điểm \((x[i], 0)\) và \((x[i], h[i])\).

Đường đi bộ trên cao \(j\) (\(0 \leq j \leq m-1\)) có hai đầu mút tại các tòa nhà mang số \(l[j]\) và \(r[j]\), với tung độ dương \(y[j]\). Do đó, đường đi này được biểu diễn bởi đoạn thẳng nối hai điểm \((x[l[j]], y[j])\) và \((x[r[j]], y[j])\).

Một đường đi bộ trên cao và một tòa nhà giao nhau nếu chúng có một điểm chung. Vì vậy, một đường đi bộ trên cao giao với hai tòa nhà tại hai đầu mút của nó, và cũng có thể giao với các tòa nhà khác ở giữa.

Kenan muốn tìm độ dài đường đi ngắn nhất từ đáy tòa nhà \(s\) đến đáy tòa nhà \(g\), với giả thiết rằng một người chỉ có thể đi dọc theo các tòa nhà và các đường đi bộ trên cao, hoặc xác định rằng không tồn tại đường đi như vậy. Lưu ý rằng không được phép đi bộ trên mặt đất, tức là dọc theo đường thẳng nằm ngang có tung độ bằng \(0\).

Một người có thể đi từ một đường đi bộ trên cao vào một tòa nhà hoặc ngược lại tại bất kỳ điểm giao nào. Nếu các đầu mút của hai đường đi bộ trên cao nằm tại cùng một điểm, người đó có thể đi từ đường đi bộ trên cao này sang đường đi bộ trên cao kia.

Nhiệm vụ của bạn là giúp Kenan trả lời câu hỏi trên.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau trong tệp walk.cpp, sử dụng tệp tiêu đề walk.h được cung cấp:

# include "walk.h"

long long min_distance(std::vector<int> x, std::vector<int> h,
                       std::vector<int> l, std::vector<int> r,
                       std::vector<int> y, int s, int g);

• \(x\) và \(h\): các mảng số nguyên có độ dài \(n\), mô tả vị trí và chiều cao của các tòa nhà.
• \(l\), \(r\) và \(y\): các mảng số nguyên có độ dài \(m\), mô tả hai đầu mút và độ cao của các đường đi bộ trên cao.
• \(s\) và \(g\): hai số nguyên chỉ tòa nhà xuất phát và tòa nhà đích.
• Hàm phải trả về độ dài đường đi ngắn nhất giữa đáy tòa nhà \(s\) và đáy tòa nhà \(g\) nếu tồn tại đường đi. Nếu không tồn tại, hàm phải trả về \(-1\).
• Kiểu trả về là số nguyên có dấu 64 bit (long long trong C++, tương ứng với int64 trong mô tả chính thức).
• Trình chấm gọi hàm này đúng một lần cho mỗi trường hợp kiểm thử.

Trình chấm cung cấp hàm main và thực hiện việc đọc, ghi dữ liệu.

Các ví dụ

Ví dụ 1

Xét lời gọi hàm sau, viết theo cú pháp C++:

min_distance({0, 3, 5, 7, 10, 12, 14},
             {8, 7, 9, 7, 6, 6, 9},
             {0, 0, 0, 2, 2, 3, 4},
             {1, 2, 6, 3, 6, 4, 6},
             {1, 6, 8, 1, 7, 2, 5},
             1, 5);

Giá trị trả về đúng là \(27\).

Hình dưới đây minh họa cho Ví dụ 1:

Ví dụ 2

min_distance({0, 4, 5, 6, 9},
             {6, 6, 6, 6, 6},
             {3, 1, 0},
             {4, 3, 2},
             {1, 3, 6},
             0, 4);

Giá trị trả về đúng là \(21\).

Ràng buộc

• \(1 \leq n, m \leq 100\,000\).
• \(0 \leq x[0] < x[1] < \ldots < x[n-1] \leq 10^9\).
• \(1 \leq h[i] \leq 10^9\) với mọi \(0 \leq i \leq n-1\).
• \(0 \leq l[j] < r[j] \leq n-1\) với mọi \(0 \leq j \leq m-1\).
• \(1 \leq y[j] \leq \min(h[l[j]], h[r[j]])\) với mọi \(0 \leq j \leq m-1\).
• \(0 \leq s, g \leq n-1\).
• \(s \neq g\).
• Hai đường đi bộ trên cao không có điểm chung, ngoại trừ có thể tại các đầu mút của chúng.

Giới hạn thời gian: 4 giây. Giới hạn bộ nhớ: 1024 MiB.

Chấm điểm

Tổng điểm là \(100\). Nhóm kiểm thử ví dụ trong gói chính thức có \(0\) điểm.

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu đầu vào theo định dạng sau:

Trình chấm mẫu in ra một dòng duy nhất chứa giá trị trả về của min_distance.

Dữ liệu mẫu 1

Đầu vào:

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

Đầu ra:

27

Dữ liệu mẫu 2

Đầu vào:

5 3
0 6
4 6
5 6
6 6
9 6
3 4 1
1 3 3
0 2 6
0 4

Đầu ra:

21

Nguồn: Đề thi chính thức IOI 2019, ngày thi thứ hai, bài “Sky Walking” (walk); bản tiếng Việt, bản Markdown và gói đính kèm do ban tổ chức cung cấp.