Trò chơi đổi số

[TrucSam (Truc)]

Mình đang bí bài này quá. Bạn nào biết cách làm vui lòng giúp mình nhé. Thanks

Trong trò chơi đổi số, một cặo số nguyên dương (x, y) có thể đổi lấy một cặp số mới trong có cặp số (x + y, y), (y, x) hoặc (x-y, y) nếu x-y cũng là số nguyên dương.

Cho trước 4 số nguyên dương a, b, c và d. Người chơi cần tìm cách đổi từ cặp số (a, b) thành cặp số (c, d)n phím 4 số nguyên dương a, b, c và d không vượt qua 1000.

Xuất ra màn hình số k là số lượng số lần đổi số ít nhất từ cặp số (a, b) nhận được cặp số (c, d). Nếu không tìm được cách đổi số thì xuất K = -1.

Ví dụ: Với a= 14, b = 35, c= 28 và d = 21 thi K = 7. Quá trình đổi số có thể thực hiện như sau: Từ cặp số (14,35) ta lần lượt đổi thành các cặp sô (35, 14), (21, 14), (7, 14), (14, 7), (21,7), (7,21) và cuối cùng nhân được cặp số (28,21).

[dtran]

bài này khá hay đó, nên dùng đệ qui nhĩ

[rogp10]

Đầu tiên là tìm bất biến (invariant) trước x, y luôn thỏa mãn một điều kiện nào đó.

[hungaya (Hung)]

Gọi (x,y) là ước chung lớn nhất của 2 số nguyên dương x và y, thì: (x,y) = (y,x) = (x+y, x) = (x-y, y). Do đó, điều kiện để K = -1 là (a,b) != (c,d).

Quá trình thực hiện thì gồm 4 bước:

• Bước 1: sử dụng Euclid algorithm để chuyển (a,b) thành dạng (p, kp) hoặc (kp, p) với p = (a,b).
• Bước 2: sử dụng Euclid algorithm chuyển tiếp (c,d) thành dạng (p, kp) hoặc (kp, p).
• Bước 3: loại các bước trùng nhau gần (p, kp). Ví dụ:
  • (a,b) -> (a₁, b₁) -> (a₂, b₂) -> … -> (m, n) -> … -> (p, kp)
  • (c,d) -> (c₁, d₁) -> (c₂, d₂) -> … -> (m, n) -> … -> (p, kp)
  • Loại các bước từ (m, n) -> … -> (p, kp)
• Bước 4: Nối (a,b) và (c,d) lại với nhau, trong đó (c,d) đổi ngược thứ tự lại, thành (a,b) -> … -> (p, kp) -> … (c,d).
  • hoặc (a,b) -> … (m,n) -> … -> (c,d)

[TrucSam (Truc)]

mình đã làm đc bước 1 và 2 rồi: mình đổi a và b thành ax+by=t, mình tìm x, y và t tương tự cho c và d (t là ước chung lớn nhất của a và b để đảm bảo ax+by = cp+dq=t) nhưng qua bước 3, 4 thì mình chưa biết cách loại và nối các bước lại như thế nào bạn gợi ý chút được không?

[hungaya (Hung)]

Sau khi nghĩ lại thì mình nghĩ cho (a,b) và (c,d) về (t,0) luôn cho tiện. Sau đó so từ (t,0) trở lên.

Bước 3 trở đi là mình đoán thôi, chả biết đúng hay sai cả :v
Thử vài ví dụ:

(20,15) --> (5,15) --> (15,5) --> (10,5) --> (5,5) --> (0,5) --> (5,0)
(25,20) --> (5,20) --> (20,5) --> (15,5) --> (10,5) --> (5,5) --> (0,5) --> (5,0)
==> (20,15) --> (5,15) --> (15,5) --> (20,5) --> (5,20) --> (25,20)

(21,15) --> (6,15) --> (15,6) --> (9,6) --> (3,6) --> (6,3) --> (3,3) --> (0,3) --> (3,0)
(12,9) --> (3,9) --> (9,3) --> (6,3) --> (3,3) --> (0,3) --> (3,0)
==> (21,15) --> (6,15) --> (15,6) --> (9,6) --> (3,6) --> (6,3) --> (9,3) --> (3,9) --> (12,9)

(12,17) --> (17,12) --> (5,12) --> (12,5) --> (7,5) --> (2,5) --> (5,2) --> (3,2) --> (2,1) --> (1,1) --> (0,1) --> (1,0)
(23,19) --> (4,19) --> (19,4) --> (15,4) --> (11,4) --> (7,4) --> (3,4) --> (4,3) --> (1,3) --> (3,1) --> (2,1) --> (1,1) --> (0,1) --> (1,0)
==> (12,17) --> (17,12) --> (5,12) --> (12,5) --> (7,5) --> (2,5) --> (5,2) --> (3,2) --> (2,1) --> (3,1) --> (1,3) --> (4,3) --> (3,4) --> (7,4) --> (11,4) --> (15,4) --> (19,4) --> (4,19) --> (23,19)

[tntxtnt]

xài BFS chạy nổi ko :V

edit: chắc là nổi, x, y <= 1000 thì BFS O(xy) ~ 10^6 là cùng :V

mỗi cặp (x,y) là 1 vertex
1 vertex có tối đa 3 edges tới (y,x), (x-y, y), (x+y,y)
tìm đường ngắn nhất từ vertex (a,b) tới vertex (c,d) thì BFS là ra :V :V