trang chủ / đề bài / icpc21_nat_e

Đườ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 (0,0) và góc trên bên phải tại (M,M). Tại mỗi điểm trong (M+1)2 điểm lưới có một bóng đèn. Ban đầu có đúng N 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 (px0,py0),(px1,py1),…,(pxk,pyk) thỏa mãn:

  • k+1 điểm này nằm trong sân thi đấu (tức là 0≤pxi,pyi≤M với mọi 0≤i≤k);
  • 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à |pxi−pxi+1|+|pyi−pyi+1|=1 với mọi 0≤i<k;
  • độ dài đường đi (k) 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ả k+1 bóng đèn tại (px0,py0),(px1,py1),…,(pxk,pyk) đề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á 10000.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên T, số bộ dữ liệu. Tiếp theo là T bộ dữ liệu, mỗi bộ có dạng:

  • Dòng đầu tiên chứa hai số nguyên M và N.
  • N dòng tiếp theo, dòng thứ i chứa hai số nguyên xi,yi, 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á 10000 lượt chạy, in ra −1.
  • Ngược lại, in ra P (0≤P≤10000), số lượt chạy, trên dòng đầu tiên, tiếp theo là P dòng mô tả P lượt chạy. Mỗi dòng bắt đầu bằng số nguyên k, độ dài đường đi, tiếp theo là k+1 cặp số nguyên pxi,pyi (0≤i≤k), 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≤100000.
  • 1≤M≤50, 0≤N≤(M+1)2.
  • 0≤xi,yi≤M.
  • Tổng N trong tất cả các bộ dữ liệu không vượt quá 100000.

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 3 lượt chạy độ dài 2 trong một ô vuông đơn vị. Chẳng hạn với bóng (0,0): ba lượt (0,0)→(1,0)→(1,1), (1,0)→(0,0)→(0,1), (0,0)→(0,1)→(1,1) đảo (0,0) 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ó 2 lượt (0,0)→(0,1)→(0,2) và (2,1)→(1,1)→(0,1); bộ thứ hai có 1 lượt đi qua cả 5 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

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0