반경 r까지 주변 환경을 모니터링할 수 있는 센서 모듈이 있다고 가정합니다. 모니터링이 필요한 모듈 모니터링 서클의 격자점에 몇 가지 사항이 있습니다. 따라서 k개의 저전력 모듈을 배치하여 특정 지점만 모니터링할 수 있습니다. 반경의 제곱과 저전력 모듈의 k 개수가 주어지면 포인트를 올바르게 모니터링할 수 있는지 확인해야 합니다. 모니터링이 가능하면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
따라서 입력이 반지름(j) =4의 제곱, 모니터링 지점 수(k) =3과 같으면 출력은 False
가 됩니다.j =4이면 모니터링 원의 둘레에 4개의 점이 있습니다. (0,2), (0,-2), (2,0) 및(-2,0)입니다. 따라서 3개의 새로운 모니터링 스테이션을 도입하면 포인트를 완전히 모니터링할 수 없습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- square_set :=44721까지의 값의 제곱을 포함하는 집합
- i :=0
- res :=0
- 나는 <(j ^ 0.5) 동안, 하는 동안
- square_set에 (j - i ^ 2)가 있으면
- res :=res + 1
- 나는 :=나는 + 1
- square_set에 (j - i ^ 2)가 있으면
- res :=res * 4
- k>=res이면
- 참 반환
- 그렇지 않으면
- 거짓을 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
square_set = set([z ** 2 for z in range(44722)]) def solve(j, k): i = 0 res = 0 while i < (j ** 0.5): if j - i ** 2 in square_set: res += 1 i += 1 res *= 4 if k >= res: return True else: return False print(solve(4, 3))
입력
4, 3
출력
False