Google Foobar Challenge (Python)-Lucky LAMBS 문제 [종료 됨]
질문은 ~이야:
henchman이되는 것이 모든 고된 것은 아닙니다. 가끔 Lambda 사령관이 관대함을 느끼면 Lucky LAMB (Lambda의 다목적 머니 벅스)를 나눠줍니다. Henchmen은 Lucky LAMB를 사용하여 두 번째 양말 한 켤레, 침대용 베개 또는 세 번째 일일 식사 등을 구입할 수 있습니다!
그러나 실제로 LAMB를 전달하는 것은 쉽지 않습니다. 각 henchman 분대는 엄격한 선임 순위를 가지고 있으며, 그렇지 않으면 henchmen이 반란을 일으키고 모두 다시 미니언으로 강등됩니다!
반란을 피하기 위해 따라야 할 4 가지 주요 규칙이 있습니다.
- 가장 후배의 헨치 맨 (가장 낮은 선임)은 정확히 1 개의 LAMB를받습니다. (항상 한 팀에 최소 1 명의 헨치 맨이 있습니다.)
- 바로 위에있는 사람이 자신이하는 양의 두 배 이상을 받으면 헨치 맨은 반란을 일으킬 것입니다.
- 다음 두 부하를 합친 양의 양이 그들이 얻는 양보다 많으면 헨치 맨은 반란을 일으킬 것입니다. (가장 후배 두 명의 부하가 두 명의 부하 직원이 없기 때문에이 규칙이 적용되지 않는다는 점에 유의하십시오. 두 번째로 주니어 부하에게는 적어도 가장 후배의 부하만큼 많은 양의 양이 필요합니다.)
- 당신은 항상 더 많은 부하를 찾을 수 있습니다-사령관은 많은 직원을 가지고 있습니다. 다른 규칙을 준수하면서 다른 헨치 맨을 가장 선배로 추가 할 수있을 정도로 양이 충분하다면 그 헨치 맨을 항상 추가하고 지불해야합니다.
모든 LAMB를 나눠주지 못할 수도 있습니다. 단일 LAMB는 세분화 할 수 없습니다. 즉, 모든 henchmen은 양의 정수 양의 LAMB를 가져야합니다.
solution (total_lambs)라는 함수를 작성합니다. 여기서 total_lambs는 나누려는 유인물에있는 LAMB의 정수 개수입니다. 위의 모든 사항을 계속 준수하면서 LAMB를 공유 할 수있는 헨치 맨의 최소 및 최대 수의 차이를 나타내는 정수를 반환해야합니다. 반란을 피하기위한 규칙. 예를 들어, 10 개의 양이 있고 가능한 한 관대하다면 3 명의 헨치 맨 (오름차순으로 1, 2, 4 개의 양) 만 지불 할 수있는 반면, 가능한 한 인색 한 경우 4 개를 지불 할 수 있습니다. henchmen (1, 1, 2 및 3 LAMB). 따라서 solution (10)은 4-3 = 1을 반환해야합니다.
흥미를 유지하기 위해 Lambda 사령관은 Lucky LAMB 지불금의 크기를 변경합니다. total_lambs는 항상 10 억 (10 ^ 9) 미만의 양의 정수일 것으로 예상 할 수 있습니다.
내 코드 :
def solution(total_lambs):
if total_lambs <= 10**9:
return h_stin(total_lambs) - h_gen(total_lambs)
else: return 0
def h_gen(total_lambs):
x = 1
# I have directly used formulas for sum and nth term of GP instead of assigning them variables
while (2**x - 1) < total_lambs:
x += 1
if (2**x - 1) <= total_lambs or 2**(x-2) + 2**(x-3) <= total_lambs - (2**(x-1) - 1):
return x
else: return x-1
def h_stin(total_lambs):
if total_lambs == 1:
return 1
if total_lambs == 2:
return 2
arr = [1, 1]
for i in range(1,10**9):
if sum(arr) < total_lambs:
arr.append(arr[i] + arr[i-1])
else: break
if sum(arr) <= total_lambs:
return len(arr)
else: return len(arr) - 1
내 PC의 명령 줄에서이 코드를 실행하면 올바른 출력이 반환되지만 foobar 터미널에서 확인하면 10 개 사례 중 9 개에 대해 테스트 실패라고 표시됩니다. 누군가 나를 도와 줄 수 있습니까? 또한 내 코드가 잘못된 경우에도 알려주십시오. 감사!!
답변
당신이 관대하면 1, 2, 4, 8, 16을 지불하여 n henchman이 2**n - 1단위를 얻는 것 같습니다 .
당신이 인색 할 때, 당신은 1, 1, 2, 3, 5, ... (피보나치라고 말할 수 있습니까?)를 지불하여 m henchmen이 F (0), ..... F ( m-1) F (m + 1)-1.
그래서 당신은 그 2 ** n - 1 <= lambs와 같은 가장 큰 n과 그 와 같은 가장 큰 m 을 찾아야합니다 F(m + 1) - 1 <= lambs.
이것은 Google 코딩 과제이므로 직접 코드를 작성해야합니다.