JOI 2013 Final Camp - Ngày 1

Thành phố JOI có hệ thống giao thông công cộng phát triển. Các đường dành riêng cho xe buýt tạo thành một lưới: có \(W\) đường chạy theo hướng bắc–nam và \(H\) đường chạy theo hướng đông–tây, các đường liên tiếp cùng hướng cách nhau \(1\) km. Mỗi giao điểm là một trạm xe buýt. Tất cả xe buýt chạy theo chiều kim đồng hồ trên một tuyến hình chữ nhật, với tốc độ không đổi \(1\) km mỗi phút.

JOI định đi xem một trận cricket nhưng đã ngủ quên. Cậu muốn đến sân thi đấu càng sớm càng tốt để xem được nhiều nhất có thể. Cậu đã biết tuyến đường và vị trí hiện tại của từng xe buýt.

Đánh số các đường bắc–nam từ tây sang đông và các đường đông–tây từ bắc xuống nam. Giao điểm của đường thứ \(x\) và đường thứ \(y\) có tọa độ \((x,y)\). Ban đầu JOI ở \((S_X,S_Y)\), còn sân thi đấu ở \((G_X,G_Y)\).

JOI chỉ được di chuyển bằng xe buýt. Việc chuyển xe cần thời gian: nếu xuống một xe tại thời điểm \(t\), cậu không thể lên ngay một xe khác đang ở cùng giao điểm tại thời điểm đó; cậu chỉ có thể lên xe đến trạm từ thời điểm \(t+1\) trở đi. Bảo đảm có thể đến sân thi đấu chỉ bằng xe buýt.

Yêu cầu

Hãy tính thời gian ít nhất, tính bằng phút kể từ hiện tại, để JOI đến sân thi đấu bằng cách đi và chuyển các xe buýt.

Dữ liệu vào

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

• Dòng đầu tiên chứa sáu số nguyên \(W,H,S_X,S_Y,G_X,G_Y\).
• Dòng thứ hai chứa số nguyên \(N\), là số xe buýt.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa năm số nguyên \(X1_i,Y1_i,X2_i,Y2_i,T_i\). Tuyến của xe thứ \(i\) có góc tây bắc tại \((X1_i,Y1_i)\) và góc đông nam tại \((X2_i,Y2_i)\). Tại thời điểm ban đầu, xe ở vị trí cách góc tây bắc \(T_i\) km khi đi theo chiều kim đồng hồ dọc theo tuyến.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa thời gian ít nhất để JOI đến sân thi đấu.

Ràng buộc

• Giới hạn thời gian: 3 giây.
• Giới hạn bộ nhớ: 256 MB.
• \(2\le W,H\le1000\).
• \(1\le N\le1000\).
• \(1\le S_X,G_X\le W\) và \(1\le S_Y,G_Y\le H\).
• Vị trí ban đầu khác đích đến. Tại thời điểm ban đầu, không có xe buýt nào ở vị trí của JOI.
• \(1\le X1_i<X2_i\le W\) và \(1\le Y1_i\le Y2_i\le H\).
• \(0\le T_i<2(X2_i-X1_i+Y2_i-Y1_i)\).
• Bảo đảm JOI có thể đến đích chỉ bằng xe buýt.

Phân nhóm

Mỗi nhóm gồm một hoặc nhiều bộ dữ liệu. Chỉ nhận được điểm của một nhóm khi chương trình trả lời đúng tất cả bộ dữ liệu trong nhóm.

• Nhóm 1 (30 điểm): \(W,H,N\le30\).
• Nhóm 2 (50 điểm): \(W,H,N\le300\).
• Nhóm 3 (20 điểm): Không có ràng buộc bổ sung.

10 10 1 3 10 1
3
1 3 5 6 4
5 5 7 10 1
7 1 10 5 9

50

Ban đầu JOI phải chờ xe số \(1\). Cậu lên xe này sau \(10\) phút; đến phút thứ \(11\), cậu đang ở \((2,3)\). Cậu xuống xe số \(1\) ở \((5,5)\) vào phút thứ \(16\). Đến phút thứ \(19\), cậu vẫn chờ ở trạm này trong khi xe số \(2\) ở \((7,9)\). Cậu lên xe số \(2\) tại \((5,5)\) vào phút thứ \(27\).

Sau đó, JOI xuống xe số \(2\) ở \((7,5)\) vào phút thứ \(29\). Đúng lúc này xe số \(3\) cũng ở cùng giao điểm, nhưng cậu không thể lên xe đó ngay vì việc chuyển xe cần \(1\) phút. Cậu chờ đến phút thứ \(43\) để lên xe số \(3\). Vào phút thứ \(49\), cậu ở \((9,1)\) và đến sân thi đấu sau đó \(1\) phút. Không có cách đến sớm hơn, nên kết quả là \(50\).

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

6

JOI rất thích sưu tầm ảnh và đã lưu được rất nhiều ảnh. Gần đây, ổ cứng của cậu sắp hết chỗ. Vì không có tiền mua ổ cứng mới và không muốn xóa ảnh, cậu quyết định nén chúng.

Mỗi ảnh là một bảng vuông có \(2^N\) hàng và \(2^N\) cột, gồm tổng cộng \(2^N\times2^N\) điểm ảnh. Mỗi điểm ảnh có màu trắng hoặc đen. JOI nén ảnh theo quy tắc sau:

• Nếu tất cả điểm ảnh có cùng màu, chỉ ghi lại màu đó. Kích thước dữ liệu sau khi nén là \(1\).
• Nếu không, chia ảnh thành bốn ảnh vuông bằng nhau bằng cách cắt ở chính giữa theo cả chiều ngang lẫn chiều dọc. Với ảnh có kích thước \(2^k\times2^k\), mỗi ảnh nhỏ có kích thước \(2^{k-1}\times2^{k-1}\). Nén từng ảnh nhỏ theo cùng quy tắc. Kích thước dữ liệu sau khi nén bằng tổng kích thước nén của bốn ảnh nhỏ cộng thêm \(1\).

Để thử phương pháp này, JOI bắt đầu với một ảnh hoàn toàn trắng rồi thực hiện lần lượt \(Q\) thao tác. Thao tác thứ \(i\) được mô tả bởi hai số \(T_i,X_i\):

• Nếu \(T_i=0\), đảo màu tất cả \(2^N\) điểm ảnh trên hàng thứ \(X_i\) tính từ trên xuống.
• Nếu \(T_i=1\), đảo màu tất cả \(2^N\) điểm ảnh trên cột thứ \(X_i\) tính từ trái sang.

Đảo màu nghĩa là đổi trắng thành đen và đen thành trắng. Cụ thể, gọi \((a,b)\) là điểm ảnh ở hàng \(a\), cột \(b\): khi \(T_i=0\), đảo màu các điểm \((X_i,b)\) với \(1\le b\le2^N\); khi \(T_i=1\), đảo màu các điểm \((a,X_i)\) với \(1\le a\le2^N\). Các thao tác được thực hiện liên tiếp trên ảnh hiện tại.

Sau mỗi thao tác, JOI muốn biết kích thước của ảnh khi nén bằng phương pháp trên. Cậu cần tính nhanh để thực hiện được nhiều thao tác thử nghiệm.

Yêu cầu

Cho \(N\), \(Q\) và mô tả các thao tác, hãy tính kích thước dữ liệu sau khi nén ảnh ngay sau mỗi thao tác.

Dữ liệu vào

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

• Dòng đầu tiên chứa hai số nguyên \(N,Q\).
• Trong \(Q\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(T_i,X_i\), mô tả thao tác thứ \(i\).

Dữ liệu ra

Ghi ra đầu ra chuẩn \(Q\) dòng. Dòng thứ \(i\) chứa một số nguyên là kích thước dữ liệu sau khi nén ảnh ngay sau thao tác thứ \(i\).

Ràng buộc

• Giới hạn thời gian: 5 giây.
• Giới hạn bộ nhớ: 256 MB.
• \(1\le N\le20\).
• \(1\le Q\le2000000\).
• \(T_i\in\{0,1\}\) và \(1\le X_i\le2^N\).

Phân nhóm

Mỗi nhóm gồm một hoặc nhiều bộ dữ liệu. Chỉ nhận được điểm của một nhóm khi chương trình trả lời đúng tất cả bộ dữ liệu trong nhóm.

• Nhóm 1 (10 điểm): \(N\le6\), \(Q\le128\).
• Nhóm 2 (20 điểm): \(N\le10\), \(Q\le2048\).
• Nhóm 3 (70 điểm): Không có ràng buộc bổ sung.

2 3
0 1
1 2
0 3

13
17
21

Ảnh có kích thước \(4\times4\). Quy ước 0 là trắng và 1 là đen, trạng thái các hàng qua ba thao tác như sau:

Kích thước nén sau các thao tác lần lượt là \(13\), \(17\) và \(21\).

Đất nước JOI nằm trên một mặt phẳng và có \(N\) ngôi làng, đánh số từ \(1\) đến \(N\). Làng \(i\) được biểu diễn bởi điểm \((i,0)\). Để đề phòng sự cố, đất nước dự định xây dựng hai hệ thống đường truyền thông tin, gọi là hệ thống \(1\) và hệ thống \(2\).

Hệ thống \(k\) có \(M_k\) bộ tập trung, đánh số từ \(1\) đến \(M_k\), và \(N+M_k-1\) đường truyền. Bộ tập trung thứ \(j\) của hệ thống \(k\) nằm tại \((X_{kj},Y_{kj})\). Mỗi đường truyền của hệ thống \(k\) nối một làng với một bộ tập trung của hệ thống đó, hoặc nối hai bộ tập trung của hệ thống đó. Đường truyền là đoạn thẳng nối hai đầu mút. Hai đường truyền bất kỳ chỉ có thể có điểm chung tại đầu mút chung của chúng.

Các bộ tập trung của hệ thống \(1\) có tung độ dương, còn các bộ tập trung của hệ thống \(2\) có tung độ âm. Hai địa điểm liên lạc được với nhau nếu có thể đi từ địa điểm này đến địa điểm kia bằng cách đi dọc các đường truyền liên tiếp. Khi chỉ xét riêng từng hệ thống, mọi làng và mọi bộ tập trung của hệ thống đó đều liên lạc được với nhau.

Người ta muốn đánh giá khả năng duy trì liên lạc khi bị tấn công. Một cuộc tấn công được mô tả bởi hai số \(A,B\) với \(A\ge0\) và \(B\le0\): tất cả bộ tập trung có tung độ lớn hơn \(A\) hoặc nhỏ hơn \(B\) bị phá hủy. Không thể truyền thông tin qua một bộ tập trung đã bị phá hủy.

Yêu cầu

Cho thông tin các làng, hai hệ thống và \(Q\) truy vấn. Truy vấn thứ \(q\) cho số nguyên \(A_q\). Hãy tìm số nguyên \(B_q\le0\) lớn nhất sao cho, sau khi phá hủy mọi bộ tập trung có tung độ lớn hơn \(A_q\) và mọi bộ tập trung có tung độ nhỏ hơn \(B_q\), tất cả các làng vẫn liên lạc được với nhau bằng các đường truyền còn sử dụng được của hai hệ thống.

Dữ liệu vào

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

• Dòng đầu tiên chứa bốn số nguyên \(N,M_1,M_2,Q\).
• Tiếp theo là thông tin hệ thống \(1\): trước hết là \(M_1\) dòng tọa độ, rồi \(N+M_1-1\) dòng mô tả đường truyền.
• Tiếp theo là thông tin hệ thống \(2\): trước hết là \(M_2\) dòng tọa độ, rồi \(N+M_2-1\) dòng mô tả đường truyền.
• Cuối cùng là \(Q\) dòng, dòng thứ \(q\) chứa số nguyên \(A_q\).

Đối với hệ thống \(k\), dòng tọa độ thứ \(j\) chứa hai số nguyên \(X_{kj},Y_{kj}\). Dòng mô tả đường truyền thứ \(i\) chứa ba số nguyên \(T_{ki},C_{ki},D_{ki}\), trong đó:

• Nếu \(T_{ki}=1\), đường truyền nối làng \(C_{ki}\) với bộ tập trung \(D_{ki}\) của hệ thống \(k\); \(1\le C_{ki}\le N\) và \(1\le D_{ki}\le M_k\).
• Nếu \(T_{ki}=2\), đường truyền nối hai bộ tập trung \(C_{ki}\) và \(D_{ki}\) của hệ thống \(k\); \(1\le C_{ki},D_{ki}\le M_k\) và \(C_{ki}\ne D_{ki}\).

Dữ liệu ra

Ghi ra đầu ra chuẩn \(Q\) dòng. Dòng thứ \(q\) chứa số nguyên \(B_q\), là đáp án của truy vấn thứ \(q\).

Nếu đáp án bằng \(0\), phải in 0, không được in -0.

Ràng buộc

• Giới hạn thời gian: 2 giây.
• Giới hạn bộ nhớ: 256 MB.
• \(1\le N,M_1,M_2\le100000\).
• \(-10^9\le X_{1j},X_{2j}\le10^9\) với các chỉ số tương ứng hợp lệ.
• \(1\le Y_{1j}\le10^9\) với \(1\le j\le M_1\).
• \(-10^9\le Y_{2j}\le-1\) với \(1\le j\le M_2\).
• Trong cùng một hệ thống, không có hai bộ tập trung trùng tọa độ: nếu \(i\ne j\) thì \(X_{ki}\ne X_{kj}\) hoặc \(Y_{ki}\ne Y_{kj}\).
• \(1\le Q\le100000\) và \(0\le A_q\le10^9\).
• \(T_{ki}\in\{1,2\}\).
• Hai đường truyền bất kỳ chỉ có thể có điểm chung tại đầu mút chung.
• Khi chỉ xét riêng từng hệ thống, mọi làng và mọi bộ tập trung của hệ thống đó đều liên lạc được với nhau.

Phân nhóm

Mỗi nhóm gồm một hoặc nhiều bộ dữ liệu. Chỉ nhận được điểm của một nhóm khi chương trình trả lời đúng tất cả bộ dữ liệu trong nhóm.

• Nhóm 1 (20 điểm): \(N,M_1,M_2,Q\le1000\).
• Nhóm 2 (80 điểm): Không có ràng buộc bổ sung.

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

-2

Với \(A_1=2\), bộ tập trung số \(3\) của hệ thống \(1\) bị phá hủy. Chọn \(B_1=-2\) sẽ phá hủy thêm bộ tập trung số \(3\) của hệ thống \(2\), nhưng các làng vẫn liên lạc được với nhau. Nếu tăng \(B_1\) lên \(-1\), bộ tập trung số \(2\) của hệ thống \(2\) cũng bị phá hủy và không còn liên lạc được giữa nhóm làng \(1,2\) với nhóm làng \(3,4\).

6 4 5 4
2 1
4 1
3 3
5 2
1 1 1
1 2 1
1 3 2
1 4 2
2 2 4
1 5 4
1 6 4
2 1 3
2 4 3
3 -3
5 -1
2 -2
2 -1
4 -2
1 2 4
1 3 4
1 1 4
2 1 3
1 5 2
1 6 2
1 4 5
2 2 5
1 3 1
2 5 1
3
1
2
0

0
-2
-1
-3

Bốn truy vấn với \(A_q\) lần lượt là \(3,1,2,0\) có các giá trị \(B_q\) lớn nhất tương ứng là \(0,-2,-1,-3\).

Chủ tịch K đang thiết kế ba tấm áp phích để cổ vũ đội tuyển Nhật Bản tham dự Olympic Tin học Quốc tế. Mỗi tấm mang một trong ba chữ J, O, I. Sau khi hoàn thành hai tấm mang chữ J và I, ông quyết định thiết kế chữ O trên nền bầu trời sao của Australia.

Tấm áp phích là một hình chữ nhật có chiều rộng \(W\), chiều cao \(H\), góc dưới bên trái tại \((0,0)\) và góc trên bên phải tại \((W,H)\). Trên đó có \(N\) ngôi sao. Ngôi sao \(S_i\) nằm tại \((X_i,Y_i)\); không có hai ngôi sao trùng tọa độ.

Ông chọn bốn ngôi sao khác nhau và lần lượt gán vai trò \(A,B,C,D\). Gọi \(O_1\) là đường tròn tâm \(A\) đi qua \(B\), và \(O_2\) là đường tròn tâm \(C\) đi qua \(D\). Bộ bốn ngôi sao này là một phương án thiết kế hợp lệ nếu thỏa mãn đồng thời:

• \(O_1\) chứa hoàn toàn \(O_2\) ở bên trong: mọi điểm nằm trong hoặc trên \(O_2\) đều phải nằm trong \(O_1\), không được nằm trên \(O_1\).
• Cả hai hình tròn đều không vượt ra ngoài áp phích: với mọi điểm \((X,Y)\) nằm trong hoặc trên mỗi đường tròn, phải có \(0\le X\le W\) và \(0\le Y\le H\).

Các vai trò \(A,B,C,D\) được phân biệt khi đếm các cách chọn.

Yêu cầu

Cho kích thước áp phích và tọa độ các ngôi sao, hãy đếm số cách chọn bốn ngôi sao \(A,B,C,D\) tạo thành một phương án thiết kế hợp lệ.

Dữ liệu vào

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

• Dòng đầu tiên chứa ba số nguyên \(N,W,H\), lần lượt là số ngôi sao, chiều rộng và chiều cao của áp phích.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(X_i,Y_i\), là tọa độ ngôi sao \(S_i\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên là số phương án thiết kế hợp lệ.

Ràng buộc

• Giới hạn thời gian: 1 giây.
• Giới hạn bộ nhớ: 256 MB.
• \(4\le N\le50\).
• \(1\le W,H\le1000\).
• \(0\le X_i\le W\) và \(0\le Y_i\le H\).
• Không có hai ngôi sao trùng tọa độ.

Phân nhóm

Mỗi nhóm gồm một hoặc nhiều bộ dữ liệu. Chỉ nhận được điểm của một nhóm khi chương trình trả lời đúng tất cả bộ dữ liệu trong nhóm.

• Nhóm 1 (80 điểm): Với mọi cách chọn bốn ngôi sao khác nhau \(A,B,C,D\), hai đường tròn \(O_1,O_2\) không tiếp xúc nhau.
• Nhóm 2 (20 điểm): Không có ràng buộc bổ sung.

7 20 15
9 5
13 9
15 13
7 4
6 8
14 7
16 7

3

Có đúng ba bộ \((A,B,C,D)\) hợp lệ: \((S_2,S_1,S_6,S_7)\), \((S_2,S_1,S_7,S_6)\) và \((S_2,S_3,S_6,S_7)\). Trong phương án cuối, hai đường tròn \(O_1\) và \(O_2\) cũng không tiếp xúc nhau: bán kính ngoài là \(\sqrt{20}\), còn khoảng cách giữa hai tâm cộng bán kính trong là \(\sqrt{5}+2<\sqrt{20}\).

15 20 30
11 8
14 25
3 20
1 27
2 16
12 8
0 4
3 10
12 11
5 9
16 3
2 13
4 24
18 3
12 28

12