فهرست مندرجات
Indisputable Right
Flatland
یک جهان ۲بعدی است که در آن موجودات زندگی بدی دارند! جدا از این زندگی، آن‌ها اخیرا به تکنولوژی وایرلس دست‌یافتند! آن‌ها برای اینکه وایرلس حق مسلّمشان بود کمیته‌ای تشکیل دادند که تمامی نقاط مهم
Flatland
را با وایرلس به‌یکدیگر وصل کنند.
همه‌چیز روبه‌راه بود تا اینکه کمیته به مناطق کوهستانی رسیدند! منطقه را می‌شود مثل یک خط افقی پایه تشبیه کرد که روی آن‌ها کوه‌های متوالی هستند، هر کوه یک مثلث متساوی‌الساقین قائمه هست (قله راس با زاویه ۹۰درجه است) که ضلع پایین مثلث روی خط افقی پایه است. در حال حاضر فقط دو نوع کوه وجود دارد، یکی با ارتفاع قله ۵۰ و دیگری ۱۰۰. (برای فهم بهتر به شکل رجوع کنید)
کمیته اول آنتن‌ها را در جاهای مقرّر در کوهستان نصب کرد، اما بعد متوجه شدند که دو آنتن درصورتی می‌توانند با یک‌دیگر در ارتباط باشند که پاره‌خط واصل آن‌ها هیچ تداخلی با کوه‌ها نداشته باشد. (و در درون کوه هم نباشد)
از آنجا که اگر کمیته آنتنی را قطع کند آشوب به پا می‌شود، کمیته مجبور شده‌است آنتن‌های اضافه‌ای نصب کند. هر آنتن می‌تواند با آنتن‌هایی که به‌آن‌ها دید مستقیم دارد ارتباط برقرار کند. از آنجا که کمیته می‌خواهد هزینه نصب آنتن‌های اضافه کمینه شود، کم‌ترین تعداد آنتن اضافه لازم برای اینکه همه آنتن‌ها بتوانند (باواسطه یا بی‌واسطه) با یک‌دیگر ارتباط برقرار کنند را بگویید.
ورودی
- ورودی شامل چندین تست است. در خط اول هر تست دو عدد $n$ ($1\leq n \leq 500$) و $m$ ($1 \leq m \leq 1000$)، به ترتیب بیانگر تعداد کوه‌ها و تعداد آنتن‌های نصب شده هستند. سپس در خط بعد $n$ عدد آمده‌است (این‌عدد یا ۵۰ است یا ۱۰۰) که عدد $i$ام ارتفاع قله $i$ام را نشان می‌دهد.
- سپس در خط بعد $m$ عدد آمده‌است که عدد $i$ ام $X$ محل آنتن $i$ در محور مختصات است (یعنی روی نقطه‌ای از کوه که آن عدد را در $X$ محور مختصات داشته باشد). فرض کنید کوه‌ها از چپ به راست و از نقطه $(0,0)$ شروع می‌شوند. (برای فهم بهتر ورودی به ورودی نمونه که همان شکل بالاست توجه‌کنید)
- در خط آخر ورودی دو عدد ۰ و ۰ آمده‌اند.
خروجی
به ازای هر تست، کم‌ترین تعداد آنتن اضافه لازم را چاپ کنید.
محدودیت‌ها
- محدودیت زمان: ۱۰ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت