المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۱۴:سوال ۱۰

شهر بلوکی

علی می‌خواهد یک شهر بلوکی برای باشگاه بسازد. منظور از شهر بلوکی شهری است که با مکعب‌های $1/1/1$ ساخته شده است. آقای ساعی دهقان یک عکس از روبرو و یک عکس از سمت راست شهر به علی داده است. فرض کنید طول شهر $K$ و عرض آن $L$ باشد. (در واقع شهر به صورت یک جدول مستطیلی $K*L$ است که روی هر خانه‌ی این جدول تعدادی مکعب قرار دارند) آقای ساعی دهقان موقع دادن عکس در واقع تعدادی عدد به علی بیچاره داده است در واقع عکس روبرو $K$ عدد دارد که به ترتیب ارتفاع بلندترین مکعب در هر امتداد دید از چپ به راست در آن قرار دارد. (منظور از ارتفاع تعداد مکعب‌هایی است که روی هم قرار دارند.) عکس از سمت راست نیز به‌طور مشابه حاوی $L$ عدد است. شما می‌بایستی با حداقل (حداکثر) تعداد مکعب شهری را بسازید که با عکس‌های داده شده مطابقت داشته باشد.

ورودی

در سطر اول فایل ورودی ابتدا $K$ و $L$ آمده است. سپس در $K$ سطر $K$ عدد که نشان‌دهنده‌ی ارتفاع بلندترین ساختمان‌ها از روبرو است داده شده است. در $L$ سطر بعدی هم $L$ عدد که ارتفاع بیش‌ترین ساختمان را در عکس از سمت راست نشان می‌دهد وجود دارد. دقت کنید $1\leq K,L \leq 10^5$.

خروجی

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

محدودیت‌ها

  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۶۰۰ کیلوبایت

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
4 3
1
3
4
2
1
4
2
10 21
2 2
4
1
1
3
No solution

ابزار صفحه