Teemo Hái Nấm

Submit solution
Points: 4 (partial)
Time limit: 0.8s
Memory limit: 98M
Author:
koembuonlam
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Teemo có một cánh đồng nấm gồm N*N ô. Các dòng được đánh số từ 1 đến N từ trên xuống dưới, các cột được đánh số từ 1 đến N từ trái sang phải. Teemo rất thích ma trận hình xoắn ốc vì vậy anh ta đã đánh số các ô nấm của mình theo số thứ tự xoắn ốc bắt đầu từ ô (1,1) . Hình xoắn ốc đi từ ngoài vào trong theo chiều kim đồng hồ. Hình dưới là ví dụ với bảng N=5.

enter image description here

Rồi mùa thu hoạch nấm đã tới, Teemo đang ở vị trí của ô số X và muốn chuyển đến ô của số Y bằng cách thực hiện một số bước di chuyển. Trong mỗi bước, Teemo chỉ có thể di chuyển từ ô số A đến ô số B nếu:

  • Ô chứa số A và ô chứa số B có chung một cạnh.
  • A và B nguyên tố cùng nhau.

Cho N,X,Y , Teemo muốn biết số bước di chuyển ít nhất để chuyển từ ô số X đến ô số Y. Các bạn hãy giúp anh ấy nhé.

Dữ liệu nhập:

  • Dòng đầu tiên chứa số nguyên T là số lượng test. (1≤T≤10)
  • Trong T dòng tiếp theo, mỗi test trên một dòng là 03 số nguyên N, X và Y (1≤N≤1000,1≤X,Y≤106).

Dữ liệu xuất:

  • Với mỗi test, in ra số bước ít nhất để di chuyển từ ô số X đến ô số Y. Nếu không di chuyển được in ra -1

Ví dụ

Input:

1

5 3 18

Output:

3

Thực hiện 3 bước:

  • Từ ô số 3 chuyển qua ô số 4 (3 và 4 nguyên tố cùng nhau)
  • Từ ô số 4 chuyển qua ô số 19 (4 và 19 nguyên tố cùng nhau)
  • Từ ô số 19 chuyển qua ô số 18 (19 và 18 nguyên tố cùng nhau)

Comments


  • 0
    Hinyeuthanh3000  commented on Oct. 26, 2024, 5:42 p.m.

    vậy theo input thì teemo đi từ ô 3 sang ô 25 rồi quay lại 18 thì chỉ có 2 bước chứ nhỉ


  • 0
    Manh_KHMT_K64  commented on Aug. 17, 2024, 8:52 a.m.

    ai cho em xin ảnh ma trận kia được không ạ:<


  • 0
    ndh96coder  commented on Feb. 11, 2018, 4:54 p.m.

    XIn lỗi các bạn. Cập nhật lại N <= 1000 nhé