Hướng dẫn possible path hackerrank solution python - con đường có thể giải pháp hackerrank python
Định nghĩa vấn đề ngắn:Adam đang đứng ở điểm & nbsp; (a, b) & nbsp; trong một lưới 2D vô hạn. Anh ta muốn biết nếu anh ta có thể đạt đến điểm & nbsp; (x, y) & nbsp; hoặc không. Hoạt động duy nhất anh ta có thể làm là di chuyển đến điểm & nbsp; (a+b, b) (a, b+a) (a-b, b) hoặc (a, b-a) & nbsp; từ một số điểm & nbsp; (a, b). Nó được cho là anh ta có thể di chuyển đến bất kỳ điểm nào trên lưới 2D này, tức là, các điểm có tọa độ tích cực hoặc âm & nbsp; (hoặc & nbsp;). Nói với Adam rằng anh ta có thể tiếp cận & nbsp; & nbsp; hay không. Liên kếtCó thể là con đường Complexity:Độ phức tạp về thời gian là O (log (n)) Độ phức tạp không gian là O (1) Execution:Tuyên bố vấn đề không yêu cầu đường dẫn từ A, B đến X, Y, chỉ là một đường dẫn tồn tại. Điều này làm cho nó một vấn đề toán học. Chúng tôi biết rằng GCD (A, B) == GCD (A+B, B) == GCD (A-B, B). Tại sao? Bởi vì nếu một cái gì đó là một ước số D của B, việc thêm/trừ B từ bất kỳ số A nào cũng chia hết bởi D sẽ không thay đổi yêu cầu chia rẽ. Do đó gcd (a, b) == gcd (a+n*b, b+m*a) trong đó n, m là số nguyên. Theo các quy tắc, chúng ta có thể nhận ra rằng GCD (A+N*B, B+M*A) là GCD (X, Y), dẫn chúng ta đến giải pháp cuối cùng. Solution:def gcd(a, b):
if a % b == 0:
return b
else:
return gcd(b, a % b)
def solve(a, b, x, y):
return gcd(a,b) == gcd(x,y)
Nếu bạn thích bài đăng này, thì hãy chắc chắn rằng bạn đăng ký nhận bản tin và/hoặc nguồn cấp dữ liệu của tôi. 6 tháng trước+ 0 bình luận in an infinite 2D grid. He wants to know if he can reach point or not. The only operation he can do is to move to point from some point . It is given that he can move to any point on this 2D grid, i.e., the points having positive or negative (or ) co-ordinates. Nói với Adam rằng anh ta có thể tiếp cận hay không. or not. Định dạng đầu vào Dòng đầu tiên chứa một số nguyên, theo sau là các dòng, mỗi dòng chứa các số nguyên được phân tách không gian, tức là, và., followed by lines, each containing space-separated integers i.e. , , and . Định dạng đầu ra Đối với mỗi trường hợp thử nghiệm, hiển thị Đầu vào mẫu Giải trình
Chúng tôi sử dụng cookie để đảm bảo bạn có trải nghiệm duyệt tốt nhất trên trang web của chúng tôi.Vui lòng đọc chính sách cookie của chúng tôi để biết thêm thông tin về cách chúng tôi sử dụng cookie.
toán học
|
