IOI 2014 - Ngày 1

Đài Loan có một hệ thống đường tàu lớn nối hai bờ đông và tây của hòn đảo. Hệ thống gồm \(m\) khối liên tiếp, được đánh số \(0, \ldots, m-1\) bắt đầu từ đầu phía tây. Mỗi khối có một tuyến đường một chiều ở phía bắc đi về hướng tây, một tuyến đường một chiều ở phía nam đi về hướng đông, và có thể có một ga tàu nằm giữa hai tuyến đường.

Có ba loại khối:

• Khối loại C chứa một ga tàu mà bạn phải đi vào từ tuyến phía bắc và đi ra tuyến phía nam.
• Khối loại D chứa một ga tàu mà bạn phải đi vào từ tuyến phía nam và đi ra tuyến phía bắc.
• Khối loại trống không chứa ga tàu.

Ví dụ, trong hình dưới đây, các khối 0, 4 và 6 thuộc loại trống, các khối 1, 2 và 3 thuộc loại C, còn khối 5 thuộc loại D. Các khối nối với nhau theo chiều ngang. Các tuyến tương ứng của hai khối liền kề được nối bởi các điểm nối, được minh họa bằng những hình chữ nhật tô mờ.

Hệ thống có \(n\) ga tàu, được đánh số từ \(0\) đến \(n-1\). Có thể giả thiết rằng ta có thể đi từ bất kỳ ga tàu nào đến bất kỳ ga tàu nào khác bằng cách đi theo tuyến đường. Ví dụ, để đi từ ga 0 đến ga 2, ta xuất phát từ khối 2, đi qua các khối 3 và 4 theo tuyến phía nam, đi qua ga 1 ở khối 5, rồi đi qua khối 4 theo tuyến phía bắc và cuối cùng đến ga 2 ở khối 3.

Vì có thể có nhiều đường đi, khoảng cách từ một ga đến một ga khác được định nghĩa là số lượng nhỏ nhất các điểm nối mà đường đi phải đi qua. Trong ví dụ, đường đi ngắn nhất từ ga 0 đến ga 2 đi qua các khối sau:

2-3-4-5-4-3

Đường đi này đi qua 5 điểm nối, nên khoảng cách là 5.

Hệ thống đường tàu được quản lý bởi máy tính. Không may, sau một sự cố mất điện, máy tính không còn biết các ga nằm ở đâu và nằm trong loại khối nào. Manh mối duy nhất còn lại là số thứ tự của khối chứa ga 0; khối này luôn thuộc loại C. May mắn là máy tính vẫn có thể truy vấn khoảng cách từ một ga bất kỳ đến một ga bất kỳ khác. Chẳng hạn, truy vấn “Khoảng cách từ ga 0 đến ga 2 là bao nhiêu?” sẽ nhận được giá trị 5.

Nhiệm vụ

Bạn cần cài đặt hàm findLocation(n, first, location, stype) để xác định số thứ tự khối và loại khối chứa mỗi ga tàu.

• n: số lượng ga tàu.
• first: số thứ tự khối chứa ga 0.
• location: mảng độ dài \(n\); bạn cần gán số thứ tự khối chứa ga \(i\) vào location[i].
• stype: mảng độ dài \(n\); bạn cần gán loại khối chứa ga \(i\) vào stype[i]: 1 cho loại C và 2 cho loại D.

Bạn có thể gọi hàm getDistance(i, j) để xác định vị trí và loại khối của các ga. Hàm trả về khoảng cách từ ga i đến ga j. getDistance(i, i) trả về 0. getDistance(i, j) trả về -1 nếu i hoặc j nằm ngoài phạm vi từ \(0\) đến \(n-1\).

Các subtasks

Trong tất cả các subtasks, số khối \(m\) không lớn hơn \(1\,000\,000\). Một số subtasks giới hạn số lần gọi getDistance; giới hạn tùy thuộc subtask. Chương trình nhận kết quả wrong answer nếu vượt quá giới hạn này.

Chi tiết cài đặt

Bạn phải nộp đúng một tệp có tên rail.c, rail.cpp hoặc rail.pas, cài đặt findLocation theo đặc tả trên và chữ ký dưới đây. Với C/C++, bạn phải nạp tệp tiêu đề rail.h.

C/C++:

void findLocation(int n, int first, int location[], int stype[]);

Pascal:

procedure findLocation(n, first : longint; var location,
stype : array of longint);

Hàm getDistance có chữ ký như sau.

C/C++:

int getDistance(int i, int j);

Pascal:

function getDistance(i, j: longint): longint;

Trình chấm mẫu

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

• Dòng 1: số thứ tự subtask.
• Dòng 2: n.
• Dòng \(3+i\), với \(0 \le i \le n-1\): stype[i] (1 cho loại C, 2 cho loại D), rồi location[i].

Khi findLocation trả về, trình chấm mẫu in Correct nếu toàn bộ location[0] ... location[n-1] và stype[0] ... stype[n-1] do chương trình tính được khớp với dữ liệu vào; nếu không khớp, nó in Incorrect.

Jian-Jia đang xây một bức tường bằng cách xếp các viên gạch cùng kích thước. Bức tường gồm \(n\) cột gạch, được đánh số từ \(0\) đến \(n-1\) từ trái sang phải. Các cột có thể cao khác nhau. Độ cao của một cột là số viên gạch trong cột đó.

Ban đầu, tất cả các cột đều không có gạch. Sau đó, Jian-Jia thực hiện \(k\) giai đoạn thêm hoặc bớt gạch. Quá trình xây dựng kết thúc khi hoàn thành cả \(k\) giai đoạn. Trong mỗi giai đoạn, Jian-Jia được cho một dãy cột liên tiếp và một độ cao \(h\), rồi thực hiện như sau:

• Trong giai đoạn thêm, với mỗi cột thuộc dãy đã cho có ít hơn \(h\) viên gạch, Jian-Jia thêm gạch để cột có đúng \(h\) viên. Các cột có từ \(h\) viên trở lên không thay đổi.
• Trong giai đoạn bớt, với mỗi cột thuộc dãy đã cho có nhiều hơn \(h\) viên gạch, Jian-Jia bớt gạch để cột có đúng \(h\) viên. Các cột có từ \(h\) viên trở xuống không thay đổi.

Nhiệm vụ của bạn là xác định hình dạng cuối cùng của bức tường.

Ví dụ

Giả sử có 10 cột gạch và 6 giai đoạn xây dựng. Mọi dãy cột trong bảng dưới đây đều bao gồm cả hai đầu mút.

Giai đoạn  Kiểu  Dãy cột        Độ cao
0          thêm  từ cột 1 đến 8  4
1          bớt   từ cột 4 đến 9  1
2          bớt   từ cột 3 đến 6  5
3          thêm  từ cột 0 đến 5  3
4          thêm  cột 2           5
5          bớt   từ cột 6 đến 7  0

Do ban đầu tất cả các cột đều rỗng, sau giai đoạn 0, mỗi cột từ 1 đến 8 có 4 viên gạch; các cột 0 và 9 vẫn rỗng. Trong giai đoạn 1, gạch được bớt khỏi các cột từ 4 đến 8 cho đến khi mỗi cột còn đúng 1 viên; cột 9 vẫn rỗng. Các cột từ 0 đến 3 nằm ngoài dãy đã cho nên không đổi. Giai đoạn 2 không làm thay đổi gì vì các cột từ 3 đến 6 không có nhiều hơn 5 viên gạch. Sau giai đoạn 3, số gạch trong các cột 0, 4 và 5 tăng lên thành 3. Sau giai đoạn 4, cột 2 có 5 viên gạch. Giai đoạn 5 loại bỏ tất cả gạch ở các cột 6 và 7.

Các hình dưới đây lần lượt mô tả bức tường sau từng giai đoạn.

Sau giai đoạn 0:

Sau giai đoạn 1:

Sau giai đoạn 2 (không thay đổi):

Sau giai đoạn 3:

Sau giai đoạn 4:

Sau giai đoạn 5:

Nhiệm vụ

Cho mô tả của \(k\) giai đoạn, hãy tính số viên gạch trong mỗi cột sau khi hoàn thành tất cả các giai đoạn. Bạn cần cài đặt hàm buildWall(n, k, op, left, right, height, finalHeight).

• n: số cột của bức tường.
• k: số giai đoạn.
• op: mảng độ dài \(k\); op[i] là kiểu của giai đoạn \(i\): 1 là thêm, 2 là bớt, với \(0 \le i \le k-1\).
• left, right: hai mảng độ dài \(k\); dãy cột của giai đoạn \(i\) bắt đầu tại left[i] và kết thúc tại right[i], bao gồm cả hai đầu mút, với \(0 \le i \le k-1\). Luôn có left[i] \(\le\) right[i].
• height: mảng độ dài \(k\); height[i] là thông số độ cao của giai đoạn \(i\), với \(0 \le i \le k-1\).
• finalHeight: mảng độ dài \(n\); bạn phải gán số viên gạch cuối cùng trong cột \(i\) vào finalHeight[i], với \(0 \le i \le n-1\).

Các subtasks

Trong mọi subtask, thông số độ cao ở mọi giai đoạn là số nguyên không âm không lớn hơn \(100\,000\).

Chi tiết cài đặt

Bạn phải nộp đúng một tệp có tên wall.c, wall.cpp hoặc wall.pas, cài đặt chương trình con theo đặc tả trên và chữ ký dưới đây. Với C/C++, bạn phải nạp tệp tiêu đề wall.h.

C/C++:

void buildWall(int n, int k, int op[], int left[], int right[],
int height[], int finalHeight[]);

Pascal:

procedure buildWall(n, k : longint; op, left, right, height :
array of longint; var finalHeight : array of longint);

Trình chấm mẫu

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

• Dòng 1: n, k.
• Dòng \(2+i\), với \(0 \le i \le k-1\): op[i], left[i], right[i], height[i].

Jian-Jia là một cậu bé yêu thích các trò chơi. Khi được hỏi, cậu thích chơi một trò chơi hơn là trả lời trực tiếp. Jian-Jia gặp cô bạn Mei-Yu và kể về mạng lưới chuyến bay ở Đài Loan. Đài Loan có \(n\) thành phố, được đánh số \(0, \ldots, n-1\); một số thành phố được nối với nhau bởi các chuyến bay. Mỗi chuyến bay nối hai thành phố và có thể đi theo cả hai chiều.

Mei-Yu hỏi liệu có thể đi giữa hai thành phố bất kỳ bằng máy bay, trực tiếp hoặc gián tiếp, hay không. Jian-Jia không muốn tiết lộ câu trả lời nên đề nghị chơi một trò chơi. Mei-Yu có thể đặt câu hỏi dạng “Hai thành phố \(x\) và \(y\) có chuyến bay trực tiếp nối với nhau không?”, và Jian-Jia sẽ trả lời ngay lập tức. Mei-Yu hỏi về mỗi cặp thành phố đúng một lần, với tổng số câu hỏi là

Mei-Yu thắng nếu sau khi nhận câu trả lời cho \(i\) câu hỏi đầu tiên, với một giá trị \(i < r\), cô có thể suy ra mạng có liên thông hay không, tức là có thể đi giữa mọi cặp thành phố bằng các chuyến bay, trực tiếp hoặc gián tiếp, hay không. Ngược lại, nếu cô cần hỏi đủ cả \(r\) câu, Jian-Jia thắng.

Để trò chơi thú vị hơn đối với Jian-Jia, hai bạn thỏa thuận rằng cậu có thể bỏ qua mạng lưới chuyến bay thực tế của Đài Loan và tự tạo ra mạng theo diễn biến trò chơi, lựa chọn câu trả lời dựa trên những câu hỏi trước đó của Mei-Yu. Nhiệm vụ của bạn là giúp Jian-Jia thắng bằng cách quyết định cậu nên trả lời các câu hỏi như thế nào.

Ví dụ

Ba ví dụ dưới đây minh họa luật chơi. Mỗi ví dụ có \(n=4\) thành phố và \(r=6\) lượt hỏi đáp. Trong các bảng, yes nghĩa là có chuyến bay trực tiếp, còn no nghĩa là không có.

Trong ví dụ thứ nhất, Jian-Jia thua: sau lượt 4, Mei-Yu biết chắc có thể đi giữa hai thành phố bất kỳ bằng máy bay, bất kể Jian-Jia trả lời câu 5 và câu 6 ra sao.

Lượt   Câu hỏi   Trả lời
1      0, 1      yes
2      3, 0      yes
3      1, 2      no
4      0, 2      yes
-----  --------  ------
5      3, 1      no
6      2, 3      no

Trong ví dụ thứ hai, sau lượt 3, Mei-Yu có thể chứng minh rằng không thể đi giữa hai thành phố 0 và 1 bằng máy bay, bất kể Jian-Jia trả lời câu 4, 5 và 6 ra sao. Vì vậy, Jian-Jia lại thua.

Lượt   Câu hỏi   Trả lời
1      0, 3      no
2      2, 0      no
3      0, 1      no
-----  --------  ------
4      1, 2      yes
5      1, 3      yes
6      2, 3      yes

Trong ví dụ cuối, Mei-Yu không thể xác định liệu có thể đi giữa hai thành phố bất kỳ bằng máy bay hay không cho đến khi cả sáu câu hỏi đều được trả lời, nên Jian-Jia thắng. Cụ thể, vì Jian-Jia trả lời yes cho câu cuối trong bảng dưới đây nên có thể đi giữa mọi cặp thành phố. Nếu cậu trả lời no cho câu cuối thì điều đó không thể thực hiện được.

Lượt   Câu hỏi   Trả lời
1      0, 3      no
2      1, 0      yes
3      0, 2      no
4      3, 1      yes
5      1, 2      no
6      2, 3      yes

Nhiệm vụ

Hãy viết chương trình giúp Jian-Jia thắng trò chơi. Cả Mei-Yu lẫn Jian-Jia đều không biết chiến lược của người kia. Mei-Yu có thể hỏi các cặp thành phố theo thứ tự bất kỳ; Jian-Jia phải trả lời ngay lập tức và không biết trước các câu hỏi tiếp theo. Bạn cần cài đặt hai hàm:

• initialize(n): được gọi đầu tiên; n là số thành phố.
• hasEdge(u, v): sau đó được gọi \(r=n(n-1)/2\) lần, tương ứng với các câu hỏi của Mei-Yu theo đúng thứ tự cô hỏi. Bạn phải trả lời có chuyến bay trực tiếp giữa hai thành phố \(u\) và \(v\) hay không. Trả về 1 nếu có, 0 nếu không.

Các subtasks

Mỗi subtask gồm nhiều ván chơi. Bạn chỉ được điểm của một subtask nếu chương trình giúp Jian-Jia thắng tất cả các ván của subtask đó.

Chi tiết cài đặt

Bạn phải nộp đúng một tệp có tên game.c, game.cpp hoặc game.pas, cài đặt các chương trình con theo đặc tả trên và chữ ký dưới đây.

C/C++:

void initialize(int n);
int hasEdge(int u, int v);

Pascal:

procedure initialize(n: longint);
function hasEdge(u, v: longint): longint;

Trình chấm mẫu

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

• Dòng 1: n.
• \(r\) dòng tiếp theo: mỗi dòng chứa hai số nguyên u và v, mô tả một câu hỏi về hai thành phố \(u\) và \(v\).