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

«دو قل، سه قل» یک بازی سنتی ایرانی است. در این بازی ابتدا یکی از بازیکن‌ها تعدادی سنگ‌ریزه را به n دسته افراز می‌کند و از بازیکن دوم می‌خواهد این دسته‌بندی از سنگریزه‌ها را یک دسته‌بندی موردنظر تبدیل کند. یک دسته‌بندی شامل k دسته از سنگریزه‌ها را می‌توان با یک دنباله‌ی c1,c2,,ckc_1,c_2, \cdots, c_k نمایش داد به طوری که این دنباله اندازه‌ی دسته‌های این دسته‌بندی را نشان‌می‌دهند. حال بازیکن دیگر در هر مرحله می تواند یکی از حرکات زیر را انجام دهد:

  • حرکت تجمیع: در صورت وجود بیش از یک دسته، دو تا از آن‌ها را به دلخواه انتخاب کند و سنگریزه‌های آن‌ها را در یک دسته قرار دهد. یعنی اگر تعداد سنگریز‌ه های این دو دسته به ترتیب a و b باشد، بعد از انجام این مرحله یک دسته‌ی جدید به اندازه‌ی a+ba+b به وجود می‌آید و دو دسته‌ی قبلی حذف می‌شوند.

  • حرکت تقسیم: یکی از دسته سنگریزه‌های موجود را به دو دسته‌ی غیر خالی از سنگریزه‌ها تقسیم کند.

حال شما باید برنامه‌ای بنویسید که با گرفتن وضعیت اولیه‌ی سنگریزه‌ها و وضعیت موردنظر بازیکن اول، کمترین تعداد حرکت ممکن بازیکن دوم را حساب کند. دقت کنید که ترتیب اعضای دنباله‌ای که نشان‌دهنده‌ی یک وضعیت از دسته‌بندی سنگ‌ریزه‌ها است، اهمیت ندارد. برای مثال دنباله‌های 1،2 و 2،1 یک وضعیت مشابه از دسته‌بندی 3 سنگریزه را نشان می‌دهند.

ورودی

سطر اول ورودی شامل دو عدد طبیعی n تعداد دسته‌های وضعیت اولیه‌ی سنگریزه‌ها و m تعداد دسته‌های وضعیت نهایی سنگریزه‌ها است.

در سطر دوم دنباله‌ی اعداد طبیعی a1,a2,,ana_1,a_2,\cdots,a_n آمده است به طوری که این دنباله‌ وضعیت اولیه‌ی دسته‌بندی سنگریزه‌ها را نشان می‌دهد.

سطر سوم شامل دنباله‌ی اعداد طبیعی b1,b2,,bmb_1,b_2,\cdots,b_m است که بطوری که این دنباله وضعیت نهایی سنگریزه‌ها را نشان می‌دهد.

1n,m101 \leq n,m \leq 10

1a1,a2,,an1 000,nΣi=1nai1 0001 \leq a_1,a_2,\cdots,a_n \leq 1\ 000 , n \leq \Sigma_{i=1}^{n} a_i \leq 1\ 000

1b1,b2,,bm1 000,mΣi=1mbi1 0001 \leq b_1,b_2,\cdots,b_m \leq 1\ 000 , m \leq \Sigma_{i=1}^{m} b_i \leq 1\ 000

Σi=1nai=Σi=1mbi\Sigma_{i=1}^{n} a_i = \Sigma_{i=1}^{m} b_i

خروجی

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

زیرمسئله‌ها

زیرمسئله شماره‌ی تست‌ها نمره محدودیت
۱ ۱ تا ۱۰ ۱۰۰ بدون محدودیت اضافی

مثال

ورودی نمونه ۱

2 1
3 7
10
Plain text

خروجی نمونه ۱

1
Plain text

ورودی نمونه ۲

1 2
10
3 7
Plain text

خروجی نمونه ۲

1
Plain text

ورودی نمونه ۳

3 3
1 2 3
3 2 1
Plain text

خروجی نمونه ۳

0
Plain text

ورودی نمونه ۴

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

خروجی نمونه ۴

4
Plain text

ارسال پاسخ برای این سؤال
فایلی انتخاب نشده است.