IOI 2007 - Ngày 1

Mirko rất thích những hình vẽ trên đồng ruộng, được tạo nên từ cây cỏ bị ép rạp và được cho là tác phẩm của người ngoài hành tinh. Một đêm hè, cậu quyết định tự tạo một hình như vậy trên đồng cỏ của bà. Là người yêu nước, Mirko chọn phần hình bàn cờ trên quốc huy Croatia: một bàn cờ \(5\times5\) gồm \(13\) ô vuông đỏ và \(12\) ô vuông trắng xen kẽ nhau.

Đồng cỏ là một hình vuông được chia thành \(N\times N\) ô. Ô ở góc dưới bên trái có tọa độ \((1,1)\), còn ô ở góc trên bên phải có tọa độ \((N,N)\).

Mirko chọn một số nguyên lẻ \(M\ge3\). Mỗi ô vuông của bàn cờ chiếm một khối \(M\times M\) ô của đồng cỏ, với các cạnh song song với các cạnh đồng cỏ. Toàn bộ bàn cờ nằm trọn trong đồng cỏ. Cậu chỉ ép rạp cỏ trong các ô vuông đỏ và giữ nguyên tất cả phần cỏ còn lại.

Sau khi Mirko đi ngủ, tác phẩm của cậu thu hút sự chú ý của những người ngoài hành tinh thật sự. Từ tàu vũ trụ phía trên đồng cỏ, họ khảo sát hình vẽ bằng một thiết bị đơn giản: thiết bị chỉ có thể xác định cỏ trong một ô cụ thể có bị ép rạp hay không.

Họ đã tìm được một ô có cỏ bị ép rạp và muốn xác định ô chính giữa hình vẽ để ngắm nhìn tác phẩm. Họ không biết kích thước \(M\) của các ô vuông trên bàn cờ.

Cho kích thước \(N\), tọa độ \((X_0,Y_0)\) của một ô có cỏ bị ép rạp và khả năng tương tác với thiết bị, hãy tìm tọa độ ô chính giữa hình vẽ. Bạn được sử dụng thiết bị không quá \(300\) lần trong mỗi lần chạy trên một bộ dữ liệu.

Tương tác

Đây là bài toán tương tác. Chương trình gửi lệnh qua đầu ra chuẩn và đọc phản hồi của thiết bị từ đầu vào chuẩn.

Khi bắt đầu, đọc ba số nguyên \(N,X_0,Y_0\) trên một dòng, phân cách bởi một dấu cách. \(N\) là kích thước đồng cỏ; \((X_0,Y_0)\) là tọa độ một ô có cỏ bị ép rạp.

Để kiểm tra ô \((X,Y)\), ghi một dòng có dạng examine X Y. Các tọa độ phải thỏa mãn \(1\le X,Y\le N\). Nếu tọa độ nằm ngoài đồng cỏ hoặc chương trình gửi quá \(300\) lệnh examine, chương trình nhận \(0\) điểm cho bộ dữ liệu đó.

Thiết bị trả lời bằng một dòng chứa từ true nếu cỏ trong ô \((X,Y)\) bị ép rạp, hoặc từ false nếu không.

Khi đã tìm được ô chính giữa, ghi một dòng có dạng solution XC YC, trong đó \((X_C,Y_C)\) là tọa độ ô đó. Chương trình sẽ được tự động kết thúc ngay khi xuất lời giải.

Các từ lệnh và phản hồi phải được viết đúng chữ thường như trên. Sau mỗi lần ghi ra đầu ra chuẩn, phải đẩy dữ liệu khỏi bộ đệm (flush) để bộ chấm nhận được lệnh.

Ràng buộc

• \(15\le N\le 2\,000\,000\,000\).
• \(1\le X_0,Y_0\le N\); cỏ tại ô \((X_0,Y_0)\) được bảo đảm bị ép rạp.
• \(M\) là số nguyên lẻ, \(M\ge3\); bàn cờ kích thước \(5M\times5M\) nằm trọn trong đồng cỏ.
• Không quá \(300\) lệnh examine trong mỗi lần chạy trên một bộ dữ liệu.
• Mỗi bộ dữ liệu có một đáp án đúng duy nhất, cố định và không phụ thuộc vào những câu hỏi chương trình đặt ra.

Chấm điểm trên hệ thống

Lưu ý: Cách chia nhóm và tính điểm dưới đây là bản điều chỉnh để luyện tập trên hệ thống, không khẳng định tương đương cách chấm tại IOI gốc.

Mỗi nhóm được chấm độc lập: chỉ nhận điểm của nhóm khi vượt qua tất cả bộ kiểm thử trong nhóm; nếu có bộ kiểm thử không đạt thì nhóm nhận 0 điểm. Tổng điểm tối đa là 100.

Nhãn nhóm là phần số trong tên tệp dữ liệu gốc. Tất cả tệp cùng nhãn, kể cả các hậu tố chữ và pf, đều thuộc nhóm đó.

Các ví dụ trong đề không tính điểm.

Ví dụ

19 7 4
true
false
false
true

examine 11 2
examine 2 5
examine 9 14
examine 18 3
solution 12 9

Nguồn

IOI 2007.

Năm 1964, một trận lũ thảm khốc xảy ra tại Zagreb. Nhiều tòa nhà bị phá hủy hoàn toàn khi nước lũ đập vào các bức tường. Trong bài toán này, bạn được cho một mô hình đơn giản của thành phố trước trận lũ và cần xác định những bức tường còn nguyên sau khi lũ đi qua.

Mô hình gồm \(N\) điểm trên mặt phẳng tọa độ và \(W\) bức tường. Mỗi bức tường nối hai điểm và không đi qua bất kỳ điểm nào khác trong mô hình. Không có hai bức tường nào cắt nhau hoặc chồng lên nhau, nhưng chúng có thể chạm nhau tại các đầu mút. Mỗi bức tường song song với trục hoành hoặc trục tung.

Ban đầu, toàn bộ mặt phẳng đều khô ráo. Tại thời điểm \(0\), nước lập tức tràn ngập miền bên ngoài, tức là phần không gian không bị các bức tường bao kín. Sau đúng một giờ, tất cả những bức tường có một bên là nước và bên còn lại là không khí đồng thời bị phá vỡ do áp lực nước. Nước sau đó tràn vào những vùng mới không còn bị các bức tường đứng vững ngăn cách với bên ngoài.

Lúc này có thể xuất hiện những bức tường mới có một bên là nước, một bên là không khí. Sau một giờ nữa, những bức tường đó cũng bị phá vỡ và nước tiếp tục tràn vào. Quá trình lặp lại cho đến khi toàn bộ khu vực bị ngập.

Các hình dưới minh họa quá trình này. Phần tô màu là vùng ngập nước, còn phần trắng là vùng khô, chứa không khí.

Trạng thái tại thời điểm \(0\).

Trạng thái sau một giờ.

Trạng thái sau hai giờ. Nước đã tràn ngập toàn bộ khu vực và không thể phá vỡ \(4\) bức tường còn lại.

Hãy xác định các bức tường còn đứng vững sau trận lũ.

Dữ liệu vào

• Dòng đầu chứa số nguyên \(N\), là số điểm trên mặt phẳng.
• Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên \(X,Y\), là tọa độ một điểm. Các điểm được đánh số từ \(1\) đến \(N\) theo thứ tự xuất hiện trong dữ liệu vào. Không có hai điểm trùng tọa độ.
• Dòng tiếp theo chứa số nguyên \(W\), là số bức tường.
• Mỗi dòng trong \(W\) dòng tiếp theo chứa hai số nguyên khác nhau \(A,B\), mô tả một bức tường nối điểm \(A\) với điểm \(B\) trước trận lũ. Các bức tường được đánh số từ \(1\) đến \(W\) theo thứ tự xuất hiện trong dữ liệu vào.

Dữ liệu ra

Dòng đầu chứa một số nguyên \(K\), là số bức tường còn đứng vững sau trận lũ.

\(K\) dòng tiếp theo chứa chỉ số của các bức tường đó, mỗi dòng một chỉ số. Có thể xuất các chỉ số theo thứ tự bất kỳ.

Ràng buộc

• \(2\le N\le 100\,000\).
• \(0\le X,Y\le 1\,000\,000\).
• \(1\le W\le 2N\).
• \(1\le A,B\le N\) và \(A\ne B\).
• Các điểm và bức tường thỏa mãn mọi điều kiện hình học đã nêu trong mô tả.

Chấm điểm trên hệ thống

Lưu ý: Cách chia nhóm và tính điểm dưới đây là bản điều chỉnh để luyện tập trên hệ thống, không khẳng định tương đương cách chấm tại IOI gốc.

Mỗi nhóm được chấm độc lập: chỉ nhận điểm của nhóm khi vượt qua tất cả bộ kiểm thử trong nhóm; nếu có bộ kiểm thử không đạt thì nhóm nhận 0 điểm. Tổng điểm tối đa là 100.

Nhãn nhóm là phần số trong tên tệp dữ liệu gốc. Tất cả tệp cùng nhãn, kể cả các hậu tố chữ và pf, đều thuộc nhóm đó.

Các ví dụ trong đề không tính điểm.

Ví dụ

15
1 1
8 1
4 2
7 2
2 3
4 3
6 3
2 5
4 5
6 5
4 6
7 6
1 8
4 8
8 8
17
1 2
2 15
15 14
14 13
13 1
14 11
11 12
12 4
4 3
3 6
6 5
5 8
8 9
9 11
9 10
10 7
7 6

4
6
15
16
17

Nguồn

IOI 2007.

Một chiếc thuyền buồm mới dành cho cướp biển đang được đóng. Thuyền có \(N\) cột buồm, mỗi cột được chia thành các đoạn có độ dài một đơn vị; chiều cao của cột bằng số đoạn của nó. Mỗi cột được gắn một số cánh buồm, mỗi cánh chiếm vừa đúng một đoạn. Có thể đặt các cánh buồm trên một cột vào các đoạn khác nhau tùy ý, nhưng mỗi đoạn chỉ được gắn nhiều nhất một cánh buồm.

Các cách bố trí buồm khác nhau tạo ra lực đẩy khác nhau khi đón gió. Những cánh buồm nằm phía trước các cánh buồm khác ở cùng độ cao nhận được ít gió hơn và tạo ra ít lực đẩy hơn. Với mỗi cánh buồm, định nghĩa độ kém hiệu quả của nó là tổng số cánh buồm nằm phía sau nó và ở cùng độ cao. Hai khái niệm phía trước và phía sau được xác định theo hướng của thuyền: trong hình minh họa, phía trước ở bên trái, phía sau ở bên phải.

Tổng độ kém hiệu quả của một cách bố trí là tổng độ kém hiệu quả của tất cả các cánh buồm.

Thuyền trong hình có \(6\) cột buồm với chiều cao lần lượt là \(3,5,4,2,4,3\), tính từ phía trước (front, bên trái hình) ra phía sau (back, bên phải hình). Cách bố trí này có tổng độ kém hiệu quả bằng \(10\). Số ghi trong mỗi cánh buồm là độ kém hiệu quả của riêng cánh buồm đó.

Cho chiều cao và số cánh buồm của từng cột, hãy tìm tổng độ kém hiệu quả nhỏ nhất có thể.

Dữ liệu vào

Dòng đầu chứa số nguyên \(N\), là số cột buồm trên thuyền.

Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên \(H,K\), lần lượt là chiều cao và số cánh buồm của cột tương ứng. Các cột được cho theo thứ tự từ phía trước ra phía sau thuyền.

Dữ liệu ra

Ghi một số nguyên duy nhất: tổng độ kém hiệu quả nhỏ nhất có thể.

Lưu ý dùng kiểu số nguyên \(64\) bit để tính toán và xuất kết quả, chẳng hạn long long trong C/C++ hoặc int64 trong Pascal.

Ràng buộc

• \(2\le N\le 100\,000\).
• \(1\le H\le 100\,000\).
• \(1\le K\le H\).

Chấm điểm trên hệ thống

Lưu ý: Cách chia nhóm và tính điểm dưới đây là bản điều chỉnh để luyện tập trên hệ thống, không khẳng định tương đương cách chấm tại IOI gốc.

Mỗi nhóm được chấm độc lập: chỉ nhận điểm của nhóm khi vượt qua tất cả bộ kiểm thử trong nhóm; nếu có bộ kiểm thử không đạt thì nhóm nhận 0 điểm. Tổng điểm tối đa là 100.

Nhãn nhóm là phần số trong tên tệp dữ liệu gốc. Tất cả tệp cùng nhãn, kể cả các hậu tố chữ và pf, đều thuộc nhóm đó.

Các ví dụ trong đề không tính điểm.

Ví dụ

6
3 2
5 3
4 1
2 1
4 3
3 2

10

Nguồn

IOI 2007.