شارژ موبایل


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

باتری تلفن همراه مرد مالیاتچی‌ تمام شده‌است.

می‌دانیم تلفن مرد مالیاتچی برای اینکه از ii درصد شارژ به i+1i + 1 درصد برسد i+1i + 1 دقیقه زمان می‌برد.

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

ورودی🔗

در یک خط عدد kk به شما داده می‌شود.

1k100 1 \le k \le 100

خروجی🔗

در یک خط مجموع دقایقی که طول می‌کشد را چاپ کنید.

مثال🔗

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

1
Plain text

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

1
Plain text

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

3
Plain text

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

6
Plain text

سوال زرد


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

مهدی که از کدزدن خسته شده‌است، به تازگی به رشته‌ی صنایع علاقه پیدا کرده است. به همین دلیل تصمیم گرفته است تا در مورد این رشته تحقیق کند. او به افراد مختلفی مراجعه می‌کند و هرکدام یک مقداری اطلاعات به او می‌دهند. او به اندازه‌ی مقدار اطلاعاتی که از اشخاص می‌گیرد متعجب می‌شود. مثلا اگر یک عدد اطلاعات بگیرد می‌گوید Wow!، اگر دوتا اطلاعات بگیرد می‌گویدWoow! و به همین شکل مقدار کشیدن کلمه(تعداد o ها) زیاد می‌شود. حالا شما باید بگویید که اگر یک نفر به اندازه‌ی nn به مهدی اطلاعات بدهد، ما باید انتظار چه کلمه‌ای را از او داشته باشیم.

عکس زرد

ورودی🔗

در تنها سطر ورودی یک عدد طبیعی nn به شما داده شده است که نمایانگر مقدار اطلاعات داده‌شده به مهدی است. 1n10 1 \le n \le 10

خروجی🔗

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

مثال🔗

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

1
Plain text

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

Wow!
Plain text

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

2
Plain text

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

Woow!
Plain text

همه‌ی زیرمجموعه‌ها


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

برنامه‌ای بنویسید که با ورودی گرفتن عدد nn، همه‌ی زیرمجموعه‌های مجموعه‌ی {1,2,3,...,n}\{ 1, 2, 3, ..., n \} را چاپ کند. این زیرمجموعه‌ها را به ترتیب الفبایی مرتب کنید؛ یعنی ابتدا عناصر هر زیرمجموعه را مرتب کنید و سپس به آن‌ها مانند کلمات نگاه کنید و به ترتیبی که در لغت‌نامه می‌آیند مرتب‌شان کنید.

تلاش کنید که این کار را تنها به وسیله‌ی تابع بازگشتی انجام دهید؛ یعنی طوری پیاده‌سازی کنید که این مجموعه‌ها به همین ترتیب تولید و چاپ شوند. (به جای این که ابتدا همه را تولید کرده و سپس مرتب کنید.)

برای آشنایی با قالب خروجی دادن به نمونه‌ها توجه کنید.

ورودی🔗

ورودی تنها شامل یک خط است که در آن یک عدد طبیعی nn آمده است. 1n151 \le n \le 15

خروجی🔗

خروجی برنامه‌ی شما باید شامل 2n2^n خط باشد که در هر خط یک زیرمجموعه چاپ شود.

مثال🔗

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

1
Plain text

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

{}
{1}
Plain text

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

3
Plain text

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

{}
{1}
{1, 2}
{1, 2, 3}
{1, 3}
{2}
{2, 3}
{3}
Plain text

بتایپ


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

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

ورودی🔗

در تنها خط ورودی یک رشته SS آمده‌است که همان رشته نوشته‌شده توسط پاشا است.

1S100 0001 \le |S| \le 100\ 000

  • رشته SS تنها از حروف کوچک انگلیسی و = تشکیل شده‌است.

خروجی🔗

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

مثال🔗

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

sall=am
Plain text

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

salam
Plain text

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

testtwoo===wo
Plain text

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

testtwo
Plain text

خواب پوپک


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

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

پوپک می‌داند که او در خوابش دو کیسه تیله داشته است که در هر کیسه حداقل یک تیله بوده است. پوپک می‌داند که تعداد تیله‌های کیسه اول مقسوم‌علیهی از عدد aa بوده و تعداد تیله‌های کیسه دوم مقسوم علیهی از عدد bb بوده است. همچنین پوپک به یاد دارد که دو کیسه‌اش خیلی سنگین نبودند و در مجموع حداکثر xx تیله در دو کیسه قرار داشته است.

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

در همین هنگام توک یه دل نه صد دل عاشق پوپک می‌شود ...

ورودی🔗

در تنها خط ورودی به ترتیب سه عدد aa و bb و xx آمده است.

1a,b1 0001 \le a, b\le 1\ 000 2x1 0002 \le x \le 1\ 000

خروجی🔗

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

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

2 2 2
Plain text

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

1
Plain text

تنها حالت ممکن این است که در هر دو کیسه دقیقا 11 تیله قرار گرفته باشد.

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

7 7 14
Plain text

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

4
Plain text

چهار حالت مختلف برای تعداد تیله‌های در کیسه (1,1)(1, 1) و (1,7)(1, 7) و (7,1)(7, 1) و (7,7)(7 , 7) هستند.

اعداد فیثاغورثی


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

برنامه‌ای بنویسید که سه عدد صحیح مثبت را به عنوان ورودی از کاربر دریافت کند و در صورتی که امکان ساخت مثلث قائم الزاویه با طول اضلاع داده شده وجود داشته باشد YES و در غیر این صورت NO چاپ کند.

ورودی🔗

۳ عدد صحیح در ۳ خط ورودی به شما داده می‌شود.

خروجی🔗

چنانچه می‌توانیم با ۳ عدد ورودی مثلث قائم الزاویه‌ای بسازیم YES در غیر اینصورت NO چاپ کنید.

مثال🔗

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

5
4
3
Plain text

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

YES
Plain text

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

8
7
10
Plain text

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

NO
Plain text

جشن هدیه‌ها


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

زانا سالی یک بار یک جشن خاص برگزار می‌کند و تعدادی از دوستانش را به این جشن دعوت می‌کند. اسم این جشن «جشن هدیه‌ها» است! هر فردی که در این جشن شرکت می‌کند مقداری پول به همراه خود دارد و به تعدادی از دوستانش هدیه می‌دهد. روش هدیه دادن در این جشن کمی عجیب است! هر کدام از افراد یک لیست هدیه دارد که در آن لیست، نام تعدادی از دوستانش که در جشن شرکت کرده‌اند نوشته شده است و تمام پولی که همراه دارد را بین افراد این لیست به طور مساوی تقسیم می‌کند و این پول را به آنها هدیه می‌دهد! چون پول اعشاری (کوچکتر از یک) نداریم ، این تقسیم‌ها تقسیم صحیح هستند و اگر تقسیم پول بین اعضای لیست باقیمانده‌ای داشته باشد ، فرد هدیه دهنده این باقیمانده را برای خود نگه می‌دارد. به طور مثال اگر ساینا ۱۱ واحد پول داشته باشد و در لیست او فقط سه نفر باشند ، به هر کدام از آنها ۳ واحد پول میدهد و ۲ واحد از پول خود را برای خود نگه می‌دارد.

حال شما برنامه‌ای بنویسید که پس از گرفتن اسامی شرکت کنندگان، مقدار پول اولیه‌ی هر کدام و لیست هدیه هر کس، مشخص کند که هرکسی چقدر سود یا زیان کرده است!

ورودی🔗

  • خط 1 : عدد n که برابر است با تعداد شرکت کنندگان در جشن.
  • خط 2 تا n+1 : در هر خط اسم یکی از شرکت کنندگان.
  • خط n+1 الی آخر : از این خط به بعد ورودی به n دسته تقسیم می‌شود که هرکدام مطابق زیر است: خط اول نام فردی که قرار است هدیه بدهد. در خط دوم دو عدد می‌آید: عدد اول مقدار پول آن فرد، عدد دوم (k) تعداد افراد موجود در لیست هدیه‌ی آن فرد در k خط بعدی در هر خط نام یکی از افراد موجود در لیست هدیه‌ی آن فرد.

می‌توانید فرض کنید نام هر دو نفر از افراد شرکت‌کننده در جشن متمایز است و 2n10 2 \leq n \leq 10

خروجی🔗

در خروجی باید n خط چاپ کنید که در هر ابتدای هر خط نام هر شخص و بعد از آن مقدار سود او آورده شود. (اگر آن شخص ضرر کرده است، باید منفی مقدار ضرر چاپ شود.) ترتیب نام‌ها در خروجی باید مانند ترتیب نام‌ها در خطوط 2 تا n+1 ورودی باشد.

مثال🔗

ورودی نمونه🔗

5
dave
laura
owen
vick
amr
dave
200 3
laura
owen
vick
owen
500 1
dave
amr
150 2
vick
owen
laura
0 2
amr
vick
vick
0 0
Plain text

خروجی نمونه🔗

dave 302
laura 66
owen -359
vick 141
amr -150
Plain text

تاکسیک‌علیش


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

علیش که دیگه هدفی واسه زندگی‌کردن نداره تصمیم گرفته مریض‌شه. اما آقا مجید (که داره دکتر می‌شه) بهش گفته که باید nn تا قرص بخوره. علیش هم که به این سادگی نمی‌خواد قبول کنه mm تا شرط واسه قرص خوردن داره که هر شرط شامل aia_i و bib_i است که یعنی قرص aia_iام رو باید قبل قرص bib_iام بخوره. هم‌چنین nn شرط دیگه هم داره که قرص iiام باید حداقل lil_iامین و حداکثر rir_iامین قرصی باشه که می‌خوره. یه ترتیبی به علیش بدید که اگه به این ترتیب قرصاشو بخوره همه شرط‌ها برقرار باشه.

ورودی🔗

در خط اول nn و mm آمده که با یک فاصله از هم جدا شده‌اند.

در nn خط بعدی lil_i و rir_i ها آمده‌است.

در mm خط بعدی دو عدد aia_i و bib_i آمده که با فاصله از هم جدا شده اند و یعنی قرص aia_iام باید قبل قرص bib_iام خورده شود.

1n200 0001 \le n \le 200\ 000 1m300 0001 \le m \le 300\ 000 1lirin1 \le l_i \le r_i \le n 1aibin 1 \le a_i \le b_i \le n

خروجی🔗

در خروجی nn خط که شامل جایگشتی از اعداد ۱ تا nn است و تمام شروط در آن برقرار است چاپ شود. اگر چند جواب وجود داشت یکی را به دلخواه چاپ نمایید. اگر ترتیبی وجود نداشت که همه شرط‌ها در آن برقرار باشند -1 چاپ کنید.

مثال🔗

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

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

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

-1
Plain text

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

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

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

1
2
3
4
Plain text

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

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

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

1
4
3
2
Plain text

قطار کامیابی


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

بعد از مدت‌ها که لیته توانست با موفقیت چالش خوش‌اندام شدن را تا حدودی پشت سر بگذارد، فیته نیز کم‌کم به او علاقه‌مند شد و امروز آن‌ها می‌خواهند به اولین قرار خود بروند. لیته در نقطه aa شهر زندگی می‌کند و فیته نقطه bb را برای اولین قرار انتخاب کرده‌است.

در این شهر دو نوع قطار برای جا‌به‌جایی وجود دارد:

  • نوع اول: نقطه xx و x+1x + 1 را با یک مسیر دو طرفه به هم متصل می‌کند. ( به ازای هر xx صحیح )
  • نوع دوم: نقطه k×xk \times x و k×(x+1)k \times (x +1) را با یک مسیر دوطرفه به هم متصل می‌کند. ( به ازای هر xx صحیح و kk داده شده در ورودی )

کوتاه‌ترین مسیر

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

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

ورودی🔗

ورودی تنها شامل یک سطر است که در آن به ترتیب سه عدد صحیح kk و aa و bb با فاصله از هم آمده‌است. 109a,b109-10^9 \le a, b \le 10^9 1k1091 \le k \le 10^9

خروجی🔗

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

ورودی نمونه🔗

4 1 10
Plain text

خروجی نمونه🔗

5
Plain text

نمونه‌ی بالا همان تصویر موجود در صورت سوال است؛ مسیر بهینه با ۵ سفر در تصویر پررنگ شده است.

ترور


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

«مِسِریکس» از گرمایش جهانی به ستوه آمده و قصد دارد از خلاّقیّتش در زمینه‌ی بحران محیط زیست استفاده کند؛ امّا...

به تازگی پلیس با خبر شده که قرار است حمله‌ای تروریستی به شهر بشود. فعلا تروریست‌ها در خانه‌هایی در کنار خیابان آزادی پنهان شده‌اند. در کنار خیابان آزادی nn خانه وجود دارد و در هر خانه حداکثر یک تروریست زندگی می‌کند.

برای مهار این حمله‌ی تروریستی و دستگیری تروریست‌ها، mm پلیس آن خانه‌ها را زیر نظر گرفته‌اند. پلیس ii-ام خانه‌های lil_i تا rir_i را زیر نظر گرفته‌است. می‌دانیم اگر در بازه‌ی تحت نظر یک پلیس بیش از یک تروریست زندگی کند، پلیس‌ها مشکوک شده و تروریست‌ها را دستگیر می‌کنند.

مسریکس که از این ماجرا خبردار شده است، با خودش فکر می‌کند شاید بیشینه‌ی تعداد تروریست‌هایی که در این خانه‌ها می‌توانند زندگی کنند(بدون آن که دستگیر شوند) می‌تواند پارامتری موثّر در بحران محیط زیست باشد. پس از شما می‌خواهد که این مقدار را برای او محاسبه کنید.

ورودی🔗

در سطر اوّل ورودی به ترتیب دو عدد nn و mm می‌آید.

در سطر ii-ام از mm سطر بعد، دو عدد lil_i و rir_i آمده‌است که نشان‌دهنده‌ی بازه‌ی خانه‌هایی است که پلیس ii-ام زیر نظر گرفته است.

1lirin1 \le l_i \le r_i \le n 1n,m100 0001 \le n, m \le 100\ 000

خروجی🔗

در تنها سطر خروجی حداکثر تعداد تروریست‌هایی را چاپ کنید که می‌توانند در این خانه‌ها زندگی کنند و دستگیر نشوند.

مثال🔗

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

5 2
1 3
2 4
Plain text

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

3
Plain text

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

6 3
2 4
3 5
2 5
Plain text

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

3
Plain text

مسئله گراف اعداد


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

مسئله‌ای به شما داده شده است که بایستی به صورت یک مسئله CSPCSP آن را فرموله کرده و پیاده‌سازی نمایید. فرض کنید گرافی در اختیار داریم که گره‌های آن می‌توانند هر یک از اشکال مثلث، مربع، پنج ضلعی، شش ضلعی و یا دایره باشند. می‌خواهیم به هر گره از این گراف، یک عدد بین ١ تا ٩ نسبت دهیم به صورتی که شروط زیر برقرار باشند:

  • عدد منتسب به هر گره مثلثی شکل، برابر سمت چپ ترین رقم حاصل ضرب اعداد منتسب به گره‌های مجاور آن باشد.
  • عدد منتسب به هر گره به شکل مربع، برابر سمت راست ترین رقم حاصل ضرب اعداد منتسب به گره‌های مجاور آن باشد.
  • عدد منتسب به هر گره به شکل پنج ضلعی، برابر سمت چپ ترین رقم حاصل جمع اعداد منتسب به گره‌های مجاور آن باشد.
  • عدد منتسب به هر گره به شکل شش ضلعی، برابر سمت راست ترین رقم حاصل جمع اعداد منتسب به گره‌های مجاور آن باشد.
  • محدودیتی برای گره‌های دایره‌ای شکل وجود ندارد.

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

شکل

ورودی🔗

خط اول ورودی عدد TT است که تعداد تست‌ها را نشان می‌دهند. خط اول هر تست، شامل اعداد VV و EE است که اولی نشان دهنده تعداد گره‌ها و دومی نشان دهنده تعداد یال‌های گراف است.

در خط بعد VV کاراکتر از بین یکی ͬاز کاراکترهای Tبرای مثلث، S برای مربع، P برای پنج ضلعی، H برای شش ضلعی و C برای دایره، که با یک فاصله از هم جدا شده‌اند می‌آید که کاراکتر iiام، شکل گره iiام را مشخص می‌کند (0 ≥ ii).

پس از آن، EE خط به صورت ‍‍i j می‌آید. که نشان می‌دهد یالی میان گره iiام و گره jjام وجود دارد. نمونه ورودی متناظر با شکل در ادامه آمده است.

خروجی🔗

به ازای هر تست، یک خط خروجی می‌آید که شامل VV عدد بین ١ تا ٩ است که با فاصله از هم جدا شده اند و عدد iiام، مقدار منتسب به گره iiام را نشان می‌دهد.

مثال🔗

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

1
9 8
C P H S S H H T C
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
Plain text

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

9 1 7 6 8 3 5 2 4
Plain text

چیهمونی؟


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

علیش که دیگه از این زندگی خسته‌شده داره میره اونور و امشب گودبای پارتیشه. پاشا هم که علاقه زیادی به پیش‌خدمت بودن داره پیش‌خدمت دم دره و به علیش کمک می‌کنه. مهمونی ساعت 00:00 شروع میشه و تا ساعت 23:59 طول می‌کشه.

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

ورودی🔗

در خط اول nn تعداد تیکه کاغذها آمده سپس در nn خط بعدی اسم و ساعت و یکی از کاراکترهای + یا - آمده‌است.

1n100 0001 \le n \le 100\ 000

  • فرمت تمام ساعت‌ها به‌شکل HH:MM است.
  • اسم رشته‌ای تشکیل‌شده از حروف کوچک انگلیسی است.
  • تضمین می‌شود جمع طول اسم‌ها حداکثر 500 000500\ 000 باشد.
  • تضمین می‌شود اگر کسی وارد مهمانی شود، قبل از آن در مهمانی نبوده و اگر هم خارج‌شود قبل از آن در مهمانی بوده‌است.

خروجی🔗

در تنها خط خروجی شلوغ‌ترین ساعت مهمونی رو با فرمت HH:MM چاپ‌کنید. در صورت وجود چندین جواب یکی‌را به دلخواه چاپ کنید.

مثال🔗

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

2
ali 23:32 -
ali 20:12 +
Plain text

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

21:15
Plain text

هر ساعتی بین 20:1220:12 تا 23:3123:31 نیز می‌تواند جواب باشد.

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

4
alish 16:15 +
pasha 22:34 -
alish 23:56 -
pasha 21:21 +
Plain text

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

21:33
Plain text

مسئله راه‌بندان


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

شما بایستی از الگوریتم AA* برای حل مسئله راه‌بندان استفاده کنید.

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

شکل

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

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

ورودی🔗

ورودی شامل مشخصات پارکینگ و خودروهای پارک شده در آن به همراه موقعیت خودروی قرمز رنگ است. خط اول ورودی عدد TT است که تعداد پارکینگ‌ها را مشخص می‌کند. پس از آن مشخصات TT پارکینگ به صورت پشت سر هم در ورودی می‌آید. برای هر پارکینگ، در خط اول سه عدد NN ،MM و VV قرار دارد که به ترتیب تعداد سطرها و ستون‌های پارکینگ و تعداد خودروهای درون آن (شامل خودروی قرمز رنگ) را مشخص می‌کند. VV خط بعدی هر یک مشخصات یک خودرو را نشان می‌دهد. در هر خط، ابتدا دو عدد RR و CC قرار دارند که به ترتیب سطر و ستون قسمت بالا و سمت چپ خودرو را مشخص می‌کنند. در ادامه راستای خودرو با یک کاراکتر hh برای افقی و یا vv برای عمودی مشخص می‌شود. در انتهای خط نیز عدد LL طول خودرو را نشان می‌دهد.

لازم به ذکر است که خانه بالای سمت چپ در سطر ١ و ستون ١ قرار داشته و خانه پایین سمت راست در سطر NN و ستون MM قرار دارد. ضمناً اولین خط از لیست مشخصات خودروها متعلق به خودروی قرمز رنگ است. نمونه ورودی متناسب با شکل در زیر آمده است.

خروجی🔗

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

ورودی نمونه🔗

1
6 6 13
3 1 h 2
1 1 v 2
1 2 v 2
1 4 h 3
2 3 h 2
2 5 h 2
3 4 v 2
4 2 v 2
5 3 h 2
5 5 v 2
5 6 v 2
6 1 h 2
6 3 h 2
Plain text

خروجی نمونه🔗

Test #1: 16
Plain text

کوه عسل


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

پس از تلاش‌های ناموفق لیته برای خوشحال کردن فیته، وی تصمیم گرفت خودش و فیته را در برنامه بعدی گروه کوه دانشگاه ثبت‌نام کند تا این سفر چندروزه باعث بهبود روابطشان شود.

برنامه بعدی گروه کوه در منطقه‌ی بقمچگاه برگزار خواهد شد که استراحت‌گاه‌های آن و راه‌های ارتباطی بین آن‌ها مثل یک گراف جهت‌دار هستند. در این گراف:

  • از یک استراحت‌گاه به یک استراحت‌گاه دیگر حداکثر یک راه مستقیم وجود دارد. (ممکن است بین دو استراحت‌گاه دو راه متفاوت در خلاف جهت یکدیگر وجود داشته باشد)
  • از یک استراحت‌گاه به خودش راه مستقیمی وجود ندارد.
  • ممکن است در گراف دور وجود داشته باشد.

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

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

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

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

نیمه‌های شب لیته با اتصال به روح مهرسا از زمان همه زمین‌لرزه‌ها و پس‌لرزه‌ها باخبر می‌شود و حالا مدام سوالاتی به ذهنش می‌رسند که اگر در روز tt-ام اردو در استراحت‌گاه شماره xx باشند، آیا ممکن است تا آخر اردو زنده بمانند یا خیر. طبیعتا شما باید در حل این مسئله به او کمک کنید.

ورودی🔗

سطر اول ورودی شامل سه عدد طبیعی nn و mm و qq است که به ترتیب نشان‌دهنده تعداد استراحت‌گاه‌ها، تعداد راه‌های یک‌طرفه بین آن‌ها و تعداد سوالات ذهن لیته هستند.1n,m,q400 0001 \le n, m, q \le 400\ 000 در ii-امین سطر از nn سطر بعد اطلاعات لرزش‌های استراحت‌گاه شماره ii آمده است، به این صورت که در ابتدا عدد kk آمده است که نشاندهنده تعداد لرزش‌های شهر ii است و به دنبال آن kk عدد مثل tt به ترتیب صعودی اکید آمده اند که نشاندهنده‌ی روزهایی هستند که در شهر ii لرزش اتفاق افتاده است.

  • اولین لرزش هر شهر یک زمین‌لرزه است و بقیه لرزش‌ها در آن شهر پس‌لرزه هستند.
  • تضمین می‌شود که زمان تمامی لرزش‌ها متفاوت هستند. یعنی در یک زمان در دو استراحت‌گاه لرزش اتفاق نمی افتد. 0k400 0000 \le k \le 400\ 000 1t1091 \le t \le 10^9
  • هم‌چنین تضمین می‌شود در مجموع تعداد لرزش ها کمتر مساوی 400 000400\ 000 می‌باشد.

در هر یک از mm سطر بعد دو عدد vv و uu آمده‌است که نشان‌دهنده وجود مسیر یک‌طرفه از استراحت‌گاه شماره vv به استراحت‌گاه شماره uu است. 1v,un1 \le v, u \le n در هر یک از qq سطر بعد به ترتیب دو عدد xx و tt آمده‌است که نشان‌دهنده یکی از سوالات ذهن لیته است. (آیا اگر آنها در روز tt در استراحت‌گاه شماره xx باشند می‌میرند یا زنده خواهند ماند) 1t1091 \le t \le 10^9 1xn1 \le x \le n

خروجی🔗

به ازای هر سوال ذهن لیته، اگر پاسخ سوال این است که زنده خواهند ماند کلمه Alive را چاپ کنید و در غیر این‌صورت کلمه Dead را چاپ کنید.

ورودی نمونه🔗

4 4 4
2 2 4
3 1 5 7
1 6
1 10
1 2
2 3
3 1
2 4
2 5
2 6
1 4
1 5
Plain text

خروجی نمونه🔗

Dead
Alive
Dead
Alive
Plain text

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

اگر در زمان ۵ در استراحت‌گاه ۲ باشند (پرسش اول) قطعا می‌میرند زیرا چه به استراحت‌گاه ۳ (در زمان ۶) بروند چه استراحت‌گاه ۴ (در زمان ۱۰) می‌میرند.

اگر در زمان ۶ در استراحت‌گاه ۲ باشند (پرسش دوم) می‌توانند در زمان ۷ پس لرزه می‌آید و آنها با رفتن به استراحت‌گاه ۳ زنده می‌مانند. زیرا در زمان ۸ به استراحت‌گاه ۳ می‌رسند و دیگر زلزله‌ای نمی‌آید.

اگر در زمان ۴ در استراحت‌گاه ۱ باشند (پرسش سوم) مجبورند به استراحت‌گاه ۲ بروند و مانند پرسش اول می‌میرند.

اگر در زمان ۵ در استراحت‌گاه ۱ باشند (پرسش چهارم) زلزله‌ای نمی‌آید و همانجا زنده می‌مانند.

پاشاشاپا


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

ممل علیشو مجبور کرده که nn تا رشته از حروف کوچک انگلیسی رو، رو یه کاغذ بنویسه. ممل می‌خواد این کاغذو بذاره جلو پاشا و بهش بگه با این کلمه‌ها یه رشته‌ی پالیندروم(رشته ای که خودش با برعکس برابره مثل abba) بنویسه.

پاشا باید حداقل یکی از این رشته‌هارو استفاده کنه و می‌تونه یه رشته رو چند بار استفاده کنه و به هر ترتیبی که خواست اونارو بچسبونه به هم و بنویسه و نتیجه باید رشته‌ای پالیندروم بشه.

ممل به تعداد حروفی که پاشا در رشته آخر نوشته علیشو می‌زنه. علیش رشته‌هایی که نوشته بودو یادشه و می‌خواد بدونه حداقل چند بار کتک می‌خوره. حداقل تعداد کتک‌هایی که علیش می‌خوره چند تاست؟‌ اگه پاشا نتونه رشته پالیندروم بسازه ممل علیشو ماچ می‌کنه که معادل -1 بار(!) کتک خوردنه.

ورودی🔗

در خط اول nn، و در nn خط بعدی رشته هایی که علیش نوشته آمده. تضمین می‌شود رشته‌ها فقط از حروف کوچک انگلیسی تشکیل شده باشند و جمع طول آنها حداکثر 3 0003\ 000 باشد.

1n3 0001 \le n \le 3\ 000

خروجی🔗

در خروجی تنها حداقل تعداد بار‌هایی که علیش کتک می‌خوره رو چاپ کنید.

مثال🔗

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

3
ps
as
sp
Plain text

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

4
Plain text

**رشته‌ی پالیندرومی که پاشا می‌تونه بسازه و کمترین طول رو داره pssp است.

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

4
abb
ba
bba
abaa
Plain text

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

5
Plain text

**رشته‌ی پالیندرومی که پاشا می‌تونه بسازه و کمترین طول رو داشته باشه abbba است.

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

3
abbs
sbbx
we
Plain text

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

-1
Plain text

**پاشا نمی‌تونه رشته پالیندرومی بسازه.