Đường đi chẵn
Đề bài
Mô tả
Năm ngoái, Arthur tham gia Olympic Robot Việt Nam với một con robot bị trục trặc. Năm nay, Arthur quyết định tham gia thêm một lần nữa.
Thử thách năm nay khó hơn nhiều. Sân thi đấu là một lưới vuông, góc dưới bên trái tại và góc trên bên phải tại . Tại mỗi điểm trong điểm lưới có một bóng đèn. Ban đầu có đúng bóng đèn đang bật. Robot được phép chạy nhiều lượt và mục tiêu là tắt hết các bóng đèn.
Một lượt chạy hợp lệ của robot là một dãy các điểm lưới thỏa mãn:
- điểm này nằm trong sân thi đấu (tức là với mọi );
- các điểm này đôi một phân biệt;
- hai điểm liên tiếp phải kề nhau, tức là với mọi ;
- độ dài đường đi () phải là số chẵn.
Theo luật thi, trong một lượt chạy, mỗi khi robot đi qua một điểm lưới, robot có thể chọn tắt bóng đèn tại đó. Tuy nhiên, robot của Arthur lại bị lỗi: nó luôn đảo trạng thái bóng đèn (bật thành tắt, tắt thành bật) mỗi khi đi qua một điểm lưới. Nói cách khác, cả bóng đèn tại đều bị đảo trạng thái.
Với con robot lỗi này, chỉ riêng việc tắt hết đèn cũng đã khó. Nhiệm vụ của bạn là giúp Arthur làm được điều đó. Số lượt chạy không cần tối thiểu, nhưng không được vượt quá .
Dữ liệu vào
Dòng đầu tiên chứa số nguyên , số bộ dữ liệu. Tiếp theo là bộ dữ liệu, mỗi bộ có dạng:
- Dòng đầu tiên chứa hai số nguyên và .
- dòng tiếp theo, dòng thứ chứa hai số nguyên , vị trí của một bóng đèn đang bật lúc đầu. Các vị trí này đôi một phân biệt.
Dữ liệu ra
Với mỗi bộ dữ liệu:
- Nếu không thể tắt hết các bóng đèn với không quá lượt chạy, in ra .
- Ngược lại, in ra (), số lượt chạy, trên dòng đầu tiên, tiếp theo là dòng mô tả lượt chạy. Mỗi dòng bắt đầu bằng số nguyên , độ dài đường đi, tiếp theo là cặp số nguyên (), tọa độ các điểm trên đường đi.
Nếu có nhiều đáp án, bạn có thể in ra đáp án bất kỳ.
Ràng buộc
- .
- , .
- .
- Tổng trong tất cả các bộ dữ liệu không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 2 4 0 0 0 2 1 1 2 1 4 5 1 1 2 1 2 2 3 2 3 3 |
12 2 0 0 1 0 1 1 2 1 0 0 0 0 1 2 0 0 0 1 1 1 2 0 2 1 2 1 1 2 1 2 0 2 0 1 2 0 2 0 1 1 1 2 1 1 2 1 2 2 2 2 1 1 1 1 2 2 1 1 1 2 2 2 2 2 1 1 1 1 2 2 1 1 2 1 2 2 2 2 1 2 2 1 2 15 2 1 1 2 1 2 2 2 2 1 1 1 1 2 2 1 1 1 2 2 2 2 2 1 3 1 3 2 2 3 1 2 1 2 2 2 2 1 2 2 3 2 2 2 2 3 2 3 3 2 3 2 2 2 2 3 2 2 2 2 3 3 3 2 3 2 4 2 4 3 2 4 2 3 2 3 3 2 3 2 3 3 4 3 2 3 3 4 3 4 4 2 4 3 3 3 3 4 2 3 3 3 4 4 4 |
Mỗi bóng đèn được tắt riêng bằng lượt chạy độ dài trong một ô vuông đơn vị. Chẳng hạn với bóng : ba lượt , , đảo ba lần và mỗi điểm còn lại hai lần. Đề gốc dùng ít lượt hơn: bộ thứ nhất có lượt và ; bộ thứ hai có lượt đi qua cả bóng. |
| 2 1 1 0 0 1 2 1 1 0 1 |
3 2 0 0 1 0 1 1 2 1 0 0 0 0 1 2 0 0 0 1 1 1 6 2 1 1 0 1 0 0 2 0 1 1 1 1 0 2 1 1 1 0 0 0 2 0 1 1 1 1 0 2 1 1 0 1 0 0 2 0 1 0 0 1 0 |
Ví dụ bổ sung (không có trong đề gốc). |
Bình luận