+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- محمدرضاص که کنکورش را داده، میخواهد در همه‌ی مسابقات برنامه‌نویسی کوئرا شرکت کند؛ اما اکنون درگیر گرفتن تست بینایی از هنرجویان متقاضی گواهینامه‌ی رانندگی است. محمدرضاص در فاصله‌ی دو متری هنرجو یک کلمه از حروف انگلیسی قرار میدهد و این هنرجو باید از روی آن عیناً بنویسد. سپس محمدرضاص تعداد حرف‌های اشتباه نوشته شده را بعنوان مقدار کوری این فرد به او بگوید. محمدرضاص برای دادن مسابقه‌ی کوئرا عجله دارد و میخواهد بصورت کامپیوتری کارهای تست بینایی را انجام دهد، پس درخواست کرده که برنامه‌ای بنویسید که با ورودی گرفتن کلمه‌ی گذاشته‌شده در جلوی هنرجو و کلمه‌ی نوشته شده توسط هنرجو، تعداد اشتباه‌های هنرجو را خروجی دهد. # ورودی در سطر اول ورودی یک عدد $n$ آمده است که نمایانگر تعداد حروف کلمات است. در سطر دوم یک رشته متشکل از حروف کوچک و بزرگ انگلیسی آمده‌است که نمایانگر کلمه‌ی گذاشته‌شده جلوی هنرجوست. در سطر دوم نیز یک رشته متشکل از حروف کوچک و بزرگ انگلیسی آمده‌است که نمایانگر کلمه‌ی نوشته شده توسط هنرجوست. $$1 \le n \le 100\ 000$$ # خروجی تنها سطر خروجی باید شامل یک عدد صحیح نامنفی باشد که برابر تعداد حروفیست که هنرجو اشتباه نوشته است. # مثال ## ورودی نمونه ۱ ``` 3 ABC aBD ``` ## خروجی نمونه ۱ ``` 2 ``` هنرجو در این مثال حرف اول و سوم را اشتباه نوشته است. ## ورودی نمونه ۲ ``` 21 MASIOJESTDYSLEKTYKIEM MAsIOJSSTDXSIEKTYKLEM ``` ## خروجی نمونه ۲ ``` 5 ```

تست بینایی

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

محمدرضاص که کنکورش را داده، میخواهد در همه‌ی مسابقات برنامه‌نویسی کوئرا شرکت کند؛ اما اکنون درگیر گرفتن تست بینایی از هنرجویان متقاضی گواهینامه‌ی رانندگی است.

محمدرضاص در فاصله‌ی دو متری هنرجو یک کلمه از حروف انگلیسی قرار میدهد و این هنرجو باید از روی آن عیناً بنویسد. سپس محمدرضاص تعداد حرف‌های اشتباه نوشته شده را بعنوان مقدار کوری این فرد به او بگوید.

محمدرضاص برای دادن مسابقه‌ی کوئرا عجله دارد و میخواهد بصورت کامپیوتری کارهای تست بینایی را انجام دهد، پس درخواست کرده که برنامه‌ای بنویسید که با ورودی گرفتن کلمه‌ی گذاشته‌شده در جلوی هنرجو و کلمه‌ی نوشته شده توسط هنرجو، تعداد اشتباه‌های هنرجو را خروجی دهد.

ورودی🔗

در سطر اول ورودی یک عدد $n$ آمده است که نمایانگر تعداد حروف کلمات است.

در سطر دوم یک رشته متشکل از حروف کوچک و بزرگ انگلیسی آمده‌است که نمایانگر کلمه‌ی گذاشته‌شده جلوی هنرجوست.

در سطر دوم نیز یک رشته متشکل از حروف کوچک و بزرگ انگلیسی آمده‌است که نمایانگر کلمه‌ی نوشته شده توسط هنرجوست.

$1 \le n \le 100\ 000$

خروجی🔗

تنها سطر خروجی باید شامل یک عدد صحیح نامنفی باشد که برابر تعداد حروفیست که هنرجو اشتباه نوشته است.

مثال🔗

ورودی نمونه ۱🔗

3
ABC
aBD

خروجی نمونه ۱🔗

هنرجو در این مثال حرف اول و سوم را اشتباه نوشته است.

ورودی نمونه ۲🔗

21
MASIOJESTDYSLEKTYKIEM
MAsIOJSSTDXSIEKTYKLEM

خروجی نمونه ۲🔗

+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- محمدرضاص که کنکورش را داده، میخواهد در همه‌ی مسابقات برنامه‌نویسی کوئرا شرکت کند؛ اما اکنون درگیر دسته‌بندی کردن تعدادی مثلث است. محمدرضاص باید $n$‌مثلث را دسته‌بندی کند. او مختصات هر سه راس مثلث‌ها را دارد. در ابتدا او باید به ازای هر سه نقطه، بدست آورد که آیا این سه نقطه تشکیل یک مثلث با مساحت مثبت میدهند یا نه. (اگر سه نقطه‌ی داده شده همخط باشند و یا یک جفت نقطه برابر بینشان باشد، این سه تشکیل یک مثلث را نمیدهند. در این حالات اگر آن سه را به هم وصل کنیم مساحت شکل بدست آمده برابر ۰ میشود.) اگر سه نقطه داده شده مثلثی با مساحت مثبت بودند، او باید آن‌ها را دسته بندی کند. او مثلث‌ها را بر حسب زوایایشان به سه دسته تقسیم میکند: + مثلثی که یک زاویه بزرگتر از ۹۰ درجه دارد، مثلث باز، منفرجه یا obtuse نامیده میشود. + مثلثی که زاویه ۹۰ درجه دارد، مثلث قائم‌الزاویه، راست و یا right نامیده میشود. + مثلثی که هر سه زاویه‌ی آن کمتر از ۹۰ درجه است، مثلث حاد و یا acute نامیده میشود. همچنین محمدرضاص این مثلث‌ها را بر اساس طول ضلع‌هایشان به سه دسته تقسیم میکند: + مثلثی که سه ضلع با طول‌های مختلف دارد، مثلث مختلف‌الاضلاع یا scalene نامیده میشود. + مثلثی که دو ضلع برابر دارد، مثلث متساوی‌الساقین یا isosceles نامیده میشود. + مثلثی که هر سه ضلعش برابر است نیز متساوی‌الاضلاع یا equilateral نامیده میشود. میتوانید فرض کنید چنین مثلث‌هایی را به محمدرضاص نمیدهند. محمدرضاص برای اینکه به مسابقه‌ی کوئرا برسد، باید برنامه‌ای بنویسد که این کار را برای او انجام دهد. به او با نوشتن این برنامه کمک کنید! # ورودی در سطر اول ورودی یک عدد $n$ آمده است که نمایانگر تعداد مثلث‌های داده شده به محمدرضاص است. در هر سطر از $n$‌ سطر بعدی، مختصات رئوس یک مثلث آمده است. هریک از این خطوط شامل ۶ عدد صحیح $x_1, y_1, x_2, y_2, x_3, y_3$ است که مختصات سه راس این مثلث برابر $(x_1, y_1)$ و $(x_2, y_2)$ و $(x_3, y_3)$ است. $$1 \le n \le 100$$ $$-1\ 000 \le x_1, y_1, x_2, y_2, x_3, y_3 \le 1\ 000$$ # خروجی خروجی باید شامل $n$ سطر باشد. به ازای مثلث‌های ورودی، وضعیت و دسته‌بندی آن‌ها را به ترتیب ورودی در سطری جداگانه خروجی دهید. این وضعیت ۷ حالت میتواند داشته باشد: + `not a triangle` (اگر نقاط داده شده تشکیل یک مثلث با مساحت مثبت نمیدهند) + `isosceles acute triangle` + `isosceles obtuse triangle` + `isosceles right triangle` + `scalene acute triangle` + `scalene obtuse triangle` + `scalene right triangle` # مثال ## ورودی نمونه ``` 8 6 6 6 7 6 8 7 7 7 7 7 7 0 0 0 4 1 2 1 1 1 4 3 2 2 2 2 4 4 3 3 3 3 4 5 3 4 4 4 5 5 6 5 5 5 6 6 5 ``` ## خروجی نمونه ``` not a triangle not a triangle isosceles obtuse triangle scalene acute triangle isosceles acute triangle scalene right triangle scalene obtuse triangle isosceles right triangle ```

دسته‌بندی مثلث‌ها

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

محمدرضاص که کنکورش را داده، میخواهد در همه‌ی مسابقات برنامه‌نویسی کوئرا شرکت کند؛ اما اکنون درگیر دسته‌بندی کردن تعدادی مثلث است.

محمدرضاص باید $n$ ‌مثلث را دسته‌بندی کند. او مختصات هر سه راس مثلث‌ها را دارد.

در ابتدا او باید به ازای هر سه نقطه، بدست آورد که آیا این سه نقطه تشکیل یک مثلث با مساحت مثبت میدهند یا نه. (اگر سه نقطه‌ی داده شده همخط باشند و یا یک جفت نقطه برابر بینشان باشد، این سه تشکیل یک مثلث را نمیدهند. در این حالات اگر آن سه را به هم وصل کنیم مساحت شکل بدست آمده برابر ۰ میشود.)

اگر سه نقطه داده شده مثلثی با مساحت مثبت بودند، او باید آن‌ها را دسته بندی کند. او مثلث‌ها را بر حسب زوایایشان به سه دسته تقسیم میکند:

مثلثی که یک زاویه بزرگتر از ۹۰ درجه دارد، مثلث باز، منفرجه یا obtuse نامیده میشود.
مثلثی که زاویه ۹۰ درجه دارد، مثلث قائم‌الزاویه، راست و یا right نامیده میشود.
مثلثی که هر سه زاویه‌ی آن کمتر از ۹۰ درجه است، مثلث حاد و یا acute نامیده میشود.

همچنین محمدرضاص این مثلث‌ها را بر اساس طول ضلع‌هایشان به سه دسته تقسیم میکند:

مثلثی که سه ضلع با طول‌های مختلف دارد، مثلث مختلف‌الاضلاع یا scalene نامیده میشود.
مثلثی که دو ضلع برابر دارد، مثلث متساوی‌الساقین یا isosceles نامیده میشود.
مثلثی که هر سه ضلعش برابر است نیز متساوی‌الاضلاع یا equilateral نامیده میشود. میتوانید فرض کنید چنین مثلث‌هایی را به محمدرضاص نمیدهند.

محمدرضاص برای اینکه به مسابقه‌ی کوئرا برسد، باید برنامه‌ای بنویسد که این کار را برای او انجام دهد. به او با نوشتن این برنامه کمک کنید!

ورودی🔗

در سطر اول ورودی یک عدد $n$ آمده است که نمایانگر تعداد مثلث‌های داده شده به محمدرضاص است.

در هر سطر از $n$ ‌ سطر بعدی، مختصات رئوس یک مثلث آمده است. هریک از این خطوط شامل ۶ عدد صحیح $x_1, y_1, x_2, y_2, x_3, y_3$ است که مختصات سه راس این مثلث برابر $(x_1, y_1)$ و $(x_2, y_2)$ و $(x_3, y_3)$ است.

$1 \le n \le 100$ $-1\ 000 \le x_1, y_1, x_2, y_2, x_3, y_3 \le 1\ 000$

خروجی🔗

خروجی باید شامل $n$ سطر باشد. به ازای مثلث‌های ورودی، وضعیت و دسته‌بندی آن‌ها را به ترتیب ورودی در سطری جداگانه خروجی دهید. این وضعیت ۷ حالت میتواند داشته باشد:

not a triangle (اگر نقاط داده شده تشکیل یک مثلث با مساحت مثبت نمیدهند)
isosceles acute triangle
isosceles obtuse triangle
isosceles right triangle
scalene acute triangle
scalene obtuse triangle
scalene right triangle

مثال🔗

ورودی نمونه🔗

8
6 6 6 7 6 8
7 7 7 7 7 7
0 0 0 4 1 2
1 1 1 4 3 2
2 2 2 4 4 3
3 3 3 4 5 3
4 4 4 5 5 6
5 5 5 6 6 5

خروجی نمونه🔗

not a triangle
not a triangle
isosceles obtuse triangle
scalene acute triangle
isosceles acute triangle
scalene right triangle
scalene obtuse triangle
isosceles right triangle

+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- محمدرضاص که کنکورش را داده، میخواهد در همه‌ی مسابقات برنامه‌نویسی کوئرا شرکت کند؛ اما اکنون درگیر حدس زدن درصد‌های کنکور پویان (یک نوجوان تپل که تصمیم گرفته است وزن خود را کاهش دهد) است. محمدرضاص ابتدا بنابه شناختی که از پویان دارد، یک ترتیب برای درصد‌های درس‌های مختلف پویان پیش بینی میکند. او لیستی از این درس‌ها مینویسد که به نظرش درصد‌های پویان در این درس‌ها به ترتیب این لیست بصورت صعودی است. (همه میدانند که پویان هیچوقت در دو درس، درصد برابری نمیگیرد.) سپس پویان پیش‌بینی خودش از درصد‌هایش را رونمایی میکند. محمدرضاص هیچوقت در گفتن ترتیب درصدهای دروس پویان اشتباه نمیکند. پس اگر درصد‌هایی که پویان پیش‌بینی کرده به ترتیب محمدرضاص نبودند، پویان برخی از درصدها را اشتباه پیش‌بینی کرده است. برای درست کردن ترتیب پیش‌بینی شده‌ی پویان، آن‌ها تعدادی درس را انتخاب کرده و درصد گفته‌ی پویان در این درس‌ها را به هر عدد دلخواهی تغییر میدهند. (این عدد میتواند اعشاری هم باشد.) پس از این تغییرات درصدها باید به ترتیب پیش‌بینی شده توسط محمدرضاص باشند. پویان و محمدرضاص بین همه‌ی مجموعه درس‌هایی که میتوانند با تغییر درصد آن‌ها ترتیب را درست کنند، مجموعه درس‌هایی را انتخاب میکنند که کمترین تعداد درس را داشته باشد.(برای رسیدن به مسابقه‌ی کوئرا! ) اگر انتخاب این کمترین تعداد درس‌ها چند حالت داشت، آن‌ها مجموعه درس‌هایی را انتخاب میکنند که به اسامی آنها ترتیب الفبایی کوچکترین باشد. در هر مجموعه درس‌ها، اسامی را به ترتیب الفبایی از کوچک به بزرگ در نظر میگیریم. (مقایسه‌ی اسم‌ها طبق ترتیب الفبایی مانند مقایسه‌ی تعریف‌شده‌ی رشته‌ها در زبان‌های برنامه‌نویسی است.) فرض میکنیم که تعداد درس‌های داخل مجموعه $A$ و $B$ برابر است. مجموعه درس‌های $A$ به ترتیب الفبایی کوچکتر از مجموعه درس‌های $B$ است اگر و تنها اگر عدد $i$ وجود داشته باشد که اسم درس‌های اول، دوم، سوم، ... و $i - 1$م در $A$ و $B$ برابر باشد و اسم درس $i$م در $A$ از نظر الفبایی کوچکتر از اسم درس $i$م در $B$ باشد. با ورودی گرفتن ترتیب محمدرضاص و درصد‌های پویان، مجموعه درس‌های بهینه برای تغییر دادن را خروجی دهید. # ورودی در سطر اول ورودی حداکثر ۶۴ اسم درس آمده است که ترتیب پیش‌بینی شده‌ی درس‌ها از طرف محمدرضاص را نشان میدهد. همه‌ی این اسامی رشته‌های به طول کمتر-مساوی ۲۰ و متمایز هستند که از حروف کوچک انگلیسی و آندرلاین تشکیل شده‌اند. این درس‌ها به ترتیب درصد از کم به زیاد آمده‌اند. در سطر دوم درصدهای پویان برای این درس‌ها، به ترتیب سطر قبل آمده است. یعنی عدد $i$م این درس نمایانگر درصد گفته‌شده توسط پویان برای درس با نام $i$م در سطر اول است. درصدها اعداد صحیح بین ۱ و ۱۰۰ هستند. # خروجی در تنها سطر خروجی ایم درس‌هایی که در انتخاب بهینه، درصدشان تغییر میکند را بنویسید. این اسامی باید از نظر الفبایی به ترتیب صعودی خروجی داده شوند. تضمین میشود که در ورودی‌های داده‌شده، نیاز است درصد حداقل یک درس تغییر کند. # مثال ## ورودی نمونه ۱ ``` dini_1 zaban fizik_pish arabi_1_loghat shimi 20 15 40 30 41 ``` ## خروجی نمونه ۱ ``` arabi_1_loghat dini_1 ``` آن‌ها میتوانند با تغییر درصد درس‌های zaban و arabi_ 1_ loghat نیز ترتیب را درست کنند، اما چون dini _1 به ترتیب الفبایی کوچکتر از zaban است، آن‌ها dini _1 و arabi _1 _loghat را انتخاب و تغییر میدهند. به این شکل، آن ها میتوانند نمره‌ها را به ترتیب زیر کنند: ``` 10 15 40 40.5 41 ```

پیش‌بینی درصدها

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

محمدرضاص که کنکورش را داده، میخواهد در همه‌ی مسابقات برنامه‌نویسی کوئرا شرکت کند؛ اما اکنون درگیر حدس زدن درصد‌های کنکور پویان (یک نوجوان تپل که تصمیم گرفته است وزن خود را کاهش دهد) است.

محمدرضاص ابتدا بنابه شناختی که از پویان دارد، یک ترتیب برای درصد‌های درس‌های مختلف پویان پیش بینی میکند. او لیستی از این درس‌ها مینویسد که به نظرش درصد‌های پویان در این درس‌ها به ترتیب این لیست بصورت صعودی است. (همه میدانند که پویان هیچوقت در دو درس، درصد برابری نمیگیرد.)

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

برای درست کردن ترتیب پیش‌بینی شده‌ی پویان، آن‌ها تعدادی درس را انتخاب کرده و درصد گفته‌ی پویان در این درس‌ها را به هر عدد دلخواهی تغییر میدهند. (این عدد میتواند اعشاری هم باشد.) پس از این تغییرات درصدها باید به ترتیب پیش‌بینی شده توسط محمدرضاص باشند. پویان و محمدرضاص بین همه‌ی مجموعه درس‌هایی که میتوانند با تغییر درصد آن‌ها ترتیب را درست کنند، مجموعه درس‌هایی را انتخاب میکنند که کمترین تعداد درس را داشته باشد.(برای رسیدن به مسابقه‌ی کوئرا! ) اگر انتخاب این کمترین تعداد درس‌ها چند حالت داشت، آن‌ها مجموعه درس‌هایی را انتخاب میکنند که به اسامی آنها ترتیب الفبایی کوچکترین باشد.

در هر مجموعه درس‌ها، اسامی را به ترتیب الفبایی از کوچک به بزرگ در نظر میگیریم. (مقایسه‌ی اسم‌ها طبق ترتیب الفبایی مانند مقایسه‌ی تعریف‌شده‌ی رشته‌ها در زبان‌های برنامه‌نویسی است.) فرض میکنیم که تعداد درس‌های داخل مجموعه $A$ و $B$ برابر است. مجموعه درس‌های $A$ به ترتیب الفبایی کوچکتر از مجموعه درس‌های $B$ است اگر و تنها اگر عدد $i$ وجود داشته باشد که اسم درس‌های اول، دوم، سوم، ... و $i - 1$ م در $A$ و $B$ برابر باشد و اسم درس $i$ م در $A$ از نظر الفبایی کوچکتر از اسم درس $i$ م در $B$ باشد.

با ورودی گرفتن ترتیب محمدرضاص و درصد‌های پویان، مجموعه درس‌های بهینه برای تغییر دادن را خروجی دهید.

ورودی🔗

در سطر اول ورودی حداکثر ۶۴ اسم درس آمده است که ترتیب پیش‌بینی شده‌ی درس‌ها از طرف محمدرضاص را نشان میدهد. همه‌ی این اسامی رشته‌های به طول کمتر-مساوی ۲۰ و متمایز هستند که از حروف کوچک انگلیسی و آندرلاین تشکیل شده‌اند. این درس‌ها به ترتیب درصد از کم به زیاد آمده‌اند.

در سطر دوم درصدهای پویان برای این درس‌ها، به ترتیب سطر قبل آمده است. یعنی عدد $i$ م این درس نمایانگر درصد گفته‌شده توسط پویان برای درس با نام $i$ م در سطر اول است.

درصدها اعداد صحیح بین ۱ و ۱۰۰ هستند.

خروجی🔗

در تنها سطر خروجی ایم درس‌هایی که در انتخاب بهینه، درصدشان تغییر میکند را بنویسید. این اسامی باید از نظر الفبایی به ترتیب صعودی خروجی داده شوند.

تضمین میشود که در ورودی‌های داده‌شده، نیاز است درصد حداقل یک درس تغییر کند.

مثال🔗

ورودی نمونه ۱🔗

dini_1 zaban fizik_pish arabi_1_loghat shimi
20 15 40 30 41

خروجی نمونه ۱🔗

arabi_1_loghat dini_1

آن‌ها میتوانند با تغییر درصد درس‌های zaban و arabi_ 1_ loghat نیز ترتیب را درست کنند، اما چون dini _1 به ترتیب الفبایی کوچکتر از zaban است، آن‌ها dini _1 و arabi _1 _loghat را انتخاب و تغییر میدهند. به این شکل، آن ها میتوانند نمره‌ها را به ترتیب زیر کنند:

10 15 40 40.5 41

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- محمدرضاص که کنکورش را داده، میخواهد در همه‌ی مسابقات برنامه‌نویسی کوئرا شرکت کند؛ اما اکنون با شروع فصل گرما، درگیر نصب سقف برای جلوگیری تابش مستقیم آفتاب روی باغچه‌اش است. در باغچه‌ی محمدرضاص $n$ گل وجود دارد که نباید بهشان آفتاب مستقیم بخورد. محمدرضا میخواهد $k$ آفتابگیر مربعی شکل هم‌اندازه بخرد و آن‌ها را طوری روی باغچه‌اش نصب کند که روی هیچ گلی آفتاب مستقیم نتابد؛ یعنی هر گل زیر حداقل یک آفتابگیر باشد. او باید آفتابگیر‌ها را طوری نصب کند که اضلاع مربع آن‌ها موازی با اضلاع باغچه‌اش باشد. بخش‌هایی از آفتابگیرها میتوانند پس از نصب شدن روی هم بیفتند. محمدرضاص میخواهد آفتابگیرها را با کمترین طول ضلع ممکن بخرد. با ورودی گرفتن مختصات گل‌ها و عدد $k$، حداقل طول ضلع آفتابگیرها را خروجی دهید. # ورودی در سطر اول ورودی دو عدد $n$ و $k$ آمده‌اند که به ترتیب نمایانگر تعداد گل‌های باغچه‌ی محمدرضاص و تعداد آفتابگیر‌ها هستند. سپس در هریک از $n$ سطر بعدی، مختصات یک گل بصورت دو عدد صحیح $x_i, y_i$ آمده‌ است. (مختصات با فرض اینکه اضلاع باغچه، محورهای مختصات هستند داده شده‌اند.) $$1 \le k < n \le 15$$ $$0 \le x_i, y_i \le 64\ 000$$ # خروجی خروجی باید شامل یک عدد باشد که برابر کمترین طول ممکن برای آفتابگیرهای محمدرضاص است. # مثال ## ورودی نمونه ``` 5 2 1 1 2 2 3 3 6 6 7 8 ``` ## خروجی نمونه ``` 2 ```

پوش مربع

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

محمدرضاص که کنکورش را داده، میخواهد در همه‌ی مسابقات برنامه‌نویسی کوئرا شرکت کند؛ اما اکنون با شروع فصل گرما، درگیر نصب سقف برای جلوگیری تابش مستقیم آفتاب روی باغچه‌اش است.

در باغچه‌ی محمدرضاص $n$ گل وجود دارد که نباید بهشان آفتاب مستقیم بخورد. محمدرضا میخواهد $k$ آفتابگیر مربعی شکل هم‌اندازه بخرد و آن‌ها را طوری روی باغچه‌اش نصب کند که روی هیچ گلی آفتاب مستقیم نتابد؛ یعنی هر گل زیر حداقل یک آفتابگیر باشد. او باید آفتابگیر‌ها را طوری نصب کند که اضلاع مربع آن‌ها موازی با اضلاع باغچه‌اش باشد. بخش‌هایی از آفتابگیرها میتوانند پس از نصب شدن روی هم بیفتند.

محمدرضاص میخواهد آفتابگیرها را با کمترین طول ضلع ممکن بخرد. با ورودی گرفتن مختصات گل‌ها و عدد $k$ ، حداقل طول ضلع آفتابگیرها را خروجی دهید.

ورودی🔗

در سطر اول ورودی دو عدد $n$ و $k$ آمده‌اند که به ترتیب نمایانگر تعداد گل‌های باغچه‌ی محمدرضاص و تعداد آفتابگیر‌ها هستند. سپس در هریک از $n$ سطر بعدی، مختصات یک گل بصورت دو عدد صحیح $x_i, y_i$ آمده‌ است. (مختصات با فرض اینکه اضلاع باغچه، محورهای مختصات هستند داده شده‌اند.)

$1 \le k < n \le 15$

$0 \le x_i, y_i \le 64\ 000$

خروجی🔗

خروجی باید شامل یک عدد باشد که برابر کمترین طول ممکن برای آفتابگیرهای محمدرضاص است.

مثال🔗

ورودی نمونه🔗

خروجی نمونه🔗

+ محدودیت ز مان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- محمدرضاص که کنکورش را داده، میخواهد در همه‌ی مسابقات برنامه‌نویسی کوئرا شرکت کند؛ اما درگیری‌هایش باعث شدند او پس از شروع مسابقه برسد. محمدرضاص پس از اینکه متوجه شد دیگر نمیتواند در مسابقه‌ی ششم کوئرا شرکت کند، از ناراحتی از هوش رفت. او در خواب و خیال خودرا در یک صفحه شطرنجی با $H$ سطر و $W$ ستون یافت. او دید که سطرهای این جدول با اعداد طبیعی ۱ تا $H$ از بالا به پایین و ستون‌های آن با اعداد طبیعی ۱ تا $W$ از چپ به راست شماره گذاری شده‌اند و خودش روی خانه‌ی در سطر و ستون اول(خانه‌ی بالا-چپ جدول)، سوار بر یک اسب سفید متنظر حرکت است. همچنین دید که $n$ خانه از صفحه شطرنج شامل مانع هستند (یعنی اسب او نمیتاند وارد آن خانه‌ها شود) و روی خانه‌ی در سطر $H$ و ستون $W$ (خانه‌ی پایین-چپ جدول) دارد مسابقه‌ی کوئرا برگزار میشود! اسبی که محمدرضاص روی آن سوار است مانند همه‌ی اسب‌های شطرنج، میتواند بصورت $L$ حرکت کند. یعنی به خانه‌هایی میتواند برود که فاصله اقلیدسی آنها با خانه‌ی کنونی برابر $\sqrt 5$ است. محمدرضاص با خوشحالی قصد حرکت کردن به سمت خانه‌ی مسابقه کرد، اما متوجه شد که اسب رویاهای او شل است و تنها میتواند به سمت پایین-راست حرکت کند؛ یعنی پس از هر حرکت باید شماره سطر و ستونش زیاد بشود. دقت کنید که ممکن است محمدرضاص با این وضعیت نتواند به خانه‌ی مسابقه برسد، مثلاً اگر $H = 3$ و $W = 10$ اینگونه میشود. حال محمدرضاص میخواهد از فضای خیالی خود سوء استفاده کرده و از خود بیشترین تعداد کپی ممکن را بگیرد و از مسیرهای مختلف به محل برگزاری مسابقه برود. (بدون علم به اینکه مسابقه حضوری نیست!) اکنون محمدرضاص بیدار و هشیار شده و اطلاعات صفحه شطرنج خیالش را به ما داده است. با ورودی گرفتن $W, H$ و خانه‌های شامل مانع، تعداد مسیر‌های مختلفی که محمدرضاص میتوانست با اسب خود از گوشه‌ی بالا-چپ به گوشه‌ی پایین-راست جدول برود را خروجی دهید. چون که این عدد میتواند بسیار بزرگ باشد، باقیمانده‌ی این عدد پس از تقسیم بر $10007$ را خروجی دهید. # ورودی سطر اول ورودی شامل سه عدد $H$ و $W$ و $n$ است که به ترتیب نمایانگر تعداد سطرها و تعداد ستون‌های صفحه شطرنج خیالی محمدرضاص و تعداد خانه‌های شامل مانع آن هستند. سپس در $i$ مین سطر از هریک از $n$ سطر بعدی، دو عدد $h_i$ و $w_i$ آمده‌اند که نمایانگر سطر و ستون $i$مین مانع هستند. $$0 \le n \le 10$$$$1 \le h_i \le H \le 100\ 000\ 000$$$$1 \le w_i \le W \le 100\ 000\ 000$$ # خروجی تنها سطر خروجی باید شامل یک عدد باشد که برابر باقیمانده‌ی تعداد مسیرهای محمدرضاص پس از تقسیم بر $10007$ است. # مثال ## ورودی نمونه ۱ ``` 1 1 0 ``` ## خروجی نمونه ۱ ``` 1 ``` ## ورودی نمونه ۲ ``` 7 10 2 1 2 7 1 ``` ## خروجی نمونه ۲ ``` 5 ```

خیال شطرنجی

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

محمدرضاص که کنکورش را داده، میخواهد در همه‌ی مسابقات برنامه‌نویسی کوئرا شرکت کند؛ اما درگیری‌هایش باعث شدند او پس از شروع مسابقه برسد.

محمدرضاص پس از اینکه متوجه شد دیگر نمیتواند در مسابقه‌ی ششم کوئرا شرکت کند، از ناراحتی از هوش رفت. او در خواب و خیال خودرا در یک صفحه شطرنجی با $H$ سطر و $W$ ستون یافت. او دید که سطرهای این جدول با اعداد طبیعی ۱ تا $H$ از بالا به پایین و ستون‌های آن با اعداد طبیعی ۱ تا $W$ از چپ به راست شماره گذاری شده‌اند و خودش روی خانه‌ی در سطر و ستون اول(خانه‌ی بالا-چپ جدول)، سوار بر یک اسب سفید متنظر حرکت است. همچنین دید که $n$ خانه از صفحه شطرنج شامل مانع هستند (یعنی اسب او نمیتاند وارد آن خانه‌ها شود) و روی خانه‌ی در سطر $H$ و ستون $W$ (خانه‌ی پایین-چپ جدول) دارد مسابقه‌ی کوئرا برگزار میشود!

اسبی که محمدرضاص روی آن سوار است مانند همه‌ی اسب‌های شطرنج، میتواند بصورت $L$ حرکت کند. یعنی به خانه‌هایی میتواند برود که فاصله اقلیدسی آنها با خانه‌ی کنونی برابر $\sqrt 5$ است. محمدرضاص با خوشحالی قصد حرکت کردن به سمت خانه‌ی مسابقه کرد، اما متوجه شد که اسب رویاهای او شل است و تنها میتواند به سمت پایین-راست حرکت کند؛ یعنی پس از هر حرکت باید شماره سطر و ستونش زیاد بشود.

دقت کنید که ممکن است محمدرضاص با این وضعیت نتواند به خانه‌ی مسابقه برسد، مثلاً اگر $H = 3$ و $W = 10$ اینگونه میشود.

حال محمدرضاص میخواهد از فضای خیالی خود سوء استفاده کرده و از خود بیشترین تعداد کپی ممکن را بگیرد و از مسیرهای مختلف به محل برگزاری مسابقه برود. (بدون علم به اینکه مسابقه حضوری نیست!)

اکنون محمدرضاص بیدار و هشیار شده و اطلاعات صفحه شطرنج خیالش را به ما داده است. با ورودی گرفتن $W, H$ و خانه‌های شامل مانع، تعداد مسیر‌های مختلفی که محمدرضاص میتوانست با اسب خود از گوشه‌ی بالا-چپ به گوشه‌ی پایین-راست جدول برود را خروجی دهید.

چون که این عدد میتواند بسیار بزرگ باشد، باقیمانده‌ی این عدد پس از تقسیم بر $10007$ را خروجی دهید.

ورودی🔗

سطر اول ورودی شامل سه عدد $H$ و $W$ و $n$ است که به ترتیب نمایانگر تعداد سطرها و تعداد ستون‌های صفحه شطرنج خیالی محمدرضاص و تعداد خانه‌های شامل مانع آن هستند.

سپس در $i$ مین سطر از هریک از $n$ سطر بعدی، دو عدد $h_i$ و $w_i$ آمده‌اند که نمایانگر سطر و ستون $i$ مین مانع هستند.

$0 \le n \le 10$ $1 \le h_i \le H \le 100\ 000\ 000$ $1 \le w_i \le W \le 100\ 000\ 000$

خروجی🔗

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

مثال🔗

ورودی نمونه ۱🔗

1 1 0

خروجی نمونه ۱🔗

ورودی نمونه ۲🔗

7 10 2
1 2
7 1