المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۱۷:سوال ۳

Triples

مجموعه‌ی $A=\{1,2,…,n\}$ را در نظر بگیرید. $m$ زیرمجموعه‌ی سه عضوی از این مجموعه داده شده است. می‌خواهیم $\frac{n}{3}$ تا از این زیرمجموعه‌ها را به نحوی انتخاب کنیم که مجموعه‌ی $A$ را افراز کنند. به عبارت دیگر، هر یک از اعضای مجموعه‌ی $A$، عضو یکی از این زیر مجموعه‌ها باشد و هیچ دو زیرمجموعه‌ای اشتراک نداشته باشند.

این یک مسئله‌ی خروجی تنها می‌باشد. برای شما تعدادی فایل ورودی ساخته شده است که باید فایل‌های خروجی متناظرشان را ساخته و ارسال کنید. فایل‌های ورودی با نام‌های triples0.in، triples1.in، triples2.in، …، triples10.in به صورت فشرده ($zip$) در قسمت $Download$‌ در واسط مسابقات قرار دارد. شما باید فایل‌های خروجی triples0.out، triples1. out ، triples2. out ، …، triples10. Out را ساخته، در یک پوشه قرار دهید و پس از فشرده سازی (با $zip$ یا $gzip$) برای ارزش‌یابی ارسال کنید.

دقت کنید که تست‌های $6a$ و $6b$ و $6c$ همگی مربوط به تست ششم هستند و با هم در یک گروه قرار دارند. بنابراین تنها در صورتی نمره‌ی این تست را می‌گیرید که هر سه را درست جواب دهید.

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

ورودی

در سطر اول ورودی، دو عدد $n$ و $m$ با فاصله از هم قرار دارند.

در $m$‌سطر بعدی، زیر مجموعه‌های سه عضوی به شما داده می‌شود، به این نحو که در سطر $i+1$ام ورودی، سه عدد $b_i،a_i$ و $c_i$ با فاصله از هم قرار دارند که نشان‌دهنده‌ی اعضای زیرمجموعه‌ی $i$ام است.

زیرمجموعه‌های سه عضوی که در ورودی داده می‌شوند متفاوت هستند (به عبارت دیگر زیرمجموعه‌ی تکراری در ورودی وجود ندارد) و اندازه‌ی آرشیو ارسالی نمی‌تواند بیش از ۱۰۰ کیلوبایت باشد.

خروجی

در صورتی که مسئله جواب ندارد، در تنها سطر خروجی «NO» بنویسید. در غیر این صورت، در سطر اول فایل خروجی «Yes» بنویسید و در سطر دوم شماره‌ی سه‌تایی‌هایی را با فاصله از هم بنویسید که تشکیل افرازی از مجموعه‌ی $A$ می‌دهند.

از آن‌جا که در این مسئله باید فقط خروجی‌ها را برای ما ارسال کنید. لزومی ندارد که اجرای برنامه‌ی شما برای همه‌ی تست‌ها مدت زمان کمی طول بکشد.

محدودیت‌ها

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

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
6 5
6 4 1
2 4 6
2 5 3
6 5 1
6 3 6
Yes
3 1

ابزار صفحه