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

ربات جدیدی در تلگرام آمده است که از قابلیت‌هایش این است که می‌تواند خانه را جارو کند!! پارسا این ربات را گرفته و می‌خواهد به کمک آن اتاق خویش را مرتب کند. اتاق پارسا از بالا به شکل یک جدول مستطیل شکل به ابعاد $n \times m$ است ($n$ سطر و $m$ ستون) که در هر خانه‌ی آن یا یک توپ قرار دارد و یا یک آشغال (کلا بسیاری از اشیا در زندگی پارسا یا توپ اند و یا آشغال!) پارسا این ربات را در ‌خانه‌ی $(x, y)$ (سطر $x$م و ستونم $y$م) قرار داد که در آن خانه‌ آشغالی قرار دارد و ربات آشغال را مکید به کیسه‌ی انبار خود یعنی فضای مجازی فرستاد! از آنجایی که این ربات یک ربات است، قابل کنترل می‌باشد و در حال حاضر کنترل آن به دست پارسا می‌باشد. کنترل ربات ۵ دکمه بیشتر ندارد. دکمه‌ی چپ، بالا، راست، پایین و دکمه‌ی شروع.

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

نحوه‌ی کار با ربات به این صورت است که در ابتدا پارسا مقداری دکمه‌های چپ و بالا و راست و پایین را فشار می‌دهد و با فشار دادن این دکمه‌ها رشته‌ی دستوری به روی صفحه‌ی نمایش نقش می‌بندد. برای مثال اگر پارسا به ترتیب ۱ بار دکمه‌ی چپ، سپس ۱ بار دکمه‌ی بالا، سپس ۲ بار دکمه‌ی راست، سپس ۱ بار دکمه‌ی پایین و در نهایت ۱ بار دکمه‌ی چپ را فشار دهد رشته‌ی دستوری نوشته‌شده روی کنترل به این صورت می‌شود: LURRDL

• نمایانگر بالا: U
• نمایانگر راست: R
• نمایانگر پایین: D
• نمایانگر چپ: L

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

نحوه‌ی اجرای دستور نوشته شده روی صفحه‌ی نمایش توسط ربات به این صورت است که او به ترتیب حروف دستور را گرفته و آنقدر آن عملیات را انجام می‌دهد تا به دیوار یا به توپ برسد. مثلا اگر $U$ را ببیند از $(x,y)$ به $(x - 1, y)$ و سپس به $(x - 2, y)$ و همینطور تا آخر میرود و خانه‌ها را تمیز میکند تا به دیوار یا توپ برسد. سپس به سراغ دستور بعدی می‌رود. حالا پارسا می‌خواهد بداند که آیا این ربات ارزش خریدن را داشته یا نه. برای همین می‌خواهد تعداد خانه‌های تمیز شده را بداند. اما پارسا به شدت مشغول توپ بازی است و فرصت این گونه محاسبات را ندارد. به او کمک کنید تا این مقدار را پیدا کند.

ورودی🔗

در سطر اول ورودی سه عدد $n$ و $m$ و $l$‌ می‌آید که به ترتیب نمایانگر طول و عرض اتاق و طول رشته‌ی دستورات است.

در خط بعدی دو عدد $x$ و $y$ آمده که نشان‌دهنده‌ی محلی است که ربات در اول کار در آن قرار دارد.

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

در $n$ خط بعدی در هر خط یک رشته به طول $m$ آمده که نمایانگر جدول اتاق پارسا است. O نشان‌دهنده‌ی توپ و # نشان‌دهنده‌ی آشغال است. تضمین می‌شود که در مکان اولیه‌ی ربات توپ نیست.

$1 \le n,m,l \le 100$ $1 \le x \le n$ $1 \le y \le m$

خروجی🔗

در تنها خط خروجی تعداد خانه‌هایی که تمیز شده‌اند را خروجی دهید.

مثال🔗

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

4 5 5
2 2
RUDLL
##O##
O##O#
#O###
###OO

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

6

ربات در خانه‌ی (2, 2) است. بعد از خواندن حرف اول به (3 ,2) میرود. چون بالای این خانه توپ است، حرکتی نمیکند و سپس دو خانه پایین می‌آید و بعد دو خانه به چپ می‌رود و بعد از آن دوباره حرکتی نمیکند.

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

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

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

ورودی🔗

در سطر اول ورودی عدد $n$ به معنی تعداد روستا‌ها می‌آید و در $n$ سطر بعد مختصات روستاها به صورت زوج های (x, y) می‌آید که در آن x و y اعدادی صحیح هستند. مختصات هیچ دو روستایی یکی نیست.

$3 \le n \le 50$ $-100\ 000 \le x, y \le 100\ 000$

خروجی🔗

در تنها خط خروجی، در صورتی که نقطه ای با ویژگی دلخواهمان وجود داشت، مختصات آن را چاپ کنید و در غیر این صورت عبارت "No Answer" را خروجی دهید.

مثال🔗

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

4
6 12
12 10
16 6
-8 0

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

5 -1

شکل مربوط به مثال:

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

3
5 4
7 10
2 -5

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

No Answer

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

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

۱. تعداد فعل‌های موجود در یک کتاب

۲. تعداد فاعل‌های موجود در یک کتاب

۳. تعداد صفت‌های موجود در یک کتاب

۴. تعداد حروف ربط موجود در یک کتاب

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

ورودی🔗

در سطر اول ورودی دو عدد $n$‌ و $q$ آمده است که به ترتیب نمایانگر تعداد کتاب‌ها و تعداد در‌خواست‌ها می‌باشد. سپس در $n$‌ بعدی در خط $i$، چهار عدد $a_1$، $a_2$، $a_3$ و $a_4$ آمده که به ترتیب نمایانگر ۴ فاکتور کتاب $i$ ام می‌باشد. بعد از آن در $q$ خط بعدی در خط $i$، توضیحات درخواست $i$ ام به این صورت آمده است:

۴ عدد $b_1$، $b_2$، $b_3$ و $b_4$ به شما داده می‌شود که عدد $i$ نمایانگر مقداری است که برای فاکتور $i$‌ در نظر گرفته شده. اگر این عدد برابر با 1- بود به این معنا است که در پیدا کردن کتاب‌ها این فاکتور را در نظر نگیرید و تنها تعداد کتاب‌هایی را خروجی دهید که فاکتور‌های غیر از 1- با آنها می‌خواند.

$1 \le n,q \le 50\ 000$

$1 \le a_1,a_2,a_3,a_4 \le 1000\ 000\ 000$

$-1 \le b_1,b_2,b_3,b_4 \le 1000\ 000\ 000$

دقت کنید که هیچ عددی در ورودی برابر ۰ نخواهد بود.

خروجی🔗

خروجی شامل $q$ سطر است که در خط $i$ ام، جواب درخواست $i$‌ را خروجی دهید.

مثال🔗

ورودی نمونه🔗

4 3
1 2 3 4 
3 2 4 2
1 2 4 3
5 8 9 9
-1 2 -1 -1
-1 -1 4 3
2 2 2 2

خروجی نمونه🔗

3
1
0

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

با بوجود آمدن زبان‌های برنامه‌نویسی متنوع بسیار با نام‌های غیر قابل توصیف، "حاج اصغر" نیز تصمیم گرفت برای خود زبانی طراحی کند و آن را "ذله" (یا Zelle) نامید.

او نحوه‌ی برنامه‌نویسی با زبانش را به جهانیان ارائه کرد تا همه بتوانند از زبان زیبایش استفاده کنند.

هر برنامه به زبان "ذله" به شکل زیر است:

• یک برنامه شامل تعدادی "محدوده" یا "scope" است. در ابتدای هر scope یک سطر که شامل آکولاد باز (یا }) می‌شود آمده‌است و در انتهای آن یک سطر که شامل آکولاد بسته (یا {) می‌شود آمده‌است. یک محدوده می‌تواند شامل تعدادی محدوده شود؛ به این صورت که کل محدوده‌ی داخلی بین شروع و پایان محدوده‌ی خارجی قرار داشته باشد. برای مثال، برنامه‌ی زیر ۳ محدوده دارد که یکی شامل ۲ تای دیگر می‌شود:

{
{
}
{
}
}

• در هر محدوده تعدادی متغیر می‌توان تعریف کرد که در آن‌ها می‌توان یک مقدار عددی نگه‌داشت. هر متغیر بصورت زیر تعریف می‌شود:

set name = value ;

که name برابر نام متغیر است و value یک عبارت است که نمایانگر مقدار اولیه‌ی در این متغیر است. برای مثال:

set a = 24 + 18 - 10 ;

یک متغیر به‌نام a تعریف می‌کند و مقدار آن‌ را برابر ۳۲ قرار می‌دهد. نام یک متغیر باید رشته‌ای شامل تنها حروف کوچک انگلیسی باشد. همچنین نام یک متغیر نباید برابر set یا print باشد.

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

می‌توان مقدار یک متغیر را پس از تعریف آن بصورت زیر تغییر داد:

name = value ;

که name نام متغیری است که باید تغییر کند و value عبارتی‌است که حاصلش مقدار جدید این متغیر است. برای مثال:

set a = 2 ;
set b = 5 ;
a = a - b ;

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

برای مثال، برنامه‌ی زیر درست نیست:

{
    set a = 5 ;
    set a = 6 ;
}

اما برنامه‌ی زیر درست است:

{
    set a = 5 ;
    {
        set a = 6 ;
    }
}

• دستور print نیز یک عبارت را در خروجی برنامه می‌نویسد. نحوه‌ی کار با این دستور به شکل زیر است:

print value ;

که value عبارتی‌است که حاصلش باید در یک سطر از خروجی نوشته شود. برای مثال:

print a + b - c ;

• هر برنامه باید یک scope اصلی داشته باشد که بقیه برنامه درون آن قرار بگیرد و قبل و بعد از این scope هم دستور یا scope دیگری وجود نداشته باشد.
• یک عبارت در زبان "ذله" شامل تعدادی عدد/متغیر است که بینشان عملگر جمع یا تفریق به صورت + یا - ، همراه با فاصله آمده است. اعداد داخل یک عبارت همه صحیح و مثبت هستند.
• در پایان هر خط دستوری یک کاراکتر ; با فاصله می‌آید.

همچنین نباید در عبارت هنگام تعریف یک متغیر از آن و یا متغیری هم‌نام با آن استفاده کرد.

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

ورودی🔗

ورودی از تعدادی خط تشکیل شده است که برنامه را می‌سازند. می‌توانید فرض کنید برنامه ورودی حداکثر از ۱۰۰ خط تشکیل شده که هر خط شامل یک دستور، آکولاد باز و یا آکولاد بسته است. همچنین ممکن است برای خواناتر شدن در برنامه از کاراکتر های فاصله (space یا tab) اضافه استفاده شده باشد و یا سطری خالی از دستور در برنامه باشد.

همچنین می‌توانید فرض کنید در عبارت های داخل برنامه از حداکثر ۱۰ عدد/متغیر استفاده شده است و در طول اجرای برنامه مقدار قدر مطلق هیچ متغیری بیشتر از $10^6$ نمی‌شود. حداکثر طول نام متغیر ها ۱۰ کاراکتر است.

خروجی🔗

اگر در برنامه ورودی قواعد زبان برنامه نویسی ذله رعایت نشده بود باید عبارت "Zelle Error" در یک خط چاپ شود و اگرنه مقدار های مربوط به دستور های print باید به ترتیب در خط های جداگانه چاپ شوند.

مثال🔗

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

{
    set a = 3 ;
    {
        print a ;     
        set b = a + a + a ;    
        print b - 5 ;
    }
}

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

3
4

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

{
    set a = 3 ;
    {
        print a ;     
        set b = a + a + a ;    
    }
    print b - 5 ;
}

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

Zelle Error

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

{
    set a = 3 ;
    set b = 5 ;
    print a ;
    print b ;
    a = a + b ;
    b = a - b ;
    a = a - b ;
    print a ;
    print b ;
}

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

3
5
5
3

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

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

او گفت که می‌تواند تعدادی ستاره به Quera بدهد که دیگر نیازی به برگزاری مسابقه نباشد و Quera نیز طبعاً از این پیشنهاد بسیار استقبال کرد!

پس از گذشت روزها، بالاخره این دوست ستاره‌ها را برای Quera فرستاد، اما این ستارگان با آنچه Quera انتظار داشت بسیار متفاوت بودند. او تعدادی عکس از ستارگان برای Quera‌ فرستاده بود! Quera پس از این اتفاق، خونسردی خود را حفظ کرد و تلاش کرد تهدیدها را تبدیل به فرصت‌ها کند؛ پس چالشی از روی این‌ها برای شما پدید آورد!

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

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

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

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

در این مثال تنها ۵ ستاره وجود دارد که شما باید آن‌ها را بیابید.

یا برای مثال، در عکس زیر (که بازهم بخشی از یکی از عکس‌های تست‌ها است) ۱۲ ستاره وجود دارد که شما باید آن‌ها را بیابید:

(ورودی مثال این دو عکس و یک خروجی معتبرشان در نمونه‌های سوال آمده‌اند.)

دقت کنید که لازم نیست تمام ستارگان با شرایط گفته‌شده را بیابید؛ شما کافیست به تعداد $expected$ ستاره با این شرایط پیدا کنید و می‌توانید تا $\frac 4 3$ تعداد کل ستارگان با شرایط گفته شده نقطه خروجی دهید. تضمین می‌شود بیش از $\lceil \frac 5 4 \rceil$ مقدار $expected$ در هر تست، ستاره با شرایط گفته شده یافت شود.

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

ورودی🔗

در سطر اول ورودی، سه عدد $h$ و $w$ و $expected$ آمده‌است که به ترتیب نمایانگر مقدار ارتفاع و عرض عکس ورودی و تعداد ستاره‌هایی که باید یافت شوند هستند.

$150 \le w, h \le 800$

سپس در $h$ سطر بعدی، هر سطر رنگ $w$ نقطه‌ از تصویر توصیف شده‌است. توصیف هر نقطه بصورت $(r,\ g,\ b)$ می‌باشد که نمایانگر رنگ این نقطه در صورت نمایش بصورت RGB است. توصیف‌ نقاط با فاصله (space) از هم جدا شده‌اند.

تضمین می‌شود در هریک از تست‌های داده شده، حداکثر ۵۰ ستاره با شرایط گفته شده وجود دارد.

به ورودی‌های نمونه دقت کنید!

خروجی🔗

در سطر اول خروجی یک عدد $k$ چاپ کنید که نمایانگر تعداد ستاره‌هایی است که در عکس یافت شده‌اند. سپس در هریک از $k$ سطر بعدی، مختصات یکی از نقاط یکی از ستاره‌های یافت شده را خروجی دهید. هر مختصات باید بصورت $(h', w')$ باشد که یعنی این نقطه در سطر $h'$ توصیف عکس در ورودی سوال، نقطه‌ی $w'$امی بوده‌است که توصیف شده‌است.

مثال🔗

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

ورودی نمونه‌را می‌توانید در اینجا ببینید.

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

5
13 23
78 139
25 60
67 61
103 130

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

ورودی نمونه‌را می‌توانید در اینجا ببینید.

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

12
83 160
22 147
88 137
175 229
15 290
144 172
136 119
147 179
47 98
111 97
163 284
154 278