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

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

ورودی🔗

ورودی یک رشته به فرمت HH:MM می‌باشد که ساعت دیده شده در آینه را نشان می‌دهد. قسمت اول که نشان‌دهنده ساعت می‌باشد بین 1 تا 12 و قسمت دوم هم که نشان دهنده‌ی دقیقه است بین 0 تا 59 مي‌باشد.

خروجی🔗

خروجی نیز رشته‌ای به فرمت HH:MM است که ساعت واقعی را نشان می‌دهد.

ورودی-خروجی نمونه🔗

ورودی نمونه ۱

03:00

خروجی نمونه ۱

09:00

ورودی نمونه ۲

05:45

خروجی نمونه ۲

06:15

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

تعدادی توپ با شعاع یکسان بر روی یک زمین صاف بدون اصطکاک قرار دارند و هر کدام با سرعت ثابت حرکت می‌کنند. در چه لحظه‌ای برای اولین بار دو توپ با یکدیگر برخورد می‌کنند؟ در $t=0$، نقطه‌ی مشترک بین سطح زمین و توپ $i$-ام در نقطه $b_i$ قرار دارد (توپ در برخورد با زمین خمیده نمی‌شود مانند شکل زیر) و با سرعت ثابت $a_i$ در حال حرکت است. در صورتی که $a_i > 0$ باشد توپ به سمت راست و اگر $a_i < 0$ به سمت چپ حرکت خواهد‌ کرد. همچنین در لحظه اولیه هیچ دو توپی با هم برخورد ندارند.

ورودی🔗

در خط اول ورودی $2\leq n \leq 50,000$ تعداد توپ‌ها و عدد صحیح $1\leq r \leq {10} ^ {9}$ شعاع توپ‌ها می‌آید و $n$ خط بعدی هر کدام، شامل دو عدد صحیح $-{10}^{9}\leq a_i, b_i \leq {10} ^ {9}$ که به ترتیب از چپ به راست می‌آید و نشان دهنده‌ی سرعت توپ و نقطه‌ی مشترک بین زمین و توپ در $t = 0$ است، می‌باشند.

خروجی🔗

در صورتی که برخورد وجود دارد زمانی که اولین برخورد اتفاق می‌افتد را تا 2 رقم اعشار چاپ کنید و در صورتی که هیچ دو توپی به یک دیگر برخورد نخواهند کرد 1- چاپ کنید.

ورودی-خروجی نمونه🔗

ورودی نمونه 1

2 2
-2 1
2 10

خروجی نمونه 1

-1

ورودی نمونه 2

3 4
1 -10
3 6
-7 30

خروجی نمونه 2

1.60

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

فرض کنید زمینی به عرض $W$ و ارتفاع $H$ داریم. این زمین دارای $H * W$ سلول می‌باشد. بازی مین‌یاب بدین صورت است که تعدادی بمب در این زمین پخش شده است. محتوای سلول‌هایی که بمبی در آنها وجود ندارد، برابر تعداد بمب‌هایی است که در خانه‌های اطراف وجود دارد. با دانستن مختصات بمب‌ها مشخص کنید که در خانه‌ $(x, y)$ چه عددی وجود دارد.

ورودی🔗

سطر اول ورودی به ترتیب شامل دو عدد $3\leq H \leq {10} ^ {9}$ و $3\leq W \leq {10} ^ {9}$ می باشد. در سطر بعدی عدد $1\leq N \leq {10} ^ {3}$ می‌آید که بیانگر تعداد بمب‌ها می‌باشد. در $N$ سطر بعدی مختصات بمب‌ها می‌باشد. هر سطر شامل دو عدد است که عدد اول آن $x_i$ بیانگر شماره سطر، و عدد دوم آن $y_i$ بیانگر شماره ستون، می‌باشد. در سطر بعدی عدد $1\leq Q \leq {10} ^ {4}$ می‌آید که نشان‌دهنده تعداد خانه‌هایی است که می‌خواهیم محتوای داخل آنها را بدانیم. در $Q$ سطر بعدی مختصات خانه‌ها همانند مختصات بمب‌ها می‌آید.

خروجی🔗

خروجی شامل $Q$ سطر می‌باشد که هر سطر نشان‌دهنده محتوای خانه متناظر با آن است. اگر در آن خانه بمب وجود دارد باید BOMB در خروجی چاپ شود.

ورودی-خروجی نمونه🔗

ورودی نمونه

6 3
4
1 1
2 3
3 1
5 2
4
2 2
1 1
4 3
6 3

خروجی نمونه

3
BOMB
1
1

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

یک تابلوی LED شامل $m$ سطر و $n$ ستون است که تعدادی از LEDهای آن سوخته است. برای تعویض LEDهای سوخته می‌توان یک سطر از LEDهای سالم را با سطری که شامل LED سوخته است به طور کامل تعویض کرد و یا از LEDهای سالم تکی استفاده کرد. آیا با داشتن $r$ سطر از LED‌های سالم و $s$ عدد از LEDهای سالم تکی می‌توان تمام LEDهای سوخته را تعویض کرد؟

ورودی🔗

سطر اول ورودی به ترتیب از چپ به راست شامل ۴ عدد $m, n, r, s$ است که $1 \leq m, n \leq 3,000$ و $0 \leq r \leq m$ و $0 \leq s \leq n * m$ می‌باشد.در $m$ سطر بعدی هرکدام $n$ عدد 0 یا 1 می آید که 1 به معنی LED سالم در آن مکان و عدد 0 به معنی LED سوخته در آن مکان است.

خروجی🔗

اگر می‌توان تمام LEDهای سوخته را جایگزین کرد 1 و در غیر این صورت 1- در خروجی چاپ کنید.

ورودی-خروجی نمونه🔗

ورودی نمونه ۱

2 3 1 1
1 1 0
0 0 1

خروجی نمونه ۱

1

ورودی نمونه ۲

3 3 1 2
0 1 0
1 0 1
0 0 0

خروجی نمونه ۲

-1

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

رشته‌ای تمیز است که در همه‌ی زیر رشته‌های به طول 26 آن رشته، تمام حروف الفبای انگلیسی دقیقا یکبار ظاهر شده باشند. یک زیر‌ رشته از رشته $T=t_1...t_n$، یک رشته‌ی $T'=t_{i}...t_{i+m}$ است که $i+m\leq n$ و $1\leq i$.

ورودی🔗

ورودی شامل یک رشته $26 \leq |s| \leq 50,000$ است که از حروف الفبای کوچک و $'?'$ تشکیل شده است.

خروجی🔗

در صورتی که می توان به جای تمام $'?'$ها حروف الفبای کوچک را طوری قرار داد که رشته تمیز شود، رشته تمیزشده را چاپ کنید و در صورتی که این کار امکان پذیر نیست، $-1$ چاپ کنید. در صورتی که چندین جواب وجود دارد رشته‌ای را که از نظر ترتیب در دیکشنری اول است را چاپ کنید.

ورودی-خروجی نمونه🔗

ورودی نمونه 1

acmicpcacmicpcacmicpcacmicpc

خروجی نمونه 1

-1

ورودی نمونه 2

ab?defgh?jklmnop?rstu?wxy?b

خروجی نمونه 2

-1

ورودی نمونه 3

??????????????????????????

خروجی نمونه 3

abcdefghijklmnopqrstuvwxyz

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

دنباله قطبی $S$ از اعداد 1 و 1- تشکیل شده است. برای یک عدد صحیح $x$ در صورتی که داشته باشیم $\exists i | 1 \leq i \leq n, \exists j | i \leq j \leq n, \sum_{k=i}^j S_k = x$ می‌توان $x$ را از دنباله استخراج کرد. آیا می‌توان عدد $x$ را از دنباله استخراج کرد ؟

ورودی🔗

سطر اول ورودی به ترتیب شامل دو عدد $1\leq N \leq {10} ^ {5}$ طول دنباله و $1\leq Q \leq {10} ^ {3}$ تعداد اعدادی که می‌خواهیم بررسی کنیم می‌باشد. در خط بعدی دنباله قطبی به طول $N$ می‌آید. در $Q$ خط بعدی هر کدام یک عدد صحیح ${-10}^{5}\leq x_i \leq {10} ^ {5}$ می‌آید.

خروجی🔗

در صورتی که می توان $x_i$ را از دنباله قطبی استخراج کرد در i-امین خط خروجی yes و در غیر این صورت no چاپ کنید.

ورودی-خروجی نمونه🔗

ورودی نمونه ۱

3 3
1 1 -1 
1
2
3

خروجی نمونه ۱

yes
yes
no

ورودی نمونه ۲

5 2
1 1 -1 1 1
2
3

خروجی نمونه ۲

yes
yes

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

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

ورودی🔗

در ورودی ابتدا $2\leq m,n \leq 1000$ که ابعاد زمین را نشان می‌دهند، به ترتیب از چپ به راست می‌آیند. سپس در $m$ سطر بعدی هر کدام یک رشته‌ای به طول $n$ وجود دارد که نقشه را نمایش می‌دهند. نقطه شروع حرکت ربات با '^' در نقشه مشخص شده است. اهداف با '*' و تله‌ها با '#' مشخص شده اند.

خروجی🔗

اگر مسیری برای رسیدن به هیچ‌کدام از اهداف وجود ندارد در خروجی باید 1- چاپ شود.در صورتی که مسیر وجود دارد در خروجی باید مسیر به صورت دنباله‌ای از کاراکتر‌ها بیاید که به ازای هر حرکت به سمت بالا u، حرکت به سمت چپ l، حرکت به سمت پایین d و حرکت به سمت راست r چاپ شده است. اگر چندین مسیر با طول یکسان وجود داشته باشد باید مسیری چاپ شود که از نظر ترتیب در دیکشنری (lexicographical order) اول باشد.

ورودی-خروجی نمونه🔗

ورودی نمونه ۱

2 2
-*
^-

خروجی نمونه ۱

ru

ورودی نمونه ۲

5 5
-*-#*
*---#
###-#
----#
^--#*

خروجی نمونه ۲

rruruulll