شانزدهمین سوال ترجمه شد:

 

نویسنده : امیر محمد فرزانه

 

10450 - World Cup Noise

محدودیت زمانی : 3 ثانیه

 

سر و صدای جام جهانی!

"کره،کره". این فریاد حدود 54000 طرفدار فوتبال خوشحال است که تیمشان در کشور خودشان به مرحله ی نیمه نهایی جام جهانی فوتبال راه یافته است. امّا با این که شور و شوق آن ها واقعی است، مردم کره هنوز خیلی توسط طبیعت سازمان یافته اند. برای مثال آنان ترومپت های بزرگی را تدارک دیده اند تا تیمشان را در زمین پشتیبانی کنند. طرفداران می خواهند تا میزان صدا را در طول برگزاری مسابقه ثابت نگه دارند.

ترومپت ها به وسیله گاز فشرده کار می کنند و اگر هوا به مدت 2 ثانیه متوالی وارد ترومپت شود، ترومپت می شکند. بنابراین تا وقتی ترومپت صدا می دهد، همه چیز خوب است امّا هنگام مکث ترومپت، طرفداران باید فریاد بزنند : "کره" !

قبل از مسابقه گروهی از طرفداران جمع شده و برای یک الگوی صدا برای تشویق تیمشان تصمیم گیری می کنند. الگوی صدا ترتیبی از ها و 1 هاست که در آن شماره ی 1 ، لحظه ی دمیده شدن در ترومپت و شماره ی 0 لحظه ی فریاد "کره" طرفداران را نشان می دهد. برای اطمینان از نشکستن ترومپت، الگو نباید دو 1 متوالی داشته باشد.

بنابراین در این مسئله شما باید با توجه به عدد صحیح مثبت n به عنوان ورودی ، تعداد الگو های متفاوت ممکن به طول n برای تشویق را محاسبه کنید. همچنین در نظر بگیرید که در یک دنباله به طول n هیچ دو 1 مجاوری دیده نمی شود. برای مثال،  به ازای n = 3  پاسخ برابر با 5 می شود.(دنباله های 000, 001, 010, 100, 101 صحیح هستند، در حالی که دنباله های 011 110, 111 پذیرفتنی نیستند.)

 

ورودی

خط اول ورودی شامل تعداد تست ها می شود و برای هر تست یک عدد صحیح مثبت کوچکتر از 51 در یک خط می آید.

 

خروجی

خروجی هر تست با یک خط شامل “Scenario #i:” آغاز می شود، به طوری که i نشان دهنده ی شماره ی تست است و از یک شروع می شود.سپس در یک خط تعداد دنباله های به طول n را که 1 های مجاور ندارند را در یک خط چاپ کرده و خروجی هر تست را با یک خط خالی پایان دهید.

نمونه ها و لینک ها در ادامه مطلب

 

ورودی نمونه

2

3

1

خروجی نمونه

Scenario #1:

5

 

Scenario #2:

2

 

برای دیدن اصل سوال و فرستادن جواب می توانید به نشانی زیر مراجعه کنید:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1391

 

 برای دریافت فایل PDf سوال به زبان انگلیسی به نشانی زیر مراجعه کنید :

http://uva.onlinejudge.org/external/104/10450.pdf

 

برای دریافت فایل PDF سوال به زبان فارسی به نشانی زیر مراجعه کنید:

دریافت فایل
عنوان فایل:10450 - World Cup Noise