JOI 2016 Final Camp - Ngày 4

JOI thích trượt băng trên một sân băng rộng lớn giữa thiên nhiên.

Sân băng được biểu diễn bằng một hình chữ nhật gồm \(R\) hàng theo hướng bắc–nam và \(C\) cột theo hướng đông–tây. Gọi ô ở hàng thứ \(r\) tính từ phía bắc, cột thứ \(c\) tính từ phía tây là ô \((r,c)\). Mỗi ô hoặc có thể đi qua, hoặc chứa một khối băng và không thể đi qua. Tất cả các ô trên biên sân đều chứa khối băng, nên JOI không thể trượt ra ngoài sân. Cụ thể, các ô \((i,1)\), \((i,C)\) với \(1 \le i \le R\) và các ô \((1,j)\), \((R,j)\) với \(1 \le j \le C\) đều chứa khối băng.

JOI trượt băng không giỏi lắm. Mỗi lần di chuyển, cậu đạp vào ô đang đứng để trượt theo một trong bốn hướng đông, tây, nam, bắc và chỉ dừng lại ở ô ngay trước khối băng đầu tiên gặp phải. Quá trình từ lúc đạp vào mặt sân đến lúc dừng lại được tính là một lần di chuyển. Nếu ô liền kề theo một hướng chứa khối băng, cậu không thể di chuyển theo hướng đó.

Một hôm, khi đang trượt băng, JOI phát hiện rằng mỗi khi cậu đạp vào mặt sân, một khối băng sẽ mọc lên tại chính ô đó. Các ô cậu trượt qua, ngoại trừ ô đạp chân để bắt đầu di chuyển, không xuất hiện khối băng. Tiếp tục trượt trong tình trạng này rất nguy hiểm, nên JOI muốn thoát khỏi sân băng càng nhanh càng tốt.

Hiện tại JOI đang ở ô \((r_1,c_1)\). Để thoát khỏi sân băng, cậu phải dừng lại tại ô lối ra \((r_2,c_2)\). Chỉ trượt ngang qua ô lối ra trong một lần di chuyển là chưa đủ để thoát. Tùy trạng thái sân và vị trí ban đầu, có thể không có cách nào để cậu dừng tại lối ra.

Yêu cầu

Cho vị trí các khối băng, vị trí hiện tại của JOI và vị trí lối ra. Hãy xác định JOI có thể bắt đầu từ vị trí hiện tại và dừng tại lối ra hay không; nếu có, tìm số lần di chuyển ít nhất cần thực hiện.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa hai số nguyên \(R,C\), cách nhau bởi một dấu cách, là kích thước sân băng.
• \(R\) dòng tiếp theo, mỗi dòng chứa một xâu gồm \(C\) ký tự . hoặc #. Ký tự thứ \(c\) trên dòng thứ \(r\) trong số này mô tả trạng thái ban đầu của ô \((r,c)\): . là ô có thể đi qua, còn # là ô chứa khối băng và không thể đi qua.
• Dòng tiếp theo chứa hai số nguyên \(r_1,c_1\), cách nhau bởi một dấu cách, là vị trí hiện tại của JOI.
• Dòng tiếp theo chứa hai số nguyên \(r_2,c_2\), cách nhau bởi một dấu cách, là vị trí lối ra.

Dữ liệu ra

In ra đầu ra chuẩn một số nguyên trên một dòng: số lần di chuyển ít nhất để JOI dừng tại ô lối ra. Nếu không thể dừng tại ô lối ra bằng bất kỳ cách di chuyển nào, in -1.

Giới hạn

• \(3 \le R \le 1\,000\).
• \(3 \le C \le 1\,000\).
• \(1 \le r_1 \le R\).
• \(1 \le c_1 \le C\).
• \(1 \le r_2 \le R\).
• \(1 \le c_2 \le C\).
• Tất cả các ô trên biên đều chứa khối băng: \((i,1)\), \((i,C)\) với \(1 \le i \le R\) và \((1,j)\), \((R,j)\) với \(1 \le j \le C\).
• Hai ô \((r_1,c_1)\) và \((r_2,c_2)\) không chứa khối băng.

Chấm điểm

1. 13 điểm: \(R \le 10\), \(C \le 10\). Nếu có thể dừng tại lối ra, số lần di chuyển ít nhất không vượt quá \(10\).
2. 65 điểm: \(R \le 200\), \(C \le 200\).
3. 22 điểm: Không có giới hạn bổ sung.

Ví dụ

5 5
#####
#...#
#...#
#...#
#####
2 2
3 3

4

8 6
######
#..#.#
##...#
#....#
#.#..#
#....#
##...#
######
4 3
6 4

5

5 5
#####
#.#.#
#.#.#
#.#.#
#####
2 2
4 4

-1

3 3
###
#.#
###
2 2
2 2

0

Vào mùa đông, nhiều nơi ở Nga có tuyết rơi. Nước Nga có \(N\) thành phố, được đánh số từ \(0\) đến \(N-1\), và \(N-1\) con đường, được đánh số từ \(0\) đến \(N-2\). Đường \(i\) nối hai chiều giữa hai thành phố khác nhau \(A_i\) và \(B_i\), trong đó \(0 \le A_i < B_i \le N-1\). Có thể đi lại giữa bất kỳ hai thành phố khác nhau nào qua một số con đường.

Tình trạng tuyết rơi trên mỗi con đường thay đổi theo ngày. Vào mỗi ngày, một con đường hoặc có tuyết rơi, hoặc không có tuyết rơi; tình trạng này không thay đổi trong ngày.

Anya và Boris làm việc tại cơ quan giao thông của Nga. Anya thuộc bộ phận quản lý thông tin đường sá, còn Boris thuộc bộ phận trả lời câu hỏi của người dân. Người dân muốn biết số con đường có tuyết rơi ít nhất phải đi qua để từ thủ đô, tức thành phố \(0\), đến một thành phố khác. Thông thường, sau khi nhận câu hỏi, Boris trao đổi với Anya rồi trả lời người dân.

Sắp tới, Nga sẽ tổ chức một cuộc thi lập trình thế giới kéo dài \(Q\) ngày. Trong thời gian này, đường truyền dự kiến sẽ bị quá tải, khiến Anya và Boris khó trao đổi trực tiếp. Vì vậy, họ quyết định liên lạc theo cách sau:

• Vào đầu mỗi ngày, Anya nhận thông tin tuyết rơi của ngày đó rồi gửi dữ liệu lên một máy chủ trung gian.
• Khi nhận được câu hỏi của người dân, Boris trao đổi với máy chủ trung gian để tìm câu trả lời.

Việc liên lạc phải tuân theo các giới hạn sau:

• Máy chủ trung gian có dung lượng \(L = 1\,000\) bit. Anya chỉ có thể lưu tối đa \(L\) bit thông tin trên máy chủ.
• Vào đầu mỗi ngày, tất cả dữ liệu trên máy chủ được khởi tạo lại thành \(0\).
• Trong mỗi lần trao đổi với máy chủ, Boris có thể đọc một bit tại vị trí được chỉ định.
• Để trả lời mỗi câu hỏi, Boris chỉ được trao đổi với máy chủ tối đa \(20\) lần.

Bạn là người quen của giám đốc cơ quan giao thông và được nhờ xây dựng chiến lược cho Anya và Boris.

Trong hình, các nhãn tiếng Nhật lần lượt có nghĩa là “Thông tin tuyết rơi” ở phía dưới Anya, “Máy chủ trung gian” và “Dung lượng \(L\) bit” ở giữa, “Tối đa \(20\) bit cho mỗi câu hỏi” trên đường nối tới Boris, và “Người dân” ở phía dưới Boris.

Yêu cầu

Hãy viết chương trình cài đặt chiến lược của Anya và Boris để trả lời đúng các câu hỏi của người dân.

Chi tiết cài đặt

Nộp một tệp mã nguồn C++ include snowy.h được đính kèm theo bài và cài đặt cả bốn hàm dưới đây. Hệ thống chấm biên dịch cùng một mã nguồn cho hai tiến trình riêng biệt: một tiến trình thực hiện vai trò Anya và tiến trình còn lại thực hiện vai trò Boris.

Phía Anya

Hai hàm sau cài đặt chiến lược của Anya.

void InitAnya(int N, int A[], int B[]);

Hàm này được gọi đúng một lần trong mỗi bộ kiểm thử.

• N là số thành phố.
• A[] và B[] đều là mảng có độ dài \(N-1\), mô tả các con đường. Với \(0 \le i \le N-2\), đường \(i\) nối hai chiều giữa thành phố A[i] và B[i], thỏa mãn \(0 \le A[i] < B[i] \le N-1\).

void Anya(int C[]);

Hàm này được gọi \(Q\) lần sau khi InitAnya được gọi. Mỗi lần gọi tương ứng với việc Anya quyết định dãy bit cần lưu lên máy chủ sau khi thông tin tuyết rơi được cập nhật vào đầu ngày.

• C[] là mảng có độ dài \(N-1\), mô tả tình trạng tuyết rơi. Với \(0 \le i \le N-2\), C[i] là \(0\) hoặc \(1\): C[i] = 1 nghĩa là đường \(i\) có tuyết rơi; C[i] = 0 nghĩa là đường đó không có tuyết rơi.

Trong hàm Anya, bạn có thể gọi hàm sau:

void Save(int place, int bit);

Hàm này biểu diễn thao tác Anya lưu một bit lên máy chủ.

• place là vị trí cần ghi, phải là một số nguyên từ \(0\) đến \(L-1\). Nếu nằm ngoài khoảng này, chương trình bị chấm Wrong Answer [1].
• Trong mỗi lần gọi Anya, không được gọi Save hai lần hoặc nhiều hơn với cùng một giá trị place. Nếu ghi cùng vị trí lần thứ hai, chương trình bị chấm Wrong Answer [2].
• bit là giá trị cần ghi, phải là \(0\) hoặc \(1\). Giá trị khác sẽ bị chấm Wrong Answer [3].

Sau khi gọi Save, bit tại vị trí place trên máy chủ có giá trị bit. Nếu một lần gọi Save bị chấm sai, chương trình kết thúc ngay.

Ngay trước mỗi lần gọi Anya, toàn bộ bit trên máy chủ luôn được khởi tạo lại thành \(0\). Vì thế, khi Anya kết thúc, các vị trí không được ghi bằng Save vẫn có giá trị \(0\).

Phía Boris

Hai hàm sau cài đặt chiến lược của Boris.

void InitBoris(int N, int A[], int B[]);

Hàm này được gọi đúng một lần trong mỗi bộ kiểm thử.

• N là số thành phố.
• A[] và B[] đều là mảng có độ dài \(N-1\), mô tả các con đường. Với \(0 \le i \le N-2\), đường \(i\) nối hai chiều giữa thành phố A[i] và B[i], thỏa mãn \(0 \le A[i] < B[i] \le N-1\).

int Boris(int city);

Hàm này được gọi một số lần sau khi InitBoris được gọi. Mỗi lần gọi tương ứng với việc Boris trả lời một câu hỏi của người dân.

• city là một số nguyên từ \(1\) đến \(N-1\), biểu thị câu hỏi: để đi từ thành phố \(0\) đến thành phố city, cần đi qua ít nhất bao nhiêu con đường có tuyết rơi?
• Hàm phải trả về câu trả lời, là một số nguyên từ \(0\) đến \(N-1\). Nếu trả về số nguyên ngoài khoảng này, chương trình bị chấm Wrong Answer [4]. Nếu câu trả lời không đúng, chương trình bị chấm Wrong Answer [7].

Trong hàm Boris, bạn có thể gọi hàm sau:

int Ask(int place);

Hàm này biểu diễn thao tác Boris đọc một bit từ máy chủ.

• place là vị trí cần đọc, phải là một số nguyên từ \(0\) đến \(L-1\). Nếu nằm ngoài khoảng này, chương trình bị chấm Wrong Answer [5].
• Hàm trả về giá trị bit tại vị trí place trên máy chủ, là \(0\) hoặc \(1\).
• Trong mỗi lần gọi Boris, chỉ được gọi Ask tối đa \(20\) lần. Nếu gọi quá \(20\) lần, chương trình bị chấm Wrong Answer [6].

Nếu một lần gọi Ask bị chấm sai, chương trình kết thúc ngay.

Quy trình chấm

Chương trình được chấm theo trình tự sau. Nếu bị chấm sai ở bất kỳ thời điểm nào, chương trình kết thúc ngay.

1. Gọi InitAnya một lần, rồi gọi InitBoris một lần, theo đúng thứ tự đó, để cung cấp thông tin các con đường.
2. Với từng \(i = 1,\ldots,Q\), lần lượt thực hiện hai bước sau:
3. Gọi Anya đúng một lần. Lần gọi này tương ứng với việc Anya quyết định dãy bit cần lưu lên máy chủ sau khi thông tin tuyết rơi được cập nhật vào đầu ngày.
4. Gọi Boris \(D_i\) lần, trong đó \(D_i\) là số câu hỏi của người dân trong ngày thứ \(i\). Lần gọi thứ \(j\), với \(1 \le j \le D_i\), nhận đối số \(R_{ij}\), thỏa mãn \(1 \le R_{ij} \le N-1\). Nếu giá trị trả về không bằng số con đường có tuyết rơi ít nhất phải đi qua để từ thành phố \(0\) đến thành phố \(R_{ij}\), chương trình bị chấm sai.
5. Nếu không lần nào bị chấm sai, chương trình được chấm đúng.

Các lưu ý quan trọng

• Thời gian chạy và bộ nhớ sử dụng được đo trong các bước 1 và 2 của quy trình chấm. Nếu chương trình được chấm đúng, trong bước 2, Anya được gọi tổng cộng \(Q\) lần và Boris được gọi tổng cộng \(D_1+\cdots+D_Q\) lần.
• Anya và Boris không được biết các giá trị \(D_1,\ldots,D_Q\).
• Boris không được cung cấp thông tin cho biết thời điểm Anya cập nhật dữ liệu trên máy chủ.
• Bạn có thể cài đặt các hàm nội bộ và khai báo biến toàn cục. Cùng một mã nguồn được chạy trong hai tiến trình riêng cho Anya và Boris, vì vậy hai phía không thể chia sẻ biến toàn cục trong lúc chấm.
• Bài nộp không được tương tác với đầu vào chuẩn, đầu ra chuẩn hay bất kỳ tệp nào khác bằng bất cứ cách nào.

Cách nộp bài

Không viết hàm main, không đọc đầu vào chuẩn và không ghi đầu ra chuẩn. Hệ thống chấm cung cấp Save cho tiến trình Anya, cung cấp Ask cho tiến trình Boris, và gọi các hàm theo đúng quy trình ở trên.

Giới hạn

• \(2 \le N \le 500\).
• \(1 \le Q \le 500\).
• \(0 \le A_i < B_i \le N-1\) với \(0 \le i \le N-2\).
• \(1 \le D_j\) với \(1 \le j \le Q\).
• Tổng số câu hỏi thỏa mãn:

• Có thể đi lại giữa bất kỳ hai thành phố khác nhau nào qua một số con đường.

Chấm điểm

1. 15 điểm: \(N \le 20\).
2. 5 điểm: \(N \le 100\).
3. 35 điểm: \(A_i=i\) và \(B_i=i+1\) với mọi \(0 \le i \le N-2\).
4. 45 điểm: Không có giới hạn bổ sung.

Ví dụ giao tiếp

Dưới đây là một ví dụ đầu vào của chương trình chấm mẫu và một trình tự gọi hàm tương ứng.

5
0 1
1 2
1 4
2 3
2
0101 3 2 4 3
1110 1 4

Trình tự gọi hàm

Trong bảng, “không có” nghĩa là hàm không có giá trị trả về. Các thao tác trong một lần gọi được liệt kê theo thứ tự thực hiện.

Lưu ý rằng các lời gọi trong ví dụ này không nhất thiết có ý nghĩa như một chiến lược giải bài.

Các đối số truyền cho InitAnya(...), InitBoris(...) và hai lần gọi Anya(...) lần lượt là:

Vào năm 21XX, lập trình thi đấu đã được công nhận rộng rãi là một môn thể thao trí tuệ và thường xuyên được đưa tin trên truyền hình, báo chí cùng các phương tiện truyền thông khác.

Bạn là phóng viên của báo JOI, phụ trách các bài viết về lập trình thi đấu.

Hôm qua, một cuộc thi lập trình quốc tế với \(N\) thí sinh đã diễn ra. Để viết bài về cuộc thi, bạn được cung cấp những thông tin sau:

• Giống như Olympic Tin học Quốc tế và các cuộc thi tương tự, thí sinh đến từ nhiều quốc gia. Mỗi quốc gia được đánh số từ \(1\) đến \(N\). Một quốc gia có thể có nhiều thí sinh tham dự, và cũng có thể có quốc gia không có thí sinh nào tham dự.
• Thời gian thi là \(5\) giờ.
• Trong suốt cuộc thi, số điểm một thí sinh đã đạt được không bao giờ bị giảm.
• Sau khi cuộc thi bắt đầu được \(2\) giờ, không có hai thí sinh nào bằng điểm. Trên bảng xếp hạng tại thời điểm đó, thí sinh đứng thứ \(i\) đến từ quốc gia \(A_i\) và có \(B_i\) điểm, với \(1 \le i \le N\).
• Khi cuộc thi kết thúc, không có hai thí sinh nào bằng điểm. Trên bảng xếp hạng cuối cùng, thí sinh đứng thứ \(i\) đến từ quốc gia \(C_i\) và có \(D_i\) điểm, với \(1 \le i \le N\).

Tuy nhiên, khi chuẩn bị viết bài, bạn phát hiện chức năng hiển thị quốc gia trên bảng xếp hạng đã gặp lỗi. Thông tin về quốc gia của thí sinh có thể đã bị hiển thị sai. Bạn biết chắc rằng các số điểm được hiển thị đều đúng.

Bạn quyết định sửa ít thông tin nhất có thể để thu được các bảng xếp hạng không mâu thuẫn: quốc gia của cùng một thí sinh không thay đổi trong cuộc thi và điểm của thí sinh không giảm đi. Cụ thể, bạn muốn thay đổi ít vị trí nhất trong \(2N\) giá trị \(A_1,\ldots,A_N,C_1,\ldots,C_N\) sao cho tồn tại một hoán vị \(x_1,x_2,\ldots,x_N\) của \(1,2,\ldots,N\) thỏa mãn:

Bạn cần sửa ít nhất bao nhiêu vị trí trong thông tin được cung cấp?

Yêu cầu

Cho số thí sinh và thông tin bảng xếp hạng sau \(2\) giờ cũng như khi kết thúc cuộc thi. Hãy tìm số vị trí thông tin quốc gia ít nhất cần thay đổi để các bảng xếp hạng không mâu thuẫn.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa số nguyên \(N\), là số thí sinh tham dự.
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(A_i,B_i\) cách nhau bởi một dấu cách: quốc gia được hiển thị và số điểm của thí sinh đứng thứ \(i\) sau khi cuộc thi bắt đầu được \(2\) giờ.
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(C_i,D_i\) cách nhau bởi một dấu cách: quốc gia được hiển thị và số điểm của thí sinh đứng thứ \(i\) khi cuộc thi kết thúc.

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa số vị trí thông tin quốc gia ít nhất cần thay đổi để các bảng xếp hạng không mâu thuẫn.

Giới hạn

• \(2 \le N \le 200\,000\).
• \(1 \le A_i \le N\) với \(1 \le i \le N\).
• \(0 \le B_i \le 1\,000\,000\,000\) với \(1 \le i \le N\).
• \(B_i > B_{i+1}\) với \(1 \le i \le N-1\).
• \(1 \le C_i \le N\) với \(1 \le i \le N\).
• \(0 \le D_i \le 1\,000\,000\,000\) với \(1 \le i \le N\).
• \(D_i > D_{i+1}\) với \(1 \le i \le N-1\).
• Có thể làm cho các bảng xếp hạng không mâu thuẫn bằng cách thay đổi một số giá trị trong \(A_1,\ldots,A_N,C_1,\ldots,C_N\).

Chấm điểm

1. 15 điểm: \(N \le 16\).
2. 15 điểm: \(N \le 50\).
3. 30 điểm: \(N \le 5\,000\).
4. 40 điểm: Không có giới hạn bổ sung.

Ví dụ

3
3 500
2 200
1 100
1 1000
3 700
3 400

1

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

0

6
1 70
4 50
1 30
2 20
1 10
3 0
6 100
2 90
1 80
2 60
4 40
1 10

3