+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مش‌رجب که کودکی ۶ ساله است به تازگی با مفهوم لگاریتم در پایه‌ی ۲ آشنایی پیدا کرده، اما فعلاً نمی‌تواند آن را محاسبه کند.  برنامه‌ای بنویسید که با ورودی گرفتن یک عدد طبیعی، لگاریتم آن در پایه‌ی ۲ را حساب کند. از آنجایی که مش‌رجب با اعداد اعشاری آشنا نیست، جواب را برای او به پایین رند کنید. دقت کنید لگاریتم عدد $x$ در پایه‌ی ۲ عددی مانند $y$ است که داشته باشیم: $$ 2 ^ y = x $$ برای مطالعه‌ی بیشتر درباره‌ی لگاریتم، می‌توانید [این پیوند](https://fa.wikipedia.org/wiki/%D9%84%DA%AF%D8%A7%D8%B1%DB%8C%D8%AA%D9%85) را مطالعه کنید. # ورودی در تنها خط ورودی، عدد صحیح $n$ که باید لگاریتم آن در پایه‌ی ۲ محاسبه شود آمده است. $$1 \leq n \lt 2^{30}$$ # خروجی در خروجی باید یک عدد صحیح، که حاصل لگاریتم $n$ در مبنای ۲ است را به پایین رند کرده و چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 64 ``` ## خروجی نمونه ۱ ``` 6 ``` در این حالت جواب ۶ است زیرا $2 ^ 6 = 64$. ## ورودی نمونه ۲ ``` 255 ``` ## خروجی نمونه ۲ ``` 7 ``` مقدار لگاریتم در این حالت $7.99435343686$ است زیرا $2 ^ {7.99435343686} = 255$. از آنجا که باید عدد را به پایین رند کنیم، مقدار ۷ چاپ می‌شود.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- یک شرکت برنامه‌نویسی با یک الگو از اعداد دودویی مواجه می‌شود. این الگو به این صورت است که در بعضی از خانه‌های آن علامت سوال گذاشته شده است و در بقیه‌ی خانه‌ها ۰ یا ۱ آمده است. هدف این است که در هر کدام خانه‌هایی که در آن‌ها علامت سوال آمده است ۰ یا ۱ نوشته شوند. این شرکت از شما می‌خواهد برنامه‌ای بنویسید که تمامی اعداد ممکن از این الگو را به صورت نزولی چاپ کنید. دقت کنید ترتیب نزولی به این معنا است که بزرگترین عدد دودویی در ابتدا بیاید و هر عدد دودویی در این ترتیب از عدد قبلی کوچک‌تر باشد. هم‌چنین، عدد دودویی $x$ از عدد دودویی $y$ بزرگتر است اگر و تنها اگر در اولین محل اختلاف این دو عدد، $x$ شامل ۱ و $y$ شامل ۰ باشد. برای مثال اگر $x = 1100$ و $y = 1011$ باشد؛ $x$ از $y$ بزرگ‌تر است، زیرا اولین محل اختلاف خانه‌ی دوم است که در $x$ آن خانه ۱ و در $y$ آن خانه ۰ است. برای درک بهتر مسئله به مثال‌ها مراجعه کنید. # ورودی ورودی این برنامه یک الگوی دودویی است که ارقام نامشخص، با علامت سوال مشخص شده‌اند. اگر طول رشته را $l$ و تعداد علامت‌سوال‌ها را $n$ در نظر بگیریم، داریم: $$ 1 \le l \le 1000 $$$$ 1 \le n \le 10 $$ # خروجی خروجی برنامه‌ باید تمامی حالات ممکن برای الگو را به صورت نزولی در سطر‌های مختلف نمایش دهد. # مثال ## ورودی نمونه ۱ ``` ? ``` ## خروجی نمونه ۱ ``` 1 0 ``` در این حالت جای علامت سوال هم می‌تواند یک و هم می‌تواند صفر بیاید. پس به ترتیب نزولی ابتدا ۱ و سپس ۰ می‌آید. ## ورودی نمونه ۲ ``` 1?101? ``` ## خروجی نمونه ۲ ``` 111011 111010 101011 101010 ``` دو علامت سوال داریم که هر کدام از آن‌ها می‌توانند صفر یا یک باشند، پس در کل ۴ حالت خواهیم داشت. اگر این ۴ حالت را به صورت نزولی چاپ کنیم به صورت بالا می‌شود، زیرا $111011$ بزرگترین عدد و $101010$ کوچکترین عدد است.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- جورج حافظه‌ی خوبی ندارد، به همین علت نمی‌تواند به خاطر آورد هر روز از سال چند‌شنبه بوده است. او صرفا می‌داند امروز چه تاریخی دارد و چند‌شنبه است. برای جورج برنامه‌ای بنویسید که با گرفتن تاریخ و روز هفته‌ی امروز و گرفتن یک روز دلخواه دیگر، بتواند بگوید آن روز دلخواه **در همین سال** چند شنبه است. # ورودی ورودی شامل $T$ سناریو‌ی مختلف است. در خط اول هر سناریو روز و ماه، و سپس روز هفته می‌آیند. در خط دوم هر سناریو روزی که جورج می‌خواهد بداند چند شنبه‌ است می‌آید. $$ 1 \le T \le 1000 $$ نام ماه‌های سال به صورت `Farvardin`، `Ordibehesht`، `Khordad`، `Tir`، `Mordad`، `Shahrivar`، `Mehr`، `Aban`، `Azar`، `Dey`، `Bahman` و `Esfand` در ورودی داده می‌شوند. همچنین ۶ ماه اول سال ۳۱ روز، ۵ ماه بعدی ۳۰ روز و ماه آخر ۲۹ روز دارد. (سال کبیسه نداریم.) نام روز‌های هفته نیز به صورت `shanbe`، `1shanbe`، `2shanbe`، `3shanbe`، `4shanbe`، `5shanbe` و `jome` ورودی داده می‌شوند، و باید به همین صورت خروجی داده شوند. # خروجی به ازای هر سناریو باید یک خط چاپ کنید که نشان می‌دهد آن روز، چه روزی از هفته است. **توجه کنید سیستم داوری نسبت به بزرگ و کوچک بودن حروف حساس است.** # مثال ## ورودی نمونه ۱ ``` 5 11 Khordad jome 18 Azar 18 Khordad 5shanbe 16 Shahrivar 25 Khordad 3shanbe 12 Esfand 15 Ordibehesht 1shanbe 1 Azar 23 Tir 3shanbe 22 Ordibehesht ``` ## خروجی نمونه ۱ ``` 1shanbe 5shanbe 5shanbe jome 3shanbe ``` ## ورودی نمونه ۲ ``` 10 2 Bahman 4shanbe 19 Khordad 29 Azar 5shanbe 13 Dey 29 Shahrivar jome 10 Tir 7 Mordad shanbe 16 Mordad 29 Aban 4shanbe 24 Shahrivar 31 Khordad shanbe 21 Ordibehesht 25 Farvardin 5shanbe 25 Ordibehesht 24 Dey 1shanbe 5 Mehr 26 Tir shanbe 12 Azar 15 Esfand 2shanbe 25 Shahrivar ``` ## خروجی نمونه ۲ ``` 1shanbe 5shanbe 2shanbe 2shanbe 1shanbe 1shanbe 1shanbe 4shanbe jome jome ```

+ محدودیت زمان: ۱.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- رضا یک رستوران تاسیس کرده که در طبقه‌ی آخر ساختمانی ضد زلزله قرار دارد. در صورت وقوع زلزله، ساختمان به چپ متمایل می‌شود رضا $n$ میز در رستوان دارد که میز $i$ ام در فاصله $d_i$ متری درب ورودی قرار دارد (توجه کنید $d_i$ می‌تواند منفی یا مثبت باشد؛ منفی یعنی میز سمت چپ و مثبت یعنی میز سمت راست درب قرار دارد). مدیر ساختمان به رضا هشدار داده اگر ساختمان به چپ متمایل شود، میزها به چپ لیز می‌خورند مگر اینکه آن‌ها را به کف زمین بچسباند. در واقع هر میزی که به زمین چسبیده باشد حرکت نمی‌کند، در غیر این صورت اینقدر به چپ لیز می‌خورد تا به میز سمت چپش برسد (فرض کنید عرض میزها آنقدر کم است که چندین میز می‌تواند در یک فاصله از درب قرار گیرد). همچنین اگر در سمت چپ میزی که به زمین نچسبده، میزی نباشد، از پنجره به بیرون پرت می‌شود و رستوران بسته می‌شود. رضا تصمیم گرفته بعضی میزها را به زمین بچسباند و باقی را بعد از پایان زلزله هل داده و به جای اصلیشان برگرداند. رضا به شاگردش پول می‌دهد تا کارها را انجام دهد. شاگرد به ازای هر یک متری که میزی را هل دهد، هزار تومان می‌گیرد. پول چسباندن میز $i$ ام به زمین، $t_i$ هزار تومان است. (که می‌تواند مثبت یا منفی باشد، در صورتی که $t_i$ منفی باشد، رضا از شاگردش بابت چسباندن میز پول می‌گیرد!) شما باید برنامه‌ای بنویسید که در صورت وقوع زلزله، کمترین هزینه‌ی ممکن برای چسباندن و هل دادن میزها را حساب کند. توجه داشته باشید نباید میزی از پنجره بیرون بیفتد وگرنه رستوران بسته و رضا ورشکسته می‌شود. # ورودی در اولین خط عدد $n$ یعنی تعداد میزها آمده است. $$1 \le n \le 2\ 800$$ در خط دوم، $n$ عدد می‌آید که $d_i$ ها هستند. تضمین می‌شود هیچ دو میزی در ابتدا در یک نقطه قرار ندارند. $$(d_i \neq d_j)$$ در نهایت در خط سوم، $n$ عدد می‌آید که $t_i$ ها هستند. $$-2^{30} \leq d_i, t_i \leq 2^{30}$$ # خروجی در تنها خط خروجی، کمترین هزینه‌ی ممکن برای چسباندن و هل دادن میزها را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 0 2 10 5 6 13 ``` ## خروجی نمونه ۱ ``` 17 ``` کافیست تنها چپ‌ترین میز چسبانده شود. در اینصورت ۵ هزار تومان هزینه‌ی چسباندن آن است و دو میز دیگر به سمت آن می‌لغزند و هزینه‌ی هل دادن آن‌ها به جایگاه اولشان، ۱۰ + ۲ = ۱۲ هزار تومان است و جمعا ۱۷ هزار تومان هزینه می‌کنیم. ## ورودی نمونه ۲ ``` 4 -4 -3 14 -1 100 -4 1 0 ``` ## خروجی نمونه ۲ ``` 97 ``` در این مثال بهتر است همه‌ی میزها را به زمین بچسبانیم و در مجموع ۹۷ هزار تومان خرج می‌کنیم. ## ورودی نمونه ۳ ``` 4 6 2 5 3 1 7 100 2 ``` ## خروجی نمونه ۳ ``` 12 ``` میز دوم باید چسبانده شود تا از پنجره بیرون نیفتد. اگر میز اول و دوم و چهارم را بچسبانیم ۱۰ هزار تومان هزینه می‌دهیم. ۲ هزار تومان هم هزینه‌ی هل دادن میز سوم است و در مجموع ۱۲ هزار تومان هزینه می‌کنیم. ## ورودی نمونه ۴ ``` 5 1 2 3 4 5 3 3 3 3 3 ``` ## خروجی نمونه ۴ ``` 10 ``` بهترین جواب، چسباندن میز اول و چهارم است که باعث می‌شود سه میز دیگر لیز بخورند و هزینه‌ی هل دادن آن‌ها، ۴ هزار تومان و هزینه‌ی کل، ۱۰ هزار تومان شود.

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- لئونارد در یک شرکت ژنتیکی استخدام شده که روی تغییر دنباله *DNA* گیاهان برای تولید محصولات بهتر کار می‌کند. یک ژن دنباله‌ای از حروف `A`، `C`، `G` و `T‍` است. در تحقیقات اخیر مشخص شده که اگر ژن سیب، شامل ژن $t$ به صورت یک زیر رشته‌ باشد، ماندگاری بیشتری خواهد داشت. برای رسیدن به این هدف می‌خواهیم تعدادی حرف در مکان‌های مشخصی از ژن سیب تزریق کنیم تا در نهایت ژن نهایی شامل ژن $t$ شود (ژن $t$ را به عنوان زیررشته داشته باشد). تزریق هر یک از چهار کاراکتر هزینه‌ی خاصی دارد. وظیفه لئونارد یافتن مکان‌های تزریق ژن و کاراکتر‌های هر تزریق است به‌طوری که در نهایت هزینه کمینه شود. به او کمک کنید تا کمینه هزینه را محاسبه کند. # ورودی در خط اول یک رشته از $n$ کاراکتر داریم که ژن سیب را مشخص می کند. خط دوم شامل $m$ کاراکتر است که رشته‌ی $t$ را مشخص می کند. کاراکتر‌ها حروف انگلیسی بزرگ هستند. خط سوم شامل چهار عدد صحیح است که به ترتیبِ `A`، `C`، `G` و `T‍` هزینه اضافه کردن هر کاراکتر را مشخص می کند. $$1 \le n \le 10\ 000$$ $$1 \le m \le 5000$$ $$0 \le a_{i} \le 1000$$ # خروجی در یک خط کمینه هزینه را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` TATA CACA 3 0 3 0 ``` ## خروجی نمونه ۱ ``` 3 ``` در این مثال هزینه‌ی اضافه کردن `A` و `G` برابر با ۳ و هزینه‌ی اضافه کردن `C` و `T` برابر با صفر است. لئونارد می‌تواند قبل از آخرین `A` حرف `C` و بعد از آن حرف‌های `CA` را اضافه کند و در مجموع ۳ واحد هزینه می‌کند. ## ورودی نمونه ۲ ``` TCGCGAG TGCAG 10 10 15 15 ``` ## خروجی نمونه ۲ ``` 25 ``` در این مثال هزینه‌ی اضافه کردن `A` و `C` برابر با ۱۰ و هزینه‌ی اضافه کردن `G` و `T` برابر با ۱۵ است. لئونارد می‌تواند قبل از دومین `G` حرف `T` و بعد از آن حرف `C` را اضافه کند و به رشته‌ی ‍‍`TCGCTGCAG` برسد که `TGCAG` را به عنوان زیر رشته دارد و در مجموع ۲۵ واحد هزینه می‌کند.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- دو نفر در حال بازی *XO* پیشرفته هستند. بازی در یک جدول $n \times n$ انجام می‌شود. هر نفر در نوبت خود یکی از خانه‌های جدول را پر می‌کند. نفر اول با `X` و نفر دوم با `O`. خانه های خالی با `-` نمایش داده می‌شود. برنده زمانی مشخص می‌شود که حداقل $a$ خانه یکسان متوالی به صورت سطری با ستونی یا قطری قرار گیرد. جدول یکی از مراحل بازی به دست ما رسیده و می خواهیم مرحله بعد بازی را پیش بینی کنیم! + اگر بازی تا کنون به اتمام رسیده، `Finished` چاپ کنید. + اگر نفر اول می تواند با یک حرکت بازی را ببرد، `X` چاپ کنید. + اگر نفر دوم می تواند با یک حرکت بازی را ببرد، `O` چاپ کنید. + اگر هر دو می‌توانند با یک حرکت بازی را ببرند، `Both` چاپ کنید. + اگر هیچکدام از موارد بالا نیست، `None` چاپ کنید. # ورودی خط اول ورودی دو عدد $n$ و $a$ با فاصله از هم آمده است. $$2 \le a \le n \le 100$$ در $n$ خط بعدی جدول بازی آمده است. خانه های خالی با `-` مشخص شده است. # خروجی خروجی برنامه طبق توضیحات یکی از عبارات `Finished`، `X`، `O`، `Both` یا `None` است. # مثال ## ورودی نمونه ۱ ``` 3 3 X-O -XO --- ``` ## خروجی نمونه ۱ ``` Both ``` جفت بازیکن‌ها با علامت زدن خانه‌ی آخر سطر سوم می‌توانند برنده شوند. ## ورودی نمونه ۲ ``` 4 3 O-OO X--- -X-O -XXO ``` ## خروجی نمونه ۲ ``` Finished ``` ۳ تا `x` به صورت قطری در سطر دوم تا چهارم قرار دارد و یعنی بازی تا الان پایان یافته است. ## ورودی نمونه ۳ ``` 3 3 XOO X-O --X ``` ## خروجی نمونه ۳ ``` X ``` نفر اول با گذاشتن `x` در خانه‌ی اول سطر سوم می‌تواند برنده شود ولی نفر دوم نمی‌تواند برنده شود. ## ورودی نمونه ۴ ``` 4 4 X--X OO-- X--- ---X ``` ## خروجی نمونه ۴ ``` None ``` هیچ کدام از بازیکنان با یک حرکت نمی‌توانند برنده شوند.