Nội dung Bài tập
- Mã:
- CB_CHESS
- Tên:
- Cờ Vua - CodeBrain
- Dạng thi:
- acm
- Thang điểm:
- 1 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 256 MB
- Được tạo bởi:
- nxphuc
Nobita và Xuka rất thích chơi cờ vua. Tuy nhiên, Nobita dần cảm thấy chán trò chơi
này, bởi cậu không thể nào thắng được Xuka vì cô bé quá thông minh. Nobita rất
muốn chơi cùng với Xuka, tuy nhiên lại không muốn thua cô bé như vậy. Mặc dù rất
muốn đổi sang một trò chơi khác, tuy nhiên Xuka lại không thích như vậy và đưa ra
cho Nobita một câu hỏi, nếu cậu trả lời được thì Xuka sẽ đồng ý đổi sang trò chơi
mới.
Bài toán của Xuka đưa ra như sau: Trên bàn cờ vua vô hạn, các dòng được đánh số
từ trên xuống dưới và các cột được đánh số từ trái sang phải, chỉ số bắt đầu từ 0, ô
tại dòng x cột y được gọi là ô (x, y). Ban đầu đặt lên đó N quân cờ, sau đó, tại mỗi
bước, người chơi có thể đặt một quân cờ vào ô (x, y) nến như thỏa 2 điều kiện sau:
- Tại dòng x, tồn tại 2 quân cờ tại 2 ô (x, y1) và (x, y2) sao cho y1 < y < y2.
- Tại dòng y, tồn tại 2 quân cờ tại 2 ô (x1, y) và (x2, y) sao cho x1 < x < x2.
Hỏi rằng, sau khi thực hiện liên tục các bước đi như vậy, thì đến cuối cùng, sẽ có tối
đa bao nhiêu quân cờ nằm trên bàn cờ.
Mặc dù rất muốn đổi trò chơi khác nhưng Nobita lại không được thông minh cho lắm
nên vẫn chưa biết cách nào để tính được kết quả. Nhưng nếu không trả lời được câu
hỏi của Xuka thì cậu lại phải tiếp tục chơi cờ vua ☹ (chơi mà thua hoài ai mà muốn
chơi). Hãy giúp Nobita trả lời câu hỏi đó nhanh nhất có thể nhé.
Dữ liệu nhập:
Dòng đầu tiên chứa số nguyên N là số quân cờ được đặt sẵn trên bàn cờ (N ≤ 105).
N dòng tiếp theo, dòng thứ i chứa hai số nguyên không âm xi, yi là tọa độ của quân cờ
thứ i (1 ≤ i ≤ N). Các tọa độ không vượt quá 109.
Dữ liệu xuất:
Số quân cờ tối đa có thể nằm trên bàn cờ.
Ví dụ:
Input Output
Giải thích:
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
#include <iostream>using namespace std;struct ps { int tu, mau; &...