Google Foobar Challenge (Python) - ปัญหา Lucky LAMBS [ปิดแล้ว]

Question

คำถามคือ:

การเป็นลูกน้องไม่ใช่เรื่องน่าเบื่อเลย ในบางครั้งเมื่อผู้บัญชาการแลมด้ารู้สึกใจกว้างเธอจะแจก Lucky LAMBs (เหรียญเงินอเนกประสงค์ของแลมบ์ดา) ลูกน้องสามารถใช้ Lucky LAMB เพื่อซื้อของเช่นถุงเท้าคู่ที่สองหมอนสำหรับเตียงหรือแม้แต่อาหารประจำวันที่สาม!

อย่างไรก็ตามการส่ง LAMBs ออกไปไม่ใช่เรื่องง่าย ทีมลูกน้องแต่ละคนมีลำดับความอาวุโสที่เข้มงวดซึ่งต้องได้รับการเคารพ - มิฉะนั้นพรรคพวกจะก่อจลาจลและคุณจะถูกลดตำแหน่งกลับไปเป็นมินเนี่ยนอีกครั้ง!

มีกฎสำคัญ 4 ข้อที่คุณต้องปฏิบัติตามเพื่อหลีกเลี่ยงการก่อจลาจล:

1. ลูกน้องที่อายุน้อยที่สุด (มีอาวุโสน้อยที่สุด) จะได้รับ 1 LAMB (จะมีลูกน้องอย่างน้อย 1 คนในทีมเสมอ)
2. ลูกน้องจะประท้วงหากคนที่อยู่เหนือพวกเขาได้รับมากกว่าสองเท่าของจำนวน LAMB ที่พวกเขาทำ
3. ลูกน้องจะประท้วงหากจำนวน LAMB ที่มอบให้กับลูกน้องสองคนถัดไปรวมกันมากกว่าจำนวน LAMB ที่พวกเขาได้รับ (โปรดทราบว่าลูกน้องที่เป็นผู้เยาว์ที่สุดสองคนจะไม่มีลูกน้องสองคนดังนั้นกฎนี้จึงใช้ไม่ได้กับพวกเขาลูกน้องที่รองลงมาอันดับ 2 จะต้องมี LAMB มากที่สุดเท่าที่จะเป็นลูกน้องรุ่นน้องได้มากที่สุด)
4. คุณสามารถหาลูกน้องเพิ่มได้เสมอ - ผู้บัญชาการมีพนักงานมากมาย หากมี LAMB เหลือเพียงพอจนสามารถเพิ่มลูกน้องอีกคนเป็นผู้อาวุโสที่สุดได้ในขณะที่ปฏิบัติตามกฎอื่น ๆ คุณต้องเพิ่มและจ่ายเงินให้ลูกน้องคนนั้นเสมอ

โปรดทราบว่าคุณอาจไม่สามารถแจก LAMB ทั้งหมดได้ LAMB เดียวไม่สามารถแบ่งย่อยได้ นั่นคือลูกน้องทุกคนต้องได้ LAMB จำนวนเต็มบวก

เขียนฟังก์ชันที่เรียกว่าโซลูชัน (total_lambs) โดยที่ total_lambs คือจำนวนเต็มของ LAMB ในเอกสารประกอบคำบรรยายที่คุณพยายามหาร ควรส่งคืนจำนวนเต็มซึ่งแสดงถึงความแตกต่างระหว่างจำนวนลูกน้องขั้นต่ำและสูงสุดที่สามารถแบ่งปัน LAMB ได้ (นั่นคือการมีน้ำใจให้กับผู้ที่คุณจ่ายเงินและขี้เหนียวที่สุดเท่าที่จะทำได้ตามลำดับ) ในขณะที่ยังคงปฏิบัติตามทั้งหมดข้างต้น กฎเพื่อหลีกเลี่ยงการก่อจลาจล ตัวอย่างเช่นถ้าคุณมี LAMB 10 ตัวและใจกว้างที่สุดเท่าที่จะเป็นไปได้คุณสามารถจ่ายเงินให้ลูกน้องเพียง 3 คน (1, 2 และ 4 LAMBs ตามลำดับความอาวุโสจากน้อยไปมาก) ในขณะที่ถ้าคุณขี้เหนียวที่สุดคุณสามารถจ่าย 4 ลูกน้อง (1, 1, 2 และ 3 LAMBs) ดังนั้นวิธีแก้ปัญหา (10) ควรส่งคืน 4-3 = 1

เพื่อให้สิ่งต่างๆน่าสนใจ Commander Lambda จึงแตกต่างกันไปขนาดของการจ่ายเงินรางวัล Lucky LAMB คุณสามารถคาดหวังว่า total_lambs จะเป็นจำนวนเต็มบวกที่น้อยกว่า 1 พันล้านเสมอ (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

เมื่อฉันเรียกใช้รหัสนี้ในบรรทัดคำสั่งบนพีซีของฉันมันจะส่งคืนผลลัพธ์ที่ถูกต้อง แต่เมื่อฉันตรวจสอบบนเทอร์มินัล foobar มันขึ้นว่า Test Failed สำหรับ 9 ใน 10 กรณี มีใครช่วยฉันได้ไหม นอกจากนี้หากรหัสของฉันผิดโปรดแจ้งให้ฉันทราบด้วย ขอบคุณ !!

Answer 1

ดูเหมือนว่าเมื่อคุณใจกว้างคุณจะจ่าย 1, 2, 4, 8, 16 เพื่อให้ลูกน้องได้รับ2**n - 1หน่วย

เมื่อคุณขี้เหนียวคุณจ่าย 1, 1, 2, 3, 5, ... (คุณสามารถพูดว่า Fibonacci ได้หรือไม่?) เพื่อให้ลูกน้องได้รับผลรวมของ F (0), ..... F ( m - 1) ซึ่งก็คือ F (m + 1) - 1

ดังนั้นคุณต้องไปหาที่ใหญ่ที่สุด n เช่นนั้นและมที่ใหญ่ที่สุดดังกล่าวว่า2 ** n - 1 <= lambsF(m + 1) - 1 <= lambs

นี่เป็นความท้าทายในการเขียนโค้ดของ Google ดังนั้นคุณต้องเขียนโค้ดด้วยตัวเอง