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

در یک واگن مترو دو ردیف صندلی روبروی هم داریم که هر ردیف شامل ۸ صندلی است. هر صندلی یا خالی است و یا کسی روی آن نشسته.

می‌دانیم اگر کسی روی صندلی شماره $i$ نشسته باشد فقط به روبروی خود، یعنی صندلی شماره $i$ ردیف مقابل نگاه می‌کند و اگر شخصی روی آن صندلی نشسته باشد باهم «چشم تو چشم» می‌شوند.

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

ورودی🔗

ورودی در دو سطر و در هر سطر ۸ عدد صحیح که 0 یا 1 هستند با فاصله ورودی داده می‌شوند که وضعیت صندلی‌های واگن را نشان می‌دهند. 0 نشان دهنده خالی بودن صندلی و 1 نشان دهنده خالی نبودن است.

خروجی🔗

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

مثال🔗

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

1 1 0 1 0 0 1 1
1 1 0 0 0 1 0 1

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

3

در این‌جا جفت‌های ۱، ۲ و ۸ چشم‌ تو چشم هستند. بنابراین پاسخ مسئله برابر ۳ است.

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

0 0 0 1 1 1 0 1
0 0 1 0 1 1 0 0

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

2

در این‌جا جفت‌های ۵ و ۶ چشم‌ تو چشم هستند. بنابراین پاسخ مسئله برابر ۲ است.

if 1 <= n <= 100:
    # answer of problem
else:
    # print('invalid input')

input('please enter:')

package ir.quera.contest;

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

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

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

در این شهر $n$ خیابان از نوع اول و $m$ خیابان از نوع دوم داریم. پس در مجموع $nm + 1$ تقاطع بوجود می‌آید. (میدان اصلی را هم یک تقاطع در نظر بگیرید.)

می‌دانیم تمام این $n + m$ خیابان یک طرفه است. یعنی فقط می‌توان در یک جهت روی آن‌ها حرکت کرد. اما جهت آن‌ها لزوماً باهم یکسان نیست‌. به شما جهت خیابان‌ها داده می‌شود و از شما می‌خواهیم بررسی کنید آیا در این شهر می‌توان از هرتقاطی به هر تقاطع دیگری با عبور از خیابان‌ها رفت یا خیر.

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

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

ورودی🔗

ورودی شامل دو عدد $n$ و $m$ با فاصله است که به ترتیب تعداد خیابان‌های مستقیم و تعداد خیابان‌های دایره‌ای را نشان می‌دهد.

$1 \leq n , m \leq 1\, 000 \, 000$

سپس در خط بعد $n$ عدد 0 و یا 1 با فاصله می‌آیند که نشان دهنده جهت خیابان‌های مستقیم است. 1 به معنی این که جهت خیابان از میدان شروع می‌شود و 0 به معنی این است که به سمت میدان می‌رود.

سپس در خط بعد $m$ عدد 0 و یا 1 با فاصله می‌آیند که نشان دهنده جهت خیابان‌های دایره‌ای است. 1 به معنی این که جهت خیابان ساعتگرد است و 0 به معنی این است که جهت آن پادساعتگرد است.

خروجی🔗

در صورتی که شهر داده شده ویژگی مورد نظر را داشت YES و در غیر اینصورت NO را چاپ کنید. (به بزرگی و کوچکی حروف توجه کنید.)

مثال🔗

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

5 3
1 0 0 1 0
1 1 1

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

YES

در این شهر می‌توان از هر تقاطعی به هر تقاطع دیگر رفت. پس پاسخ YES است.

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

2 4
1 1
0 0 0 0

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

NO

در این شهر نمی‌توان از تقاطع‌های دیگر به میدان اصلی رسید پس پاسخ NO است.

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

به $n$ آجر که در یک ردیف کنار هم قرار گرفته‌اند یک «لایه آجر» می‌گوییم. آجر‌ها را به ترتیب با اعداد $1$ تا $n$ شماره‌گذاری کنید. آجر $i$ام یک عدد مثل $a_i$ دارد که «استحکام» آن را نشان می‌دهد.

به یک لایه آجر «مستحکم» می‌گوییم اگر دنباله‌ی $a_1, a_2, \dots, a_n$ یک دنباله غیرنزولی باشد یعنی $a_1 \leq a_2 \leq \dots \leq a_n\,$ باشد.

برای «مستحکم» کردن یک دیوار، در هر حرکت می‌توانیم یک بازه‌ از آجرها را انتخاب و سپس به «استحکام» تمام آن‌ها $x$ واحد اضافه کند. ($x$ در تمام مراحل ثابت است و به شما داده می‌شود.) یعنی می‌توان دو عدد $l$ و $r$ که $1 \leq l \leq r \leq n$ است را انتخاب کرد و وضعیت دنباله را به

$a_1, a_2, \dots, a_{l - 1}, a_l + x, a_{l + 1} + x, \dots, a_{r - 1} + x, a_r + x, a_{r + 1}, \dots, a_n$

تغییر داد.

کمترین تعداد حرکتی که نیاز داریم تا این «لایه آجر» مستحکم شود، را خروجی دهید یا بگویید مستحکم کردن این دیوار غیرممکن است.

برای ساختن یک ساختمان $q$ لایه آجر باید مستحکم شود. دنباله‌ی اولیه استحکام آجرها و مقدار $x$ برای هر لایه به شما داده می‌شود و از شما می‌خواهیم مسئله را برای هر لایه به صورت جداگانه حل کنید.

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

ورودی🔗

در سطر اول ورودی، عدد صحیح و مثبت $q$ که تعداد لایه‌های آجر را نشان میدهد آمده است. $1 \leq q \leq 100 \, 000$

در $2q$ سطر بعدی ورودی، به ترتیب به ازای هر لایه در ابتدا در یک سطر $n$ و $x$ نشان‌دهنده تعداد آجرهای آن لایه و مقدار استحکامی که در هر حرکت می‌تواند اضافه کند آمده است.

$1 \leq n \leq 100 \, 000$ $-100 \, 000 \leq x \leq 100 \, 000$

سپس در سطر بعدی به ترتیب $n$ عدد، $a_1, a_2, \dots, a_n\,$ نشان دهنده استحکام اولیه‌ی آجرهای آن لایه آمده است. تعداد کل آجرها حداکثر $100\,000$ است.

$-100 \,000 \leq a_i \leq 100 \, 000$

خروجی🔗

خروجی شما باید شامل $q$ سطر باشد. در هر سطر کمترین تعداد حرکتی را خروجی دهید که بتوان بعد از این تعداد حرکت استحکام آجرهای این لایه را غیرنزولی کرد. اگر انجام این کار ممکن نیست -1 چاپ کنید.

مثال🔗

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

4
2 2
-3 3
4 1
-2 -4 4 -3
3 0
-73 -4 -5
1 3
1

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

0
9
-1
0

در مثال اول، آرایه‌ی $[-3, 3]$ صعودی است و نیاز به هیچ عملیاتی ندارد. پس پاسخ مسئله برابر ۰ است.

در مثال دوم، آرایه‌ی اولیه $[-2, -4, 4, -3]$ است و هر بار می‌توانیم یک بازه را انتخاب کرده و $x = 1$ واحد به آن اضافه کنیم. اگر دنباله‌ی حرکت‌ها به صورت زیر باشد، بعد از ۹ حرکت به یک آرایه صعودی می‌رسیم.

1. $[-2, -4, 4, -3] \to$
2. $[-2, -3, 5, -2] \to$
3. $[-2, -2, 6, -1] \to$
4. $[-2, -2, 6, 0] \to$
5. $[-2, -2, 6, 1] \to$
6. $[-2, -2, 6, 2] \to$
7. $[-2, -2, 6, 3] \to$
8. $[-2, -2, 6, 4] \to$
9. $[-2, -2, 6, 5] \to [-2, -2, 6, 6]$

در مثال سوم مقدار $x = 0$ است، پس انجام عملیات، باعث تغییری در وضعیت آرایه نمی‌شود و هیچ‌وقت نمی‌توانیم آن را غیرنزولی کنیم.

در مثال چهارم آرایه اولیه تک عضوی است. پس غیرنزولی نیز هست.

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

یک قاب داریم که آن را شکسته‌ایم. قطعات شکسته شده $n$ مستطیل هستند. یعنی قطعه‌ی $i$ام یک مستطیل $w_i \times h_i$ است. می‌خواهیم آن‌ها را کنار هم بگذاریم و یک قاب مربعی بسازیم. باید قطعات را موازی محورها قرار دهیم.

توجه کنید ممکن است یک قطعه را دوران ۹۰ درجه بدهیم ولی در نهایت باید موازی محورها شود. قطعات مستطیل‌ها را یکسان در نظر بگیرید. برای بهتر متوجه شدن سوال به نمونه‌ها توجه کنید.

ورودی🔗

در سطر اول ورودی، عدد صحیح و مثبت $n$ داده می‌شود که تعداد قطعات نشان می‌دهد. $1 \leq n \leq 6$

در $n$ سطر بعدی، در هر سطر دو عدد صحیح و مثبت $h_i$ و $w_i$ داده می‌شود که عرض و ارتفاع یک قطعه را نشان می‌دهد. $1 \leq w_i, h_i \leq 10$

خروجی🔗

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

مثال‌ها🔗

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

3
3 4
1 5
4 2

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

8

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

4
2 2
2 2
2 2
2 2

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

1

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

مقدمه🔗

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

دستورها🔗

فاز اول🔗

دستور register🔗

فرم کلی این دستور به صورت register <username> است و به معنی این است که یک کاربر با نام کاربری <username> می‌خواهد در دیوار ثبت نام کند.

• اگر این نام کاربری قبلاً توسط کاربر دیگری استفاده شده، خطای invalid username را چاپ کنید.
• اگر خطایی وجود نداشت پیام registered successfully را چاپ کنید.

دستور add_advertise🔗

فرم کلی این دستور به صورت add_advertise <username> <title> است و به معنی این است که کاربر <username> می‌خواهد آگهی با عنوان <title> را در دیوار منتشر کند.

• اگر این نام کاربری قبلاً ثبت نام نکرده، خطای invalid username را چاپ کنید.
• اگر این عنوان آگهی، برای آگهی دیگری استفاده شده، خطای invalid title را چاپ کنید.
• اگر خطایی وجود نداشت پیام posted successfully را چاپ کنید.

دستور rem_advertise🔗

فرم کلی این دستور به صورت rem_advertise <username> <title> است و به معنی این است که کاربر <username> می‌خواهد آگهی با عنوان <title> را که قبلاً در دیوار منتشر کرده را پاک کند.

• اگر این نام کاربری قبلاً ثبت نام نکرده، خطای invalid username را چاپ کنید.
• اگر این عنوان آگهی، روی هیچ آگهی قبلاً نیامده، خطای invalid title را چاپ کنید.
• اگر این عنوان آگهی، برای این کاربر نیست، خطای access denied را چاپ کنید.
• اگر خطایی وجود نداشت پیام removed successfully را چاپ کنید.

دستور list_my_advertises🔗

فرم کلی این دستور به صورت list_my_advertises <username> است و به معنی این است که یک کاربر با نام کاربری <username> می‌خواهد لیست آگهی‌هایی که منتشر کرده را مشاهده کند.

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

فاز دوم🔗

دستور add_favorite🔗

فرم کلی این دستور به صورت add_favorite <username> <title> است و به معنی این است که کاربر <username> می‌خواهد آگهی با عنوان <title> را به لیست علاقه‌مندی‌هایش اضافه کند.

• اگر این نام کاربری قبلاً ثبت نام نکرده، خطای invalid username را چاپ کنید.
• اگر آگهی با این عنوان قبلاً منتشر نشده خطای invalid title را چاپ کنید.
• اگر این آگهی با این عنوان قبلاً به لیست علاقه‌مندی‌ها اضافه شده، خطای already favorite را چاپ کنید.
• اگر خطایی وجود نداشت پیام added successfully را چاپ کنید.

دستور rem_favorite🔗

فرم کلی این دستور به صورت rem_favorite <username> <title> است و به معنی این است که کاربر <username> می‌خواهد آگهی با عنوان <title> را از لیست علاقه‌مندی‌هایش حذف کند.

• اگر این نام کاربری قبلاً ثبت نام نکرده، خطای invalid username را چاپ کنید.
• اگر آگهی با این عنوان قبلاً منتشر نشده خطای invalid title را چاپ کنید.
• اگر این آگهی با این عنوان اکنون در لیست علاقه‌مندی‌هایش نیست، خطای already not favorite را چاپ کنید.
• اگر خطایی وجود نداشت پیام removed successfully را چاپ کنید.

دستور list_favorite_advertises🔗

فرم کلی این دستور به صورت list_favorite_advertises <username> است و به معنی این است که یک کاربر با نام کاربری <username> می‌خواهد لیست آگهی‌هایی که به علاقه‌مندی‌هایش اضافه کرده را مشاهده کند.

• اگر این نام کاربری قبلاً ثبت نام نکرده، خطای invalid username را چاپ کنید.
• در غیر این صورت در یک خط عنوان همه‌ی آگهی‌ها را به ترتیب زمان اضافه شدن به علاقه‌مندی در یک سطر با یک فاصله از هم چاپ کنید.

فاز سوم🔗

دستور add_advertise🔗

فرمت کلی این دستور به صورت add_advertise <username> <title> [<tag>] خواهد بود و به معنی این است که کاربر <username> می‌خواهد آگهی با عنوان <title> را با برچسب <tag> منتشر کند.

دستور list_my_advertises🔗

فرم کلی این دستور به صورت list_my_advertises <username> [<tag>] است و به معنی این است که یک کاربر با نام کاربری <username> می‌خواهد لیست آگهی‌هایی که با برچسب <tag> منتشر کرده را مشاهده کند.

توجه کنید اگر مانند فاز اول، همچین کوئری داده شد ولی <tag> نداشت باید بدون در نظر گرفتن برچسب‌ها همه‌ی آگهی‌ها را نشان دهید.

دستور list_favorite_advertises🔗

فرم کلی این دستور به صورت list_favorite_advertises <username> [<tag>] است و به معنی این است که یک کاربر با نام کاربری <username> می‌خواهد لیست آگهی‌هایی که برچسب <tag> را دارند و به علاقه‌مندی‌هایش اضافه کرده را مشاهده کند.

توجه کنید اگر مانند فاز اول، همچین کوئری داده شد ولی <tag> نداشت باید بدون در نظر گرفتن برچسب‌ها همه‌ی آگهی‌ها را نشان دهید.

نکات🔗

• به‌جای <username> یک رشته که نشان‌دهنده‌ی «نام کاربری» است، داده می‌شود.
• به‌جای <title> یک رشته که نشان‌دهنده‌ی «عنوان آگهی» است، داده می‌شود.
• هر رشته که در ورودی داده می‌شود. شامل ارقام، کاراکتر _، حروف کوچک یا بزرگ انگلیسی است و طول آن حداکثر ۲۰ است.
• اگر آگهی از سایت دیوار حذف شده باشد باید از این لیست هم حذف شده باشد.
• اگر لیستی را باید چاپ می‌کردید که خالی است، آن سطر را خالی بگذارید.

ورودی🔗

در سطر اول ورودی، عدد صحیح و مثبت $q$ داده می‌شود. در $q$ سطر بعدی، در هر سطر یک دستور داده می‌شود. $1 \leq q \leq 50$

خروجی🔗

خروجی $q$ سطر دارد، در هر سطر پاسخ مناسب به هر دستور چاپ می‌شود.

مثال‌ها🔗

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

9
register user1
register user2
add_advertise user1 car
add_advertise user2 laptop
add_advertise user2 laptop
list_my_advertises user1
list_my_advertises user2
rem_advertise user2 phone
list_my_advertises user2

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

registered successfully
registered successfully
posted successfully
posted successfully
invalid title
car 
laptop 
invalid title
laptop 

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

10
register user1
register user2
add_advertise user1 car
add_advertise user2 laptop
add_favorite user1 laptop
add_favorite user1 phone
add_favorite user2 laptop
rem_favorite user1 phone
list_favorite_advertises user1
list_favorite_advertises user2

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

registered successfully
registered successfully
posted successfully
posted successfully
added successfully
invalid title
added successfully
invalid title
laptop 
laptop 

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

9
register user1
register user2
add_advertise user1 car automotive
add_advertise user2 laptop electronics
add_advertise user2 phone electronics
add_advertise user1 laptop electronics
list_my_advertises user1 electronics
list_favorite_advertises user1
list_my_advertises user1

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

registered successfully
registered successfully
posted successfully
posted successfully
posted successfully
invalid title


car 

1. sample1.in
2. sample2.in
3. sample3.in
4. 1_register.in
5. 1_add_advertise.in 
6. 1_rem_advertise.in
7. 1_list_my_advertises.in
8. corner.in
9. corner_2.in
10. 2_add_favorite.in
11. 2_rem_favorite.in
12. 2_list_favorite_advertises.in
13. 3_add_advertise.in
14. 3_list_my_advertises.in
15. 3_list_favorite_advertises.in