VM 13 Bài 16 - Trò chơi với những đồng xu

View as PDF

Submit solution

Points: 2.00 (partial)
Time limit: 5.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VM13 - Nguyễn Thành Trung
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

RR có ~N~ đồng xu giống hệt nhau.

RR đặt ~N~ đồng xu lên mặt phẳng tọa độ ~Oxy~, đồng xu thứ ~i~ có tọa độ (~x_i~, ~y_i~). Không có ~2~ đồng xu nào cùng vị trí.

Hai đồng xu ở vị trí ~(x_1, y_1)~ và ~(x_2, y_2)~ được gọi là kề nhau nếu ~|x_1 - x_2| + |y_1 - y_2| = 1~.

Một cách đặt các đồng xu lên mặt phẳng tọa độ như vậy được gọi là một trạng thái của ~N~ đồng xu.

Xét ~2~ trạng thái: ~H_1~, với các đồng xu ở tọa độ ~(x_1, y_1)~, ~(x_2, y_2)~ ..., ~(x_N, y_N)~ và ~H_2~ với các đồng xu ở tọa độ ~(u_1, v_1)~, ~(u_2, v_2)~, ..., ~(u_N, v_N)~.

Hai trạng thái ~H_1~ và ~H_2~ được gọi là tương đương nếu: tồn tại một hoán vị (~P_1~, ~P_2~, ..., ~P_N~) thỏa mãn:

  • ~u_1 - x(P_1) = u_2 - x(P_2) = \dots = u_N - x(P_N)~.
  • ~v_1 - y(P_1) = v_2 - y(P_2) = \dots = v_N - y(P_N)~.

Nhiệm vụ của bạn là chuyển các đồng xu từ trạng thái xuất phát đến trạng thái đích (hoặc một trạng thái tương đương với trạng thái đích), sau không quá ~10^{6}~ bước.

Mỗi bước, bạn được di chuyển đúng một đồng xu, từ vị trí ~A~ đến vị trí ~B~, nếu:

  • Vị trí ~B~ không có đồng xu nào
  • Sau khi đặt đồng xu vào vị trí ~B~, nó kề với ít nhất ~2~ đồng xu khác.

Cho biết rằng luôn tồn tại dãy di chuyển thỏa mãn đề bài, và tồn tại ~2~ đồng xu trong trạng thái xuất phát sao cho nếu di chuyển ~2~ đồng xu này đến vị trí bất kỳ (không trùng nhau và không trùng với các đồng xu khác), thì vẫn tồn tại kết quả.

Input

  • Dòng ~1~: Chứa số nguyên dương ~N~
  • Dòng ~2~ ...~N+1~: Mỗi dòng ~2~ số nguyên ~x_i~, ~y_i~, là tọa độ của đồng xu thứ ~i~ trong trạng thái xuất phát
  • Dòng ~N+2~: Dòng trống
  • Dòng ~N+3~ ...~2 \times N+2~: Mỗi dòng ~2~ số nguyên ~x_i~, ~y_i~, là tọa độ của đồng xu thứ ~i~ trong trạng thái đích.

Output

Dòng ~1~: ~K~ - số bước di chuyển của bạn

~K~ dòng tiếp theo, mỗi dòng gồm ~4~ số nguyên dương ~x_i~, ~y_i~, ~u_i~, ~v_i~, thể hiện bạn ~d_i~ chuyển đồng xu từ (~x_i~, ~y_i~) đến (~u_i~, ~v_i~).

Nếu có nhiều cách di chuyển thỏa mãn, bạn chỉ cần in ra cách di chuyển bất kỳ (không cần gồm ít bước nhất).

Giới hạn

  • ~1 \leq N \leq 30~;
  • ~x_i~, ~y_i~ là các số nguyên có giá trị tuyệt đối không quá ~10^{9}~;

Bài của bạn sẽ được chấm trên thang điểm ~100~. Điểm mà bạn nhận được sẽ tương ứng với % test mà bạn giải đúng.

Với mỗi test, bài của bạn sẽ được chấm là đúng nếu các bước di chuyển của bạn hợp lệ và sau khi thực hiện ~K~ bước di chuyển, trạng thái thu được tương đương với trạng thái kết thúc

Sample Input

5
1 1
1 2
2 2
2 3
3 2

1 2
1 3
2 1
2 2
2 3

Sample Output

2
3 2 2 1
1 1 1 3

Comments

Please read the guidelines before commenting.


There are no comments at the moment.