+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- گلابی، یک مدیر فنی منظم و علاقه‌مند به بهینه‌سازی مدیریت تسک‌هاست. او همواره به دنبال روش‌هایی است تا کارها را به شکل بهتر سازماندهی کند و زمان تیمش را به صورت موثرتری مدیریت نماید. برای مقایسه پیچیدگی تسک‌ها، از واحدی به نام «[استوری پوینت](https://mohsenalavi.com/580/%D8%A7%D8%B3%D8%AA%D9%88%D8%B1%DB%8C-%D9%BE%D9%88%DB%8C%D9%86%D8%AA-%DA%86%DB%8C-%D9%87%D8%B3%D8%AA-%D9%88-%DA%86%DB%8C-%D9%86%DB%8C%D8%B3%D8%AA%D8%9F/)» استفاده می‌شود. هرچه استوری پوینت یک تسک بیشتر باشد، آن تسک پیچیده‌تر یا پرریسک‌تر خواهد بود. برای ساده‌تر شدن تخمین تعداد استوری پوینت‌های یک تسک فنی، معمولاً از اعداد دنباله فیبوناچی استفاده می‌شود. این دنباله با اعداد ۱ و ۲ شروع شده و هر عدد برابر مجموع دو عدد قبلی است. به این ترتیب دنباله به صورت ۱، ۲، ۳، ۵، ۸، ۱۳، ۲۱ و... ادامه می‌یابد. استفاده از این دنباله به دلیل افزایش تدریجی و منطقی آن، در تخمین پیچیدگی تسک‌ها بسیار کارآمد است. گلابی در جلسات برنامه‌ریزی تیم فنی، درباره تعداد استوری پوینت هر تسک تصمیم‌گیری می‌کند. او می‌داند که برای برگزاری یک مسابقه برنامه‌نویسی، $n$ استوری پوینت نیاز است و هدفش این است که این مقدار را به **کمترین تعداد تسک ممکن** تقسیم کند، به طوری که تعداد استوری پوینت هر تسک یکی از اعداد دنباله فیبوناچی باشد. گلابی امیدوار است با این روش برنامه‌ریزی ساده‌تر و کارآمدتری انجام دهد. # ورودی در تنها خط ورودی، عدد صحیح $n$ داده می‌شود که تعداد استوری پوینت‌های مورد نیاز برای مسابقه برنامه‌نویسی را مشخص می‌کند. $$1 \le n \le 10^9$$ # خروجی در تنها خط خروجی، کمترین تعداد تسک‌های ممکن را چاپ کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 4 ```` ## خروجی نمونه ۱ ``` 2 ```` عدد $4$ در دنباله فیبوناچی نیست، اما می‌توان آن را به دو تسک $3$ و $1$ تقسیم کرد که هر دو جزو دنباله فیبوناچی هستند. ## ورودی نمونه ۲ ``` 20 ```` ## خروجی نمونه ۲ ``` 3 ```` عدد $20$ را می‌توان به سه تسک $13$، $5$ و $2$ تقسیم کرد که همگی در دنباله فیبوناچی قرار دارند. <details class="red"> <summary> **اشتباهات متداول** </summary> <details class="red"> <summary> **چک کردن شرایط ورودی مسئله** </summary> نیازی نیست چک کنید شرایط گفته شده در ورودی برقرار است یا نه. توضیحات محدودیت‌ها فقط برای آگاهی شما درباره‌ی تست‌ها و محدودیت‌های مسئله است و قطعاً در ورودی‌های داده شده به برنامه‌ی شما رعایت می‌شوند. پس نیازی نیست بنویسید: ```python if 1 <= n <= 100: # answer of problem else: # print('invalid input') ``` </details> <details class="red"> <summary> **ابتدا همه‌ی ورودی را گرفتن و در نهایت همه‌ی خروجی را چاپ کردن** </summary> شما می‌توانید لابه‌لای دریافت ورودی، خروجی دهید. پس نیازی نیست ابتدا همه‌ی ورودی‌ها را دریافت کنید و در نهایت همه‌ی خروجی‌ها را چاپ کنید. مخصوصاً برای سوالاتی که باید به چندین سوال پاسخ دهید، می‌توانید دو قسمت ورودی و خروجی را کاملاً مستقل در نظر بگیرید و مطمئن باشید تداخلی پیش نمی‌آید. </details> <details class="red"> <summary> **چاپ کردن موارد اضافه برای دریافت ورودی** </summary> لطفاً از چاپ کردن موارد اضافه مثل `please enter a number` برای دریافت ورودی پرهیز کنید. برای مثال در زبان پایتون نباید بنویسید: ```python input('please enter:') ``` </details> <details class="red"> <summary> **چند فایلی کد زدن** </summary> برای زبان‌هایی مثل جاوا نباید در بالای کد شما آدرس پکیج داده شود. برای مثال در بالای کد خود نباید بنویسید: ```java package ir.quera.contest; ``` </details> <details class="red"> <summary> **استفاده از چند `Scanner` برای دریافت ورودی** </summary> در زبان جاوا، باید فقط یک شئ از جنس `Scanner` تعریف کنید و همه‌ی ورودی‌ها را با آن دریافت کنید. </details> <details class="red"> <summary> **نام فایل ارسالی در جاوا** </summary> در زبان جاوا، باید نام فایل ارسالی شما با نام کلاسی که تابع `main` در آن قرار دارد یکسان باشد، برای مثال اگر نام کلاس شما `Question1` است، نام فایل ارسالی شما باید `Question1.java` باشد. </details> <details class="red"> <summary> **نحوه‌ی دریافت ورودی و چاپ کردن خروجی** </summary> برای آشنایی بیشتر برای نحوه‌ی دریافت ورودی و چاپ کردن خروجی این [لینک](https://quera.org/course/assignments/2693/problems/8774) را مطالعه کنید. </details>

حل سؤال در بانک سؤالات