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

دنباله فیبوناچی دنباله‌ای معروف است که به صورت زیر تعریف می‌شود.$fib(1) = 1$$fib(2) = 2$ $fib(n) = fib(n-1) + fib(n-2)$

حال، برنامه‌ای بنویسید که با ورودی گرفتن یک عدد طبیعی $n$ یک رشته مانند $s_1 , s_2 , s_3 , ... , s_n\$ از علامت های + و - را چاپ کنید به طوری که $s_i$ مثبت باشد اگر و تنها اگر عدد $i$ جزو دنباله فیبوناچی باشد. برای فهم بهتر به مثال‌ها توجه کنید.

ورودی🔗

ورودی تنها شامل یک خط است که در آن یک عدد طبیعی $n$ آمده است. $1 \le n \le 100$

خروجی🔗

در تنها سطر خروجی یک رشته به طول $n$ که پاسخ مسئله است را چاپ کنید.

مثال🔗

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

15

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

+++-+--+----+--

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

4

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

+++-

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

در هر خانه از یک جدول $n$ در $m$ یک دومینوی ایستاده قرار داده شده است. هر دومینو یا عمودی است یا افقی (دومینوهای عمودی فقط در جهت بالا یا پایین می‌افتد و دومینوهای افقی فقط در جهت چپ یا راست). وقتی یک دومینو در یک جهت می‌افتد دومینوی موجود در خانه‌ی بعدی (در همان جهت) نیز اگر از نظر عمودی و افقی بودن مانند این دومینو باشد می‌افتد (دومینوها فقط در شرایط گفته شده بر روی دومینوهای دیگر تاثیر می‌گذارند).

می‌خواهیم تعدادی دومینو را بیاندازیم به طوری که همه‌ی دومینوها بیافتند. حداقل چند دومینو را باید بیاندازیم؟

ورودی🔗

در خط اول ورودی دو عدد $n$ و $m$ آمده است که تعداد سطرها و ستون‌های جدول را نشان می‌دهند.

در $n$ خط بعدی در هر خط، $m$ کاراکتر آمده که هر کدام نشان دهنده‌ی وضعیت یک دومینو است (| برای دومینوهای افقی و - برای دومینوهای عمودی)

$1 \le n, m \le 3000$

خروجی🔗

جواب مسئله را در یک خط چاپ کنید.

مثال🔗

ورودی نمونه🔗

3 3
|||
||-
||-

خروجی نمونه🔗

4

در ورودی نمونه سه دومینوی واقع در ستون اول را به سمت راست و دومینوی واقع در ستون سوم و سطر دوم را به سمت پایین می‌اندازیم.

• طراح سوال: انجمن جاواکاپ

از شما خواسته شده است طبق توضیحات زیر، یک پیاده‌سازی مقدماتی از سامانه ثبت نسخه دارویی را به زبان جاوا انجام دهید. ابتدا بسته‌ی ir.nimbo را دانلود کرده و محتوای آن را ببینید.

این سامانه دو هدف اصلی دارد. ثبت نسخه به صورت اینترنتی و جست‌وجوی دارو

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

جست‌وجوی دارو:🔗

برای این منظور در کلاس DrugRepository به عنوان مخزن داروها (Drug)، دو متد برای جست‌وجو در بین داروها قرار دارد که شما باید آن‌ها را پیاده‌سازی کنید:

• متد findDrugByExactName: در بین داروهای موجود در مخزن جست‌وجو می‌کند و دارویی که نامش دقیقا برابر با پارامتر ورودی است را بر می‌گرداند. (کوچک و بزرگ بودن حروف مهم است).
• متد search: زمانی که نام دارویی را به صورت دقیق نمی‌دانیم و تنها بخشی از نام دارو را می‌دانیم، از این متد می‌توان برای پیدا کردن نام دقیق دارو استفاده کرد. به این صورت که بخش‌هایی از نام دارو را که نمی‌دانیم، به جایش علامت % می‌گذاریم. مثلا اگر بدانیم نام داروی مورد نظر ما شامل رشته‌ی phen می‌باشد و ابتدا یا انتهاش ممکن است حروف دیگری هم وجود داشته باشد، پارامتر ورودی متد را به صورت %phen% وارد می‌کنیم. خروجی این متد، یک لیست شامل نام کلیه‌ی داروهایی خواهد بود که با رشته‌ی ورودی مطابقت دارند (کوچک و بزرگ بودن حروف مهم نیست).

ثبت نسخه:🔗

به این منظور، دو سرویس زیر باید پیاده‌سازی شوند. این سرویس‌ها در کلاس PrescriptionService قرار دارند و به صورت زیر باید عمل کنند:

۱. سرویس primaryRegisteration: با ثبت نسخه (Prescription) و ارایه‌ی یک موقعیت مکانی (Location) دلخواه به برنامه، نزدیک‎ترین داروخانه (Pharmacy) به آن موقعیت مکانی که تمامی آیتم‌های موجود (PrescriptionItem) در آن نسخه را دارد (موجودی داروخانه باید بیشتر یا مساوی تعداد داروی مورد نظر باشد)، پیدا کرده و برگرداند.

• اگر از تاریخ نسخه بیش از ۳۰ روز گذشته باشد، یعنی تاریخ انقضای نسخه گذشته است و باید استثنایی با پیام زیر پرتاب شود:

Prescription is expired.

• اگر هیچ داروخانه‌ای پیدا نشد که تمام آیتم‌های موجود در نسخه را داشته باشد، باید استثنایی با پیام زیر پرتاب شود:

No Pharmacy Found. Try Later...

• برای محاسبه‌ی فاصله‌ی بین دو موقعیت مکانی، یک شی از نوع واسط LocationService در اختیارتان قرار داده خواهد شد و با فراخوانی متد distance از آن، می‌توانید مقدار فاصله بین دو موقعیت مکانی را بدست آورید.

۲. سرویس finalRegisteration: این سرویس با گرفتن یک داروخانه و یک نسخه در پارامترهای ورودی، باید موجودی داروهای موجود در نسخه را در آن داروخانه به‌روز کند:

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

توضیحات تکمیلی:🔗

نسخه (Prescription):

• هر نسخه دارای تعدادی آیتم دارویی (PrescriptionItem) است که نام و تعداد هر آیتم در آن ذکر شده است.
• هر نسخه دارای یک تاریخ است.
• هر نسخه دارای یک موقعیت مکانی است که برای پیدا کردن نزدیک‌ترین داروخانه به آن موقعیت مکانی، مورد استفاده قرار می‎گیرد.

مخزن دارو (DrugRepository):

• کلیه‌ی داروها در این مخزن نگه‌داری می‌شوند و داروهای موجود در داروخانه‌ها، حتما زیرمجموعه‌ای از داروهای موجود در مخزن است.
• داروها بر اساس نامشان یکتا هستند.
• این کلاس باید Singleton باشد و تنها نمونه‌ (instance) آن باید توسط متد getInstance برگردانده شود.

داروخانه (Pharmacy):

• هر داروخانه دارای تعدادی دارو با مقدار موجودی (inventory) مشخص است.
• همچنین موقعیت مکانی داروخانه نیز مشخص است (طول و عرض جغرافیایی)
• با استفاده از متد addDrug باید بتوان یک دارو با مقدار موجودی مورد نظر را به لیست داروهای داروخانه (drugs) اضافه کرد (شما پیاده‌سازی کنید). دارویی که همچنان در داروخانه موجود است، به عنوان پارامتر به این متد داده نمی‌شود.
• با استفاده از متد removeDrug باید بتوان یک دارو را از لیست داروهای داروخانه حذف کرد (شما پیاده‌سازی کنید).
• با استفاده از متد getDrugInventory باید بتوان مقدار موجودی دارویی که در پارامتر ورودی داده شده است را به دست آورد (شما پیاده‌سازی کنید).
• با استفاده از متد getDrugCount تعداد کل داروهای موجود در داروخانه به دست می‌آید (شما پیاده‌سازی کنید).

دارو (Drug):

• هر دارو دارای یک قیمت اولیه (basePrice) است.
• هر دارویی ممکن است از نوع بیمه‌شده (Insured) و یا آزاد (Uninsurd) باشد. بنابراین برای دو زیرکلاس InsuredDrug و UninsurdDrug، متد getPrice باید به گونه‌ای پیاده‌سازی شود که قیمت داروهای تحت پوشش بیمه، ۳۰% کمتر محاسبه شود و قیمت داروهای آزاد، بدون تغییر و برابر با basePrice باشد.

نکته:

• در فایل‌های ارسالی، مجاز به تغییر امضا (signature) متد نیستید اما می‌توانید یک یا چند متد جدید اضافه کرده و در پیاده‌سازی خود استفاده کنید. تغییر امضای متد شامل مواردی مانند تغییر نوع و تعداد پارامتر‌های ورودی، تغییر نوع بازگشتی، تغییر نام متد، اضافه کردن throws declaration و ...
• به کلاس‌هایی که سازنده‌ی پارامتردار (Parameterized Constructor) دارند، نباید سازنده‌ی دیگری اضافه شود.

مثال:

فایل Program.java را دانلود کرده و در کنار فایل‌هایی که پیاده‌سازی کرده‌اید قرار داده و اجرا کنید. با اجرای آن، باید خروجی زیر در کنسول چاپ شود:

Before:
3
2
After:
null
1

دقت کنید در این مثال، هدف تنها اجرای finalRegisteration بوده است، بنابراین از یک پیاده‌سازی ساده‌لوحانه و غیرواقعی از LocationService استفاده شده است.

آنچه باید آپلود کنید: یک فایل زیپ شامل بسته‌ی ir.nimbo است. به صورتی که وقتی فایل زیپ را باز می‌کنیم، دقیقا شاخه‌ی ir را ببینیم که درون آن شاخه‌ی nimbo قرار دارد. در داخل شاخه‌ی nimbo هفت فایل زیر باید وجود داشته باشد:

UninsurdDrug.java InsuredDrug.java Drug.java DrugRepository.java Pharmacy.java Prescription.java PrescriptionService.java

• محدودیت زمان:‌ ۵ ثانیه
• محدودیت حافظه: ۴۰ مگابایت

آرایه‌ای با $n$ عدد داریم. تابع $f$ را در نظر بگیرید:

$f(x, y, z) = x \times y \times z + y \times z + z$

حال $n^3$ عدد از روی این $n$ عدد به این شکل می‌سازیم که به ازای هر سه‌تایی مرتب (نه لزوماً متمایز) آن را در تابع $f$ جاگذاری می‌کنیم و عدد حاصل را برمی‌داریم. میانگین، میانه و تعداد دفعات ظاهر شدن مُد بین این $n^3$ عدد را چاپ کنید.

میانه‌ی $k$ عدد برابر $\lfloor \frac{k}{2} \rfloor + 1$ اُمین آن‌ها در ترتیب مرتب‌شده است.

مُد برابر عددی‌ست که بیش‌ترین بار ظاهر شده است.

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

ورودی🔗

در خط اول ورودی $n$ آمده است. $1 \le n \le 500$ اعداد ورودی کم‌تر مساوی $10^6$ اند.

خروجی🔗

میانگین، میانه و تعداد دفعات ظاهر شدن مُد اعداد را چاپ کنید.

مثال🔗

ورودی نمونه🔗

2
1 3

خروجی نمونه🔗

14.0000000000 13 1

اعداد ساخته شده:

$f(1, 1, 1) = 3$ $f(1, 1, 3) = 9$ $f(1, 3, 1) = 7$ $f(1, 3, 3) = 21$ $f(3, 1, 1) = 5$ $f(3, 1, 3) = 15$ $f(3, 3, 1) = 13$ $f(3, 3, 3) = 39$

میانگین این اعداد برابر ۱۴ و میانه برابر ۱۳ و مد برابر ۳ است. تعداد دفعات ظاهر شدن مد برابر ۱ است.

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

به تازگی شرکت سحاب یک مسابقه برنامه نویسی برگزار کرده است. این مسابقه $d$ روز طول می‌کشد زمان شروع مسابقه $00:00:00$ روز اول است و زمان پایان مسابقه $23:59:59$ روز $d$ام است. در زمان برگزاری مسابقه تعدادی رویداد گزارش شده است. هر رویداد نشان می‌دهد که یک شرکت کننده به صفحه مسابقه وارد شده است. این رویداد به صورت کلی زیر به شما داده می‌شود.

$[ day: number | time: hh:mm:ss | name: user ]$

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

1. تعداد افرادی که آن روز وارد مسابقه شده اند.
2. تعداد افرادی که برای اولین بار وارد مسابقه شده اند.
3. تعداد افرادی که برای آخرین بار وارد مسابقه شده اند.

از شما خواسته می‌شود برای هر روز این گزارش‌ها را به دست آورید.

ورودی🔗

در اولین سطر ورودی دو عدد طبیعی $n$ و $d$ به شما داده می‌شود که به ترتیب نشان دهنده تعداد رویداد‌های مسابقه است و تعداد روز‌های برگزاری مسابقه است. $1 \le n, d \le 100$ در $n$ سطر بعدی در هر سطر یک خط به صورت زیر داده می‌شود. $[ day: number | time: hh:mm:ss | name: user ]$ که $number$ یک عدد طبیعی از $1$ تا $d$ است. $hh:mm:ss$ نشان دهنده لحظه آن رویداد است و $user$ یک رشته حداکثر ۱۰ حرفی از حروف کوچک انگلیسی است که نشان دهنده نام شرکت کننده است. به طور مثال یک رویداد به صورت زیر است. $[ day: 3 | time: 17:06:43 | name: mahdi ]$ تضمین می‌شود که ترتیب رویداد‌ها به ترتیب زمان به شما داده می‌شود.

خروجی🔗

خروجی برنامه شما شامل $d$ خط است و خط $i$ام نشان دهنده گزارش شما برای روز $i$ام است. در هر خط سه عدد صحیح با یک فاصله از هم چاپ کنید که عدد اول نشان دهنده تعداد افرادی که آن روز وارد مسابقه شده اند و عدد دوم نشان دهنده تعداد افرادی که برای اولین بار وارد مسابقه شده اند و عدد سوم نشان دهنده تعداد افرادی که برای آخرین بار وارد مسابقه شده اند.

مثال🔗

ورودی نمونه🔗

5 2
[ day: 1 | time: 00:00:37 | name: mohammad ]
[ day: 1 | time: 01:14:41 | name: alireza ]
[ day: 1 | time: 15:12:17 | name: mohammad ]
[ day: 2 | time: 21:16:00 | name: maryam ]
[ day: 2 | time: 23:59:33 | name: alireza ]

خروجی نمونه🔗

2 2 1
2 1 2

روز اول: دو شرکت کننده به نام‌های mohammad و alireza وارد مسابقه شده اند. دو شرکت کننده به نام‌های mohammad و alireza برای اولین بار وارد مسابقه شده اند. یک شرکت کننده به نام mohammad آخرین باری است که وارد مسابقه می‌شود.

روز دوم: دو شرکت کننده به نام‌های maryam و alireza وارد مسابقه شده اند. یک شرکت کننده به نام maryam برای اولین بار وارد مسابقه شده اند. دو شرکت کننده به نام‌های maryam و alireza آخرین باری است که وارد مسابقه می‌شود.

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

در ابتدا $n$ صف خالی داریم. در هر مرحله،

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

ورودی🔗

در خط اول ورودی دو عدد $n$ و $q$ آمده است که تعداد صف‌ها و تعداد اتفاقات را نشان می‌دهد.

در $q$ خط بعدی در هر خط،

• $1\ x$

یعنی $x$ به انتهای همه‌ی صف‌ها اضافه می‌شود.

• $2\ i\ j$

از ابتدای صف $i$اُم، $j$ عنصر حذف می‌شود. تضمین می‌شود $j$ حداقل صفر و حداکثر به اندازه‌ی طول فعلی صف است.

$1 \le n, q \le 300\ 000$

$1 \le i \le n$

$1 \le x \le 10^9$

خروجی🔗

به ازای هر اتفاق از نوع دوم عدد خواسته شده را چاپ کنید.

مثال🔗

ورودی نمونه🔗

2 5
1 5
1 17
2 1 1
1 1
2 2 3

خروجی نمونه🔗

5
23

۲ صف داریم و ۵ اتفاق می‌افتد:

1. عدد ۵ به تمامی صف‌ها اضافه می‌شود.
2. عدد ۱۷ به تمامی صف‌ها اضافه می‌شود.
3. از صف اول عنصر ابتدایی (عدد ۵) حذف می‌شود.
4. عدد ۱ به تمامی صف‌ها اضافه می‌شود.
5. از صف دوم ۳ عنصر اول (۵ و ۱۷ و ۱) حذف می‌شود.

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

از شما می‌خواهیم یک اسکریپت Bash با نام organize.sh بنویسید که به این وضعیت سر و سامان دهد.

جزئیات🔗

نحوه اجرای اسکریپت به این صورت است:

bash organize.sh path/to/src/dir path/to/dst/dir

اسکریپت باید تصاویر و فیلم‌ها را طبق قواعد زیر در پوشه مقصد کپی کند.

1. فایل‌ها باید بر اساس سال میلادی و همچنین بر اساس نوع (فیلم/عکس) دسته‌بندی شوند.
   • در پوشه مقصد به ازای هر سال باید یک پوشه به نام همان سال ایجاد شود.
   • داخل پوشه هر سال، تصاویر آن سال باید در پوشه‌ای به نام photos و فیلم‌های آن سال باید در پوشه‌ای به نام videos قرار بگیرند.
2. در مورد تصاویری که عرض (width) بزرگ‌تر از ۱۰۲۴ پیکسل دارند، باید به جای نسخه اصلی این تصاویر، نسخه کوچک‌شده آن‌ها در مقصد کپی شود. این تصاویر باید با حفظ نسبت طول به عرض طوری تغییر اندازه دهند که عرض تصویر مقصد ۱۰۲۴ پیکسل باشد.
3. تنها پوشه‌هایی که لازم است باید ایجاد شوند. بنابراین اگر برای یک سال هیچ تصویر یا فیلمی وجود ندارد، نباید پوشه آن سال ایجاد شود و یا اگر در یک سال هیچ فیلمی نداریم، نباید پوشه videos در پوشه آن سال ایجاد شود.
4. معیار تشخیص سال برای هر فایل، زمان آخرین تغییر محتوای فایل است. (last data modification time)
5. تشخیص عکس یا فیلم بودن فایل‌ها باید بر اساس پسوند فایل (به صورت case insensitive) طبق لیست‌های زیر صورت بگیرد.
   • پسوند تصاویر: jpg, jpeg, png
   • پسوند فیلم‌ها: mp4, avi, 3gp, mpeg, mkv, wmv, mov
6. فایل‌هایی که (طبق قاعده قبلی) تصویر یا فیلم نباشند باید نادیده گرفته شوند و کپی نشوند.

مثال🔗

وضعیت پوشه اول: (در این مثال فرض کنید زمان modification فایل‌ها همان زمانی است که در نام فایل آمده است.)

src
├── IMG_2235.jpg   [modified time: 2018/01/28]
├── travel_photos
│   ├── 2018-11-09_11-27-14.3gp
│   ├── IMG_20171017_052418.jpg
│   ├── 20180311_214539.JPG
│   ├── IMG_2237.jpg   [modified time: 2018/02/21]
│   └── note.txt
└── vid1
    ├── images
    │   └── IMG_2014-01-12.JPG
    └── VID_20170425_184731.mp4

وضعیت پوشه مقصد پس از اجرای اسکریپت:

dst
├── 2014
│   └── photos
│       └── IMG_2014-01-12.JPG
├── 2017
│   ├── photos
│   │   └── IMG_20171017_052418.jpg
│   └── videos
│       └── VID_20170425_184731.mp4
└── 2018
    ├── photos
    │   ├── 20180311_214539.JPG
    │   ├── IMG_2235.jpg
    │   └── IMG_2237.jpg 
    └── videos
        └── 2018-11-09_11-27-14.3gp

نکات🔗

• پوشه مقصد ممکن است قبل از اجرای اسکریپت وجود نداشته باشد. در این صورت اسکریپت شما باید پوشه مقصد را بسازد.
• نام فایل‌هایی که کپی می‌شوند نباید تغییر کند.
• به جز تصاویری که باید تغییر اندازه بدهند، محتوای سایر فایل‌ها نباید هنگام کپی شدن هیچ تغییری کند.
• فایل‌های پوشه اول نباید تغییری کند.
• فرض کنید برنامه ImageMagick بر روی سیستم نصب است.
• یک فایل Zip شامل اسکریپت organize.sh را آپلود کنید.

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

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

• هر زن به تعداد مسافرهای مرد یا معتادی که مجاور او هستند ناراحت می‌شود.
• هر مرد به تعداد معتادهایی که مجاور او هستند ناراحت می‌شود.
• هر معتاد به تعداد معتادهایی که مجاور او هستند ناراحت می‌شود.

می‌دانیم در یک تاکسی یک صندلی کنار راننده و سه صندلی در عقب قرار دارد و دو نفر که صندلی‌شان کنار هم باشد مجاور یکدیگرند (مسافری که روی صندلی کنار راننده می‌نشیند با هیچ کس مجاور نیست و مسافری که روی صندلی وسط در ردیف عقب می‌نشیند با دو نفر کناری خود مجاور است و دو نفری که در کنار درهای عقب می‌نشینند تنها با نفر وسط مجاورند).

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

ورودی🔗

ورودی تنها شامل یک خط است که در آن چهار عدد طبیعی $m$ و $w$ و $a$ و $t$ با فاصله از هم آمده است و به ترتیب تعداد مردها، زن‌ها، معتادها و تاکسی‌ها را نشان می‌دهد. تضمین می شود که وقتی مردها و زن ها و معتاد ها در تاکسی ها بنشینند صندلی خالی وجود نخواهد داشت. $0 \le m, w, a \le 100\ 000$ $1 \le t \le 100\ 000$

خروجی🔗

خروجی شامل $t$ جدول دو در سه است. که جدول‌ها با سطرهای خالی از هم جدا شده اند. اگر چند روش صحیح وجود دارد یک روش را به دلخواه چاپ کنید.

مثال🔗

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

1 2 1 1

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

ِD.A
WWM

در این حالت مجموع کل ناراحتی‌ها برابر ۱ است.

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

1 1 2 1

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

D.A
WAM

در این حالت مجموع کل ناراحتی‌ها برابر ۲ است.

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

3 3 2 2

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

D.A
MMM

D.A
WWW

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

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

تعدادی پردازش و تعدادی پردازش‌گر داریم (پردازش‌ها با شماره‌های $1$ تا $k$ و پردازش‌گرها با شماره‌های $1$ تا $n$ شماره گذاری شده‌اند). پردازش $i$ به $d_i$ ثانیه زمان نیاز دارد تا انجام شود و یک مجموعه از پردازش‌های پیش‌نیاز دارد. می‌خواهیم برای انجام هر پردازش یک زمان برای انجام شدن و یکی از پردازش‌گرها انتخاب کنیم تا در آن زمان آن پردازش را به آن پردازش‌گر مشخص شده اختصاص بدهیم. اگر یکی از پیش‌نیازهای یک پردازش پیش از اختصاص آن به پردازش‌گرش انجام نشده باشند، به اندازه‌ی مشخصی (وابسته به پردازش و پیش‌نیاز) به زمان انجام آن پردازش اضافه می‌شود (نیاز به مقداری محاسبات اضافی دارد).

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

ورودی🔗

در خط اول ورودی دو عدد $n$ و $k$ آمده است که تعداد پردازش‌گرها و پردازش‌ها را نشان می‌دهند.

در خط بعدی $k$ عدد آمده که $i$امین عدد نشان دهنده‌ی زمانی که برای انجام پردازش $i$ نیاز است.

در خط بعدی یک عدد $m$ آمده است که نشان دهنده‌ی تعداد روابط پیش‌نیازی بین پردازش‌هاست.

در $m$ خط بعدی در هر خط سه عدد $v$ و $u$ و $c$ آمده است که نشان می‌دهد پردازش $v$ پیش‌نیاز پردازش $u$ است و در صورت رعایت نشدن این پیش‌نیازی پردازش $u$، $c$ ثانیه بیشتر طول می‌کشد.

$1 \le n, k \le 100$ $1 \le m \le 10\ 000$ $1 \le c, d_i \le 1\ 000\ 000$

خروجی🔗

خروجی باید شامل $k$ خط باشد که در خط $i$ام از آن دو عدد $w$ و $t$ آمده است که نشان می‌دهند پردازش $i$ام در لحظه‌ی $t$ به پردازش‌گر $w$ اختصاص داده می‌شود.

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

مثال🔗

ورودی نمونه🔗

1 3
1 1 1
3
1 2 1
2 3 2
3 1 3

خروجی نمونه🔗

1 3
1 0
1 2

برای ورودی نمونه خروجی داده شده بهترین خروجی است (مجموع زمان پایان‌ها $4 + 2 + 3 = 9$ ) ولی برای مثال خروجی‌های زیر نیز قابل قبول است.

1 0
1 4
1 5

*مجموع زمان پایان‌ها $4 + 5 + 6 = 15$ *

1 4
1 3
1 0

*مجموع زمان پایان‌ها $5 + 4 + 3 = 12$ *