حل تمرین مرد مالیاتچی و جاعل کوئرا با پایتون

حل تمرین مرد مالیاتچی و جاعل کوئرا با پایتون

در این نوشته به روش حل یکی از سوالات برنامه نویسی وب‌سایت کوئرا می‌پردازیم.

حل تمرین مرد مالیاتچی و جاعل کوئرا با پایتون

اخیرا جاعلی پیدا شده است که فیش جعلی پرداخت مالیات درست می‌کند. با این روش مردم یک فیش جعلی، که نشان می‌دهد آن‌ها مالیاتشان را پرداخته‌اند، از این جاعل می‌گیرند و به اداره‌ی مالیات نشان‌ می‌دهند و دیگر مالیات نمی‌دهند. این پدیده‌ی شوم باعث کسادی بازار مرد مالیاتچی و بیکاری او شده است. متاسفانه مرد مالیاتچی که نمی‌تواند جلوی این اتفاق را بگیرد می‌خواهد بداند که حداقل چقدر وقتش خالی شده‌ است تا بتواند شغل دوم مناسبی پیدا کند. از این رو میخواهد تعداد فیش‌های اصل را بداند. یک فیش مالیاتی رشته‌ای به طول n است که تنها از 0 و 1 درست شده است. حال فیشی تقلبی است که حداقل یکی از رشته‌های زیر، حداقل یک بار، در آن بیاید:

110,101,111,011

برای فهم بیشتر به نمونه‌ها و توضیحشان مراجعه کنید. دقت کنید که هر فیشی که تقلبی نیست، اصل است.

ورودی

در تنها سطر ورودی n آمده است که نمایان‌گر اندازه‌ی رشته‌ی فیش‌ها است.

خروجی

در تنها سطر خروجی باقیمانده‌ی تعداد فیش‌های اصل بر 10⁹ + 7 را چاپ کنید.

مثال

ورودی نمونه 1

4

خروجی نمونه 1

6

توضیح نمونه‌ی اول

فیش‌های زیر تقلبی‌اند:

0011,0101,0110,0111,1010,1011,1100,1101,1110,1111

فیش‌های زیر اصل هستند:

0000,0001,0010,0100,1000,1001

پس از کل 16 حالت فیش‌ها، 10 تا تقلبی و 6 تا اصل هستند که چون سوال تعداد اصل‌ها را خواسته‌ است جواب برابر 6 می‌شود.

ورودی نمونه 2

3

خروجی نمونه 2

4

کد پایتون سوال تمرین مرد مالیاتچی و جاعل

n = int(input())
MOD = int(1e9 + 7)

dp = [0] * (n + 1)
dp[0] = 1
if n > 0:
    dp[1] = 2
if n > 1:
    dp[2] = 3

for i in range(3, n + 1):
    dp[i] = (dp[i - 1] + dp[i - 3]) % MOD

g = [1, 2, 4]
if n < 3:
    print(g[n])
else:
    print(dp[n])

منبع سوال: کوئرا

اگر نیاز به حل تمرین‌های دیگری از کوئرا دارید در بخش نظرات همین نوشته برای ما بنویسید.