مش‌رجب و لگاریتم


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

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

توضیح تصویر

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

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

ورودی🔗

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

1n<2301 \leq n \lt 2^{30}

خروجی🔗

در خروجی باید یک عدد صحیح، که حاصل لگاریتم nn در مبنای ۲ است را به پایین رند کرده و چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

64
Plain text

خروجی نمونه ۱🔗

6
Plain text

در این حالت جواب ۶ است زیرا 26=642 ^ 6 = 64.

ورودی نمونه ۲🔗

255
Plain text

خروجی نمونه ۲🔗

7
Plain text

مقدار لگاریتم در این حالت 7.994353436867.99435343686 است زیرا 27.99435343686=2552 ^ {7.99435343686} = 255. از آنجا که باید عدد را به پایین رند کنیم، مقدار ۷ چاپ می‌شود.

الگو


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

یک شرکت برنامه‌نویسی با یک الگو از اعداد دودویی مواجه می‌شود. این الگو به این صورت است که در بعضی از خانه‌های آن علامت سوال گذاشته شده است و در بقیه‌ی خانه‌ها ۰ یا ۱ آمده است. هدف این است که در هر کدام خانه‌هایی که در آن‌ها علامت سوال آمده است ۰ یا ۱ نوشته شوند. این شرکت از شما می‌خواهد برنامه‌ای بنویسید که تمامی اعداد ممکن از این الگو را به صورت نزولی چاپ کنید.

دقت کنید ترتیب نزولی به این معنا است که بزرگترین عدد دودویی در ابتدا بیاید و هر عدد دودویی در این ترتیب از عدد قبلی کوچک‌تر باشد.

هم‌چنین، عدد دودویی xx از عدد دودویی yy بزرگتر است اگر و تنها اگر در اولین محل اختلاف این دو عدد، xx شامل ۱ و yy شامل ۰ باشد. برای مثال اگر x=1100x = 1100 و y=1011y = 1011 باشد؛ xx از yy بزرگ‌تر است، زیرا اولین محل اختلاف خانه‌ی دوم است که در xx آن خانه ۱ و در yy آن خانه ۰ است.

برای درک بهتر مسئله به مثال‌ها مراجعه کنید.

ورودی🔗

ورودی این برنامه یک الگوی دودویی است که ارقام نامشخص، با علامت سوال مشخص شده‌اند. اگر طول رشته را ll و تعداد علامت‌سوال‌ها را nn در نظر بگیریم، داریم:

1l1000 1 \le l \le 1000 1n10 1 \le n \le 10

خروجی🔗

خروجی برنامه‌ باید تمامی حالات ممکن برای الگو را به صورت نزولی در سطر‌های مختلف نمایش دهد.

مثال🔗

ورودی نمونه ۱🔗

?
Plain text

خروجی نمونه ۱🔗

1
0
Plain text

در این حالت جای علامت سوال هم می‌تواند یک و هم می‌تواند صفر بیاید. پس به ترتیب نزولی ابتدا ۱ و سپس ۰ می‌آید.

ورودی نمونه ۲🔗

1?101?
Plain text

خروجی نمونه ۲🔗

111011
111010
101011
101010
Plain text

دو علامت سوال داریم که هر کدام از آن‌ها می‌توانند صفر یا یک باشند، پس در کل ۴ حالت خواهیم داشت. اگر این ۴ حالت را به صورت نزولی چاپ کنیم به صورت بالا می‌شود، زیرا 111011111011 بزرگترین عدد و 101010101010 کوچکترین عدد است.

چند شنبه؟


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

جورج حافظه‌ی خوبی ندارد، به همین علت نمی‌تواند به خاطر آورد هر روز از سال چند‌شنبه بوده است. او صرفا می‌داند امروز چه تاریخی دارد و چند‌شنبه است.

برای جورج برنامه‌ای بنویسید که با گرفتن تاریخ و روز هفته‌ی امروز و گرفتن یک روز دلخواه دیگر، بتواند بگوید آن روز دلخواه در همین سال چند شنبه است.

ورودی🔗

ورودی شامل TT سناریو‌ی مختلف است.

در خط اول هر سناریو روز و ماه، و سپس روز هفته می‌آیند.

در خط دوم هر سناریو روزی که جورج می‌خواهد بداند چند شنبه‌ است می‌آید.

1T1000 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
Plain text

خروجی نمونه ۱🔗

1shanbe
5shanbe
5shanbe
jome
3shanbe
Plain text

ورودی نمونه ۲🔗

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
Plain text

خروجی نمونه ۲🔗

1shanbe
5shanbe
2shanbe
2shanbe
1shanbe
1shanbe
1shanbe
4shanbe
jome
jome
Plain text

رستوران‌داری


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

رضا یک رستوران تاسیس کرده که در طبقه‌ی آخر ساختمانی ضد زلزله قرار دارد. در صورت وقوع زلزله، ساختمان به چپ متمایل می‌شود رضا nn میز در رستوان دارد که میز ii ام در فاصله did_i متری درب ورودی قرار دارد (توجه کنید did_i می‌تواند منفی یا مثبت باشد؛ منفی یعنی میز سمت چپ و مثبت یعنی میز سمت راست درب قرار دارد).

مدیر ساختمان به رضا هشدار داده اگر ساختمان به چپ متمایل شود، میزها به چپ لیز می‌خورند مگر اینکه آن‌ها را به کف زمین بچسباند. در واقع هر میزی که به زمین چسبیده باشد حرکت نمی‌کند، در غیر این صورت اینقدر به چپ لیز می‌خورد تا به میز سمت چپش برسد (فرض کنید عرض میزها آنقدر کم است که چندین میز می‌تواند در یک فاصله از درب قرار گیرد). همچنین اگر در سمت چپ میزی که به زمین نچسبده، میزی نباشد، از پنجره به بیرون پرت می‌شود و رستوران بسته می‌شود. رضا تصمیم گرفته بعضی میزها را به زمین بچسباند و باقی را بعد از پایان زلزله هل داده و به جای اصلیشان برگرداند.

رضا به شاگردش پول می‌دهد تا کارها را انجام دهد. شاگرد به ازای هر یک متری که میزی را هل دهد، هزار تومان می‌گیرد. پول چسباندن میز ii ام به زمین، tit_i هزار تومان است. (که می‌تواند مثبت یا منفی باشد، در صورتی که tit_i منفی باشد، رضا از شاگردش بابت چسباندن میز پول می‌گیرد!)

شما باید برنامه‌ای بنویسید که در صورت وقوع زلزله، کمترین هزینه‌ی ممکن برای چسباندن و هل دادن میزها را حساب کند.

توجه داشته باشید نباید میزی از پنجره بیرون بیفتد وگرنه رستوران بسته و رضا ورشکسته می‌شود.

ورودی🔗

در اولین خط عدد nn یعنی تعداد میزها آمده است. 1n2 8001 \le n \le 2\ 800 در خط دوم، nn عدد می‌آید که did_i ها هستند. تضمین می‌شود هیچ دو میزی در ابتدا در یک نقطه قرار ندارند. (didj)(d_i \neq d_j)

در نهایت در خط سوم، nn عدد می‌آید که tit_i ها هستند.

230di,ti230-2^{30} \leq d_i, t_i \leq 2^{30}

خروجی🔗

در تنها خط خروجی، کمترین هزینه‌ی ممکن برای چسباندن و هل دادن میزها را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

3
0 2 10
5 6 13
Plain text

خروجی نمونه ۱🔗

17
Plain text

کافیست تنها چپ‌ترین میز چسبانده شود. در اینصورت ۵ هزار تومان هزینه‌ی چسباندن آن است و دو میز دیگر به سمت آن می‌لغزند و هزینه‌ی هل دادن آن‌ها به جایگاه اولشان، ۱۰ + ۲ = ۱۲ هزار تومان است و جمعا ۱۷ هزار تومان هزینه می‌کنیم.

ورودی نمونه ۲🔗

4
-4 -3 14 -1
100 -4 1 0
Plain text

خروجی نمونه ۲🔗

97
Plain text

در این مثال بهتر است همه‌ی میزها را به زمین بچسبانیم و در مجموع ۹۷ هزار تومان خرج می‌کنیم.

ورودی نمونه ۳🔗

4
6 2 5 3
1 7 100 2
Plain text

خروجی نمونه ۳🔗

12
Plain text

میز دوم باید چسبانده شود تا از پنجره بیرون نیفتد. اگر میز اول و دوم و چهارم را بچسبانیم ۱۰ هزار تومان هزینه می‌دهیم. ۲ هزار تومان هم هزینه‌ی هل دادن میز سوم است و در مجموع ۱۲ هزار تومان هزینه می‌کنیم.

ورودی نمونه ۴🔗

5
1 2 3 4 5
3 3 3 3 3
Plain text

خروجی نمونه ۴🔗

10
Plain text

بهترین جواب، چسباندن میز اول و چهارم است که باعث می‌شود سه میز دیگر لیز بخورند و هزینه‌ی هل دادن آن‌ها، ۴ هزار تومان و هزینه‌ی کل، ۱۰ هزار تومان شود.

ژنتیک


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

لئونارد در یک شرکت ژنتیکی استخدام شده که روی تغییر دنباله DNA گیاهان برای تولید محصولات بهتر کار می‌کند. یک ژن دنباله‌ای از حروف A، C، G و T‍ است.

در تحقیقات اخیر مشخص شده که اگر ژن سیب، شامل ژن tt به صورت یک زیر رشته‌ باشد، ماندگاری بیشتری خواهد داشت. برای رسیدن به این هدف می‌خواهیم تعدادی حرف در مکان‌های مشخصی از ژن سیب تزریق کنیم تا در نهایت ژن نهایی شامل ژن tt شود (ژن tt را به عنوان زیررشته داشته باشد).

تزریق هر یک از چهار کاراکتر هزینه‌ی خاصی دارد. وظیفه لئونارد یافتن مکان‌های تزریق ژن و کاراکتر‌های هر تزریق است به‌طوری که در نهایت هزینه کمینه شود. به او کمک کنید تا کمینه هزینه را محاسبه کند.

ورودی🔗

در خط اول یک رشته از nn کاراکتر داریم که ژن سیب را مشخص می کند. خط دوم شامل mm کاراکتر است که رشته‌ی tt را مشخص می کند. کاراکتر‌ها حروف انگلیسی بزرگ هستند. خط سوم شامل چهار عدد صحیح است که به ترتیبِ A، C، G و T‍ هزینه اضافه کردن هر کاراکتر را مشخص می کند.

1n10 0001 \le n \le 10\ 000

1m50001 \le m \le 5000

0ai10000 \le a_{i} \le 1000

خروجی🔗

در یک خط کمینه هزینه را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

TATA
CACA
3 0 3 0
Plain text

خروجی نمونه ۱🔗

3
Plain text

در این مثال هزینه‌ی اضافه کردن A و G برابر با ۳ و هزینه‌ی اضافه کردن C و T برابر با صفر است. لئونارد می‌تواند قبل از آخرین A حرف C و بعد از آن حرف‌های CA را اضافه کند و در مجموع ۳ واحد هزینه می‌کند.

ورودی نمونه ۲🔗

TCGCGAG
TGCAG
10 10 15 15
Plain text

خروجی نمونه ۲🔗

25
Plain text

در این مثال هزینه‌ی اضافه کردن A و C برابر با ۱۰ و هزینه‌ی اضافه کردن G و T برابر با ۱۵ است. لئونارد می‌تواند قبل از دومین G حرف T و بعد از آن حرف C را اضافه کند و به رشته‌ی ‍‍TCGCTGCAG برسد که TGCAG را به عنوان زیر رشته دارد و در مجموع ۲۵ واحد هزینه می‌کند.

XO پیشرفته


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

دو نفر در حال بازی XO پیشرفته هستند. بازی در یک جدول n×nn \times n انجام می‌شود. هر نفر در نوبت خود یکی از خانه‌های جدول را پر می‌کند. نفر اول با X و نفر دوم با O. خانه های خالی با - نمایش داده می‌شود. برنده زمانی مشخص می‌شود که حداقل aa خانه یکسان متوالی به صورت سطری با ستونی یا قطری قرار گیرد.

جدول یکی از مراحل بازی به دست ما رسیده و می خواهیم مرحله بعد بازی را پیش بینی کنیم!

  • اگر بازی تا کنون به اتمام رسیده، Finished چاپ کنید.
  • اگر نفر اول می تواند با یک حرکت بازی را ببرد، X چاپ کنید.
  • اگر نفر دوم می تواند با یک حرکت بازی را ببرد، O چاپ کنید.
  • اگر هر دو می‌توانند با یک حرکت بازی را ببرند، Both چاپ کنید.
  • اگر هیچکدام از موارد بالا نیست، None چاپ کنید.

ورودی🔗

خط اول ورودی دو عدد nn و aa با فاصله از هم آمده است. 2an1002 \le a \le n \le 100 در nn خط بعدی جدول بازی آمده است. خانه های خالی با - مشخص شده است.

خروجی🔗

خروجی برنامه طبق توضیحات یکی از عبارات Finished، X، O، Both یا None است.

مثال🔗

ورودی نمونه ۱🔗

3 3
X-O
-XO
---
Plain text

خروجی نمونه ۱🔗

Both
Plain text

جفت بازیکن‌ها با علامت زدن خانه‌ی آخر سطر سوم می‌توانند برنده شوند.

ورودی نمونه ۲🔗

4 3
O-OO
X---
-X-O
-XXO
Plain text

خروجی نمونه ۲🔗

Finished
Plain text

۳ تا x به صورت قطری در سطر دوم تا چهارم قرار دارد و یعنی بازی تا الان پایان یافته است.

ورودی نمونه ۳🔗

3 3
XOO
X-O
--X
Plain text

خروجی نمونه ۳🔗

X
Plain text

نفر اول با گذاشتن x در خانه‌ی اول سطر سوم می‌تواند برنده شود ولی نفر دوم نمی‌تواند برنده شود.

ورودی نمونه ۴🔗

4 4
X--X
OO--
X---
---X
Plain text

خروجی نمونه ۴🔗

None
Plain text

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