+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- عمو که فردی بسیار پول‌پرست است، به چیدن سکه‌هایش روی هم علاقه‌مند است. عمو سکه‌هایش را روی یک خط بصورت $n$ ستون از سکه با ارتفاع برابر چیده است. عمو هرشب قبل از خواب ستون‌های سکه‌اش را برانداز میکند. او دیشب قبل از خواب متوجه‌شد که چیدمان سکه‌ها به‌هم خورده است. عمو پس از تحقیق متوجه‌شد که کریم، یک پسر‌بچه‌ی ۵ ساله‌ که به جابجایی سکه‌ها علاقه‌مند است، تعدادی سکه از هر ستون به ستون‌های دیگر منتقل کرده است. حال عمو میخواهد بار دیگر ستون‌هایش را هم ارتفاع کند. او بدلیل خواب‌آلودگی، در هر دقیقه میتواند یک سکه از روی یکی از ستون ها برداشته و روی ستون دیگری بگذارد. با داشتن ارتفاع سکه‌ها بگویید که این مرتب سازی حداقل چند دقیقه از او وقت خواهد گرفت. # ورودی سطر اول ورودی شامل عدد $n$ است که نمایانگر تعداد ستون‌های سکه‌ی عمو است. در سطر $i$م از هریک از $n$ سطر بعدی یک عدد طبیعی حداقل ۰ و حداکثر $10^4$ آمده است که ارتفاع ستون‌ها را نشان میدهد. تضمین میشود که عمو میتواند با حرکت گفته‌شده همه ستون‌ها را هم ارتفاع کند. $$1 \le n \le 10^4$$ # خروجی در تنها سطر خروجی یک عدد چاپ کنید که برابر کمینه دقایقیست که عمو میتواند در آن ستون‌هایش را هم ارتفاع کند. # ورودی نمونه ``` 4 1 2 3 6 ``` # خروجی نمونه ``` 3 ``` عمو میتواند یک سکه از ستون آخر به ستون دوم ببرد و ۲ سکه از ستون آخر به ستون اول تا ارتفاع همه‌ی ستون‌ها برابر ۳ شود.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- عمو که فردی بسیار پول پرست است، به جاسوسی چند‌جانبه روی آورده. عمو در $n$ سازمان جاسوسی مختلف عضو است. هر سازمان با دریافت اطلاعات سرّی راجع به سازمانی دیگر، به عمو پول میدهد. عمو نمیتواند یک اطلاعات را به دو سازمان جاسوسی بفروشد، وگرنه این اطلاعات ارزشی نخواهد داشت. در هریک از $q$ روز گذشته، یک ایمیل حاوی اطلاعات سرّی از فردی ناشناس به دست عمو رسیده است. اگر عمو اطلاعات دو روز پشت سر هم را به دو سازمان مختلف بفروشد، مجبور است از سازمان اول به سازمان دوم برود. میدانیم که عمو طوری این اطلاعات را فروخته که کمترین تعداد جابجایی بین سازمان‌ها را داشته باشد. با دانستن اینکه هریک از اطلاعات ایمیل‌ها مربوط به کدامین سازمان جاسوسی است، بگویید که کمترین تعداد جابجاشدن عمو بین سازمان‌های جاسوسی چقدر است. # ورودی سطر اول ورودی شامل عدد $n$ است که نمایانگر تعداد سازمان‌های جاسوسی عمو است. سپس در هریک از $n$ سطر بعدی نام یکی از این سازمان‌ها آمده است. نام هر سازمان با دیگری متفاوت است. هر نام میتواند شامل چند کلمه باشد که هریک از حروف کوچک یا بزرگ انگلیسی و اعداد تشکیل شده اند. سطر بعدی ورودی شامل عدد $q$ است که نمایانگر تعداد ایمیل‌های رسیده به دست عمو است. در $i$مین سطر از $q$ سطر بعدی نام سازمانی آمده است که اطلاعات ایمیل $i$م مربوط به آن است. $$2 \le n \le 100$$ $$0 \le q \le 1000$$ # خروجی در تنها سطر خروجی یک عدد چاپ کنید که برابر کمترین تعداد جابجاشدن عمو بین سازمان‌های جاسوسی است. # ورودی نمونه ``` 3 KGB Central Intelligence Agency Central Intelligence Agency 2 6 KGB Central Intelligence Agency Central Intelligence Agency Central Intelligence Agency 2 Central Intelligence Agency 2 KGB ``` # خروجی نمونه ``` 1 ``` عمو میتواند اطلاعات 3 روز اول را به Central Intelligence Agency 2 بفروشد و سپس به Central Intelligence Agency رفته و اطلاعات 3 روز بعدی را به آن ها بدهد.

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- عمو که فردی بسیار پول‌پرست است، به ساخت شکلات‌های طویل روی آورده. در جشن تولد عمو به او دنباله‌ای از $n$ شکلات داده شد. برخی از شکلات‌ها هم‌طعم بودند و برخی طعم متفاوتی داشتند. عمو پس از دیدن این مقدار بسیار زیاد شکلات، تصمیم گرفت بازه‌های پشت‌سر‌هم از دنباله‌ی شکلات‌ها که طعمشان برابر است را به هم بچسباند و شکلات‌های بزرگ برای فروش بسازد. وجدان مالی عمو به او اجازه میدهد که حداکثر $k$ طعم انتخاب کرده و شکلات‌‌های هدیه گرفته به آن طعم‌ها را بخورد و سپس ساخت شکلات‌های بزرگ را شروع کند. بنظر عمو هرچه این شکلات‌ها بزرگتر باشند بیشتر سود خواهد کرد، پس طوری حداکثر $k$ طعم را انتخاب کرده و شکلات‌های با آن طعم‌ها را میخورد که پس از حذف آن‌ شکلات‌ها از دنباله و ساخت شکلات‌های بزرگ، طول بزرگترین شکلات ساخته شده بیشینه شود. با داشتن دنباله‌ی طعم شکلات‌ها بگویید طول بزرگترین شکلات ساخته‌شده توسط عمو چقدر است. # ورودی سطر اول ورودی شامل دو عدد $n$ و $k$ است که به ترتیب نمایانگر تعداد شکلات‌های کوچک عمو و حداکثر تعداد طعم شکلات‌هایی که عمو میتواند از آن بخورد هستند. در سطر $i$م از $n$ سطر بعدی طعم شکلات $i$م دنباله آمده است. طعم‌ها بصورت اعداد صحیح بین ۰ و یک میلیارد در ورودی آمده‌اند. $$1 \le n \le 10^5$$ # خروجی در تنها سطر خروجی یک عدد چاپ کنید که برابر طول بزرگترین شکلاتیست که عمو میتواند بسازد. # ورودی نمونه ``` 9 1 2 6 3 6 6 3 6 5 6 ``` # خروجی نمونه ``` 4 ``` اگر عمو همه‌ی شکلات‌ها با طعم ۳ را بخورد، دنباله طعم شکلات‌ها برابر ۶ ۵ ۶ ۶ ۶ ۶ ۲ خواهد بود و با این دنباله ۴ شکلات بزرگ به طول‌های ۱ و ۱ و ۴ و ۱ ساخته میشود و طول بزرگترین آن‌ها ۴ است.

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- عمو که فردی بسیار پول پرست است، جهت صرفه‌جویی در تعداد حروف پیامک‌هایش به فشرده‌سازی رشته‌ها روی آورده. روش عمو برای فشرده‌سازی به این صورت است: او در ابتدا جایگشتی از اعداد ۱, ۲, ..., $k$ انتخاب میکند. سپس رشته‌ی خود را به دسته های پشت سر هم $k$ حرفی تقسیم میکند (طول رشته باید به $k$ بخش‌پذیر باشد) و روی هر دسته از حروف، جایگشت خود را اعمال میکند. سپس رشته‌ی بدست آمده را بوسیله‌ی روش RLE که در ادامه توضیح داده خواهد شد، فشرده میکند. اعمال جایگشت $p$ روی یک دسته از $k$ حرف یعنی حرف $p_1$م را در جایگاه اول قرار داده، حرف $p_2$م را در جایگاه دوم و... برای مثال اعمال جایگشت {۲ ,۴ ,۱ ,۳} روی رشته‌ی $abcd$ آن را تبدیل به $cadb$ میکند. اعمال این جایگشت با دسته دسته کردن روی رشته‌ی $abcdefgh$، رشته‌ی $cadbgehf$ را نتیجه میدهد. رشته‌ی جایگشت داده شده توسط RLE (یا run-length encoding) فشرده میشود. جهت جلوگیری از محاسبات پیچیده، طول رشته‌ی فشرده‌شده را برابر تعداد گروه حرف‌های برابر پشت سر هم درنظر میگیریم. برای مثال طول رشته‌ی $aabcaa$ پس از فشرده‌شدن توسط RLE را ۴ در نظر میگیریم. (یک گروه ۲ حرفی a، یک گروه تک حرفی b، یک گروه تک حرفی c و یک گروه ۲ حرفی a) عمو میخواهد پیامکی را با روش گفته شده فشرده کرده و بفرستد. واضح است که طول رشته‌ی نهایی به جایگشت انتخاب‌شده مربوط است. شما با داشتن متن پیامک عمو، جایگشتی انتخاب کنید که پس از فشرده‌سازی بوسیله‌ی آن طول پیامک کمینه شود و این طول کمینه را خروجی دهید. # ورودی سطر اول تنها شامل عدد $k$ است. در سطر بعدی پیامک عمو بصورت یک رشته از حروف کوچک انگلیسی به طول حداکثر ۵۰۰۰۰ آمده است. $$2 \le k \le 16$$ # خروجی در تنها سطر خروجی یک عدد چاپ کنید که برابر کمترین طول ممکن برای پیامک عمو است. # ورودی نمونه ``` 4 abcabcabcabc ``` # خروجی نمونه ``` 7 ``` در این مثال با انتخاب جایگشت {۲ ,۳ ,۴ ,۱} نتیجه‌ی بهینه بدست می‌آید.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- عمو که فردی بسیار پول‌پرست است، به برج‌سازی روی آورده. زمینی به عمو به ارث رسیده است و او میخواهد روی آن برج‌سازی کند. این زمین از بالا مانند جدولی با $n$ سطر و $m$ ستون دیده میشود که میتوان در خانه‌های آن برج ساخت. از قبل روی برخی از خانه های این جدول برج‌هایی نیمه‌کاره ساخته‌شده و عمو نمیتواند آن ها را خراب کند. همچنین بعلت خاک نامناسب، ساخت برج روی برخی از خانه های جدول امکان ندارد. مقدار سودی که عمو با فروش یک برج به دست می آورد برابر با تعداد پنجره‌های آن است که برابر است با تعداد ضلع‌های خانه‌ای که برج در آن ساخته شده و سمت دیگر آن ضلع، برج دیگری نیست. عمو میخواهد طوری برج‌سازی کند که پس از ساخت برج‌های نوساز و تکمیل برج های نیمه کاره پیشین، در مجموع با فروختن آن‌ها بیشترین سود را بدست آورد. با داشتن نقشه‌ی زمین عمو این بیشینه مقدار را بدست آورید. # ورودی سطر اول ورودی شامل دو عدد $n$ و $m$ است که نمایانگر تعداد سطر ها و تعداد ستون های جدول هستند. سپس در هریک از $n$ سطر بعدی، یک رشته به طول $m$ متشکل از یکی از سه کاراکتر . یا # و یا ? آمده است که به ترتیب نمایانگر خانه‌ی با خاک نامرغوب، خانه‌ی با برج نیمه‌کاره و خانه‌ی با توانایی ساخت برج هستند. $$1 \le n, m \le 50$$ # خروجی در تنها سطر خروجی یک عدد چاپ کنید که برابر بیشترین سود ممکن برای عمو است. # ورودی نمونه ۱ ``` 3 3 .?. .?. .#. ``` # خروجی نمونه ۱ ``` 8 ``` # ورودی نمونه ۲ ``` 5 8 .#...##. .##..?.. .###.#.# ??#..?.. ###?#... ``` # خروجی نمونه ۲ ``` 42 ```