สมมติว่ามี n บล็อกในเส้นทาง และพนักงานกำลังวางกระเบื้องสีบนบล็อก ผู้ปฏิบัติงานกำลังวางบล็อกในลักษณะที่ว่าหากหมายเลขบล็อกในเส้นทางหารด้วย 4 หรือ/และ 2 ลงตัว แต่ไม่ใช่ 42 เขาก็จะวางแผ่นสีไว้ที่นั่น เราต้องหาจำนวนบล็อกที่เขาสามารถปิดได้หากเขาเริ่มด้วยกระเบื้องสีจำนวน k ชิ้น
ดังนั้นหากอินพุตเท่ากับ k =16 เอาต์พุตจะเป็น 32
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- MOD =10^9 + 7
- ผลหาร :=มูลค่าพื้นของ (k / 20)
- ที่เหลือ :=k mod 20
- ถ้าเศษเหลือเท่ากับ 0 แล้ว
- ผลตอบแทน ((42 * ผลหาร - 2) MOD MOD)
- มิฉะนั้น
- ผลตอบแทน ((42 * ผลหาร + 2 * ส่วนที่เหลือ) MOD MOD)
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def solve(k):
MOD = 10**9 + 7
quotient = k // 20
remainder = k % 20
if remainder == 0:
return ((42 * quotient - 2) % MOD)
else:
return ((42 * quotient + 2 * remainder) % MOD)
print(solve(16)) อินพุต
16
ผลลัพธ์
32
