• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

مش‌رجب که کودکی ۶ ساله است به تازگی با مفهوم لگاریتم در پایه‌ی ۲ آشنایی پیدا کرده، اما فعلاً نمی‌تواند آن را محاسبه کند.

برنامه‌ای بنویسید که با ورودی گرفتن یک عدد طبیعی، لگاریتم آن در پایه‌ی ۲ را حساب کند. از آنجایی که مش‌رجب با اعداد اعشاری آشنا نیست، جواب را برای او به پایین رند کنید.

دقت کنید لگاریتم عدد $x$ در پایه‌ی ۲ عددی مانند $y$ است که داشته باشیم: $2 ^ y = x$ برای مطالعه‌ی بیشتر درباره‌ی لگاریتم، می‌توانید این پیوند را مطالعه کنید.

ورودی🔗

در تنها خط ورودی، عدد صحیح $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

هیچ کدام از بازیکنان با یک حرکت نمی‌توانند برنده شوند.