پروژه طراحی الگوریتم (اختیاری)

سوال:

تعدادی مکعب مستطیل داریم که هر کدام دارای طول(x)، عرض(y)، و ارتفاع(z) مشخص هستند. می خواهیم بلندترین ارتفاعی که بوسیله روی هم قرار دادن این مکعب مستطیل ها یافت را پیدا کنیم.

محدودیتی که در حل این مسئله داریم اینکه در صورتی اجازه داریم مکعب مستطیلی را بالای مکعب مستطیل دیگر قرار دهیم که وجهی از مکعب مستطیل بالا که بر روی وجهی از مکعب مستطیل پایین قرار می گیرد حتما درون آن باشد (بزرگتر و مساوی نباشد)

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

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

ورودی:

فایلی به نام input.txt که در خط اول آن تعداد مکعب مستطیل ها (n)

و در n خط بعد اندازه مکعب مستطیل ها که با فاصله از هم جدا شده اند، آمده است (x y z)

خروجی:

فایل به نام output.txt که در خط اول آن حداکثر ارتفاع بدست آمده و در خطوط بعدی ترتیب مکعب هایی که بر روی هم قرار گرفته به ترتیب از بالا به پایین(عدد اول در هر خط ارتفاع آن مکعب).

مثال:

input.txt:
3
2 3 7
1 5 4
3 2 1

output.txt:
12
3 1 2
7 2 3
2 3 7

نکات:

نمره این پروژه 2 نمره علاوه بر بیست می باشد.

تحویل پروژه بصورت حضوری است.

به برنامه ای که توسط خود دانشجو نوشته نشده باشد و یا کپی شده باشد، نمره ای تعلق نمی گیرد.

زمان تحویل پروژه یکشنبه 13 دی

زمان ارائه دوشنبه 14 دی

تکمیلی:

به ازای فایل ورودی زیر جواب برابر 2841 می شود:

input.txt

output.txt