حل سوال های دانشگاهی

---

شرح پروژه

کیانوش متقاضی عضویت در سازمان OC است. در روز دوم مصاحبه، سازمان خلاقیت او را مورد بررسی قرار داده است.

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

کیانوش تصمیم گرفت که طوری بسته‌ها را جابجا کند که آن‌ها به شکل زیرمستطیلی با ابعاد دلخواه از جدول قرار بگیرند. روی هر خانه‌ی آن زیرمستطیل باید دقیقاً یک بسته کاه قرارگیرد و همچنین روی خانه‌‌های خارج از این مستطیل باید بسته‌ی کاهی نباشد. کیانوش میتواند در یک حرکت یک بسته‌ی کاه را از روی یک خانه‌ی جدول برداشته و روی خانه‌ی دیگری از آن بگذارد. او قصد دارد از این مستطیل بعنوان پس‌زمینه استفاده کند و با چوب و سنگ‌هایی که پیدا میکند علامت حق تکثیر (یا copyright) را روی آن حک کند.

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

ورودی

سطر اول ورودی شامل دو عدد nnn و mmm است که نمایانگر طول مزرعه و تعداد بسته‌های کاه است.

سپس در هریک از mmm سطر بعدی دو عدد آمده است که به ترتیب بیانگر شماره سطر و ستون یک بسته‌ی کاه است. سطر‌های جدول را از بالا به پایین و ستون‌‌های آن را از چپ به راست با اعداد ۱ تا nnn شماره گذاری میکنیم.

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

1≤n≤1001 \le n \le 1001≤n≤100 1≤m≤n21 \le m \le n^21≤m≤n​2​​

خروجی

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

ورودی نمونه ۱ 3 2 2 2 2 2 خروجی نمونه ۱ 1 ورودی نمونه ۲ 4 6 1 1 1 2 1 3 2 1 4 3 4 4 خروجی نمونه ۲ 2

در این مثال کافیست دو بسته‌ی کاه انتهایی را به ستون‌های دوم و سوم از سطر دوم انتقال دهیم بطوری که بسته‌های کاه مستطیلی با ۲ سطر و ۳ ستون در جدول تشکیل دهند.

فرض كنيد ماتريس A تعداد k عضو غير صفر دارد ماتريس معادل آن ماتريسي با ابعاد k*3 است كه هر سطر آن به ترتيب شامل شماره سطر،شماره ستون و مقدار يكي از عناصر غير صفر A باشد.به عنوان مثال:

و ترانهاده ي يك ماتريس هم ماتريسي است كه جاي سطر و ستون آن عوض شده باشد يعني:

ميخواهيم برنامه اي بنويسيم كه ابتدا تعداد سطرها و تعداد ستون ها و سپس ماتريس A را به صورت سطر به سطر دريافت كرده ترانهاده آن را محاسبه كرده و درنهايت ماتريس معادل ماتريس ترانهاده ي محاسبه شده را در خروجي چاپ كند. دقت كنيد اعداد ماتريس معادل خروجي بايد با يك space از هم جدا شوند.

مثال ورودی نمونه 3 2 0 5 2 0 1 4

مثال

خروجي نمونه 1 2 2 1 3 1 2 1 5 2 3 4

این پروژه شامل 2 فایل مهم است، لطفا قبل از ارسال پیشنهاد حتما نسبت به بررسی این فایل اقدام فرمایید.

مهارت ها و تخصص های مورد نیاز

---

---