- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
امتحانات میان‌ترم نزدیک است و وضعیت هندسه‌ی کاراکترهای کمکی خراب! این موضوع به شدت روی اعتماد به نفس کاراکترهای کمکی اثر گذاشته و کاراکتر اصلی ۱ را به فکر انداخته تا برای آن‌ها کلاس تقویتی تشکیل دهد.
از بین کاراکترهای کمکی $n$ نفر در این کلاس تقویتی ثبت‌نام کرده‌اند. کلاس تقویتی در کلاسی که $n$ نیمکت آن پشت سر هم و در یک ردیف چیده شده‌اند، برگزار می‌شود. نیمکت‌ها از جلوی کلاس تا انتها با شماره‌های ۱ تا $n$ شماره‌گذاری شده‌اند.
کاراکتر اصلی ۱ در اولین روز تدریسش برای کاراکترهای کمکی متوجه الگوی عجیبی در نشستن کاراکترهای کمکی روی نیمکت‌ها شد. کاراکتر کمکی ۱ که می‌آید روی نیمکت شماره‌ی ۱ می‌نشیند و از کاراکتر کمکی ۲ تا کاراکتر کمکی $n$ نیمکت استرس‌زدا را شناسایی می‌کنند و روی آن می‌نشینند.
نیمکتی را استرس‌زدا می‌نامیم که:
- خالی باشد.
- بیشینه فاصله را تا نزدیک‌ترین نیمکت پر داشته باشد. (واحد فاصله در اینجا تعداد نیمکت‌های بین است)
- اگر چند نیمکت با بیشینه فاصله موجود بود، نیمکتی که شماره‌ی آن از بقیه کمتر باشد.
از آنجایی که کاراکتر اصلی ۱ حوصله ندارد تا نشستن کاراکتر کمکی $n$ صبر کند، پس برنامه‌ای بنویسید که شماره‌ی نیمکتی که کاراکتر کمکی $n$ طبق الگو در آن می‌نشیند را چاپ کند.
ورودی
در تنها خط ورودی عدد طبیعی $n$ داده می‌شود.
$$1 \leq n \leq 10^{100 \ 000} $$
خروجی
در تنها خط خروجی شماره‌ی نیمکتی که کاراکتر کمکی $n$ در آن می‌نشیند را چاپ کنید.
مثال
ورودی نمونه
10
خروجی نمونه
9
توضیح
در مثال داده شده، کاراکتر کمکی ۱ طبق صورت سوال در نیمکت ۱ می‌نشیند.
# # # # # # # # # 1
10 9 8 7 6 5 4 3 2 1
نیمکت استرس‌زدا برای کاراکتر کمکی ۲ نیمکت ۱۰ است، چون با تنها نیمکت پر یعنی نیمکت ۱ بیشترین فاصله را دارد.
2 # # # # # # # # 1
10 9 8 7 6 5 4 3 2 1
برای کاراکتر کمکی ۳، نیمکت‌های ۵ و ۶ هر دو فاصله‌شان تا نزدیک‌ترین نیمکت پر ۳ است و نیمکتی با فاصله‌ی کمتر تا نزدیک‌ترین نیمکت پُرَش وجود ندارد. از بین این دو نیمکت ۵ استرس‌زداست چون شماره‌اش نسبت به نیمکت ۶ کوچکتر است.
2 # # # # 3 # # # 1
10 9 8 7 6 5 4 3 2 1
برای کاراکتر کمکی ۴، ۳ نیمکت وجود دارد که فاصله‌شان تا نزدیک‌ترین نیمکت پر ۱ باشد و بقیه‌ی نیمکت‌های خالی با نزدیک‌ترین نیمکت پر همسایه هستند (فاصله‌شان ۰ است). پس از بین آن ۳ نیمکت که شماره‌هایشان ۳، ۷ و ۸ است، نیمکت ۳ استرس‌زداست.
2 # # # # 3 # 4 # 1
10 9 8 7 6 5 4 3 2 1
ارسال پاسخ برای این سؤال