راهنمایی سؤالات مسابقه پیاده‌سازی کارآموزشو

سلام!

خب، بدون مقدمه بریم سراغ راه‌حل‌های سؤالات مسابقه‌ی پیاده‌سازی کارآموزشو. در صورتی که متوجه راه‌حلی نشدید، می‌تونید در بخش نظرات سؤالات و ابهام‌های خودتون رو مطرح کنید. همچنین اگه راه‌حل دیگه‌ای برای سؤالات دارید، خوشحال می‌شیم که راه‌حلتون رو در بخش نظرات با ما و دوستانتون به اشتراک بذارید.

بازه آزمونی

اگر زمان وارد شدن فرد به جلسه (x) کوچک‌تر از زمان شروع آزمون (s) باشد، باید عبارت exam did not started! را چاپ کرد. در غیر این‌صورت، اگر x بزرگ‌تر یا مساوی زمان پایان آزمون (f) باشد، باید عبارت exam finished! را چاپ کرد. در غیر این‌صورت، باید کمینه‌ی مدت زمان پاسخگویی به سؤالات (l) و f - x را چاپ کرد.

پیچیدگی زمانی:‌ O(1)

نیو فولدر

از آن‌جایی که فولدرها باید به‌صورت مرتب‌شده چاپ شوند، ساختمان داده‌ی مناسب این سؤال map (یا TreeMap در جاوا) است. اگر نام فولدر از قبل موجود نباشد، باید آن را با عدد صفر متناظر کرد. در غیر این‌صورت، اگر فرض کنیم قرار است فولدر x را برای yاُمین اضافه کنیم، باید مقدار متناظر با x را یک واحد افزایش داد و مقدار متناظر با x (y) را نیز برابر با صفر قرار داد. پس از افزودن هر فولدر، باید یک پیمایش روی map انجام داد و نام همه‌ی فولدرها را چاپ کرد.

پیچیدگی زمانی: O(n^2 \log n)

QSay

تنها کافی است تا یک لیست از خطوط داشته باشیم و روی کلمات متن ورودی (که آن را s می‌نامیم) پیمایش کنیم. هر زمان که طول خط فعلی از حداکثر طول هر خط بیشتر شود، باید به خط بعدی رفت. در نهایت، باید اندازه‌ی طولانی‌ترین خط ساخته‌شده را به‌دست آورد تا براساس آن، تعدادی space به خطوط کوتاه‌تر اضافه شود.

پیچیدگی زمانی: O(|s|)

تاس‌اندازی

کافی است تا یک آرایه‌ی شش‌عضوی از اعداد هر وجه تاس نگه‌داری کنیم. می‌توان آن را به‌ترتیب زیر فرض کرد:

• بالا (اندیس صفر): ۵
• پایین (اندیس ۱): ۲
• چپ (اندیس ۲): ۴
• راست (اندیس ۳): ۳
• جلو (اندیس ۴): ۱
• پشت (اندیس ۵): ۶

در حرکت a، جابه‌جایی اندیس‌ها به‌صورت زیر خواهد بود:

dice[0], dice[5], dice[1], dice[4] = dice[4], dice[0], dice[5], dice[1]

در حرکت b، جابه‌جایی اندیس‌ها به‌صورت زیر خواهد بود:

dice[0], dice[5], dice[1], dice[4] = dice[5], dice[1], dice[4], dice[0]

در حرکت c، جابه‌جایی اندیس‌ها به‌صورت زیر خواهد بود:

dice[0], dice[2], dice[1], dice[3] = dice[2], dice[1], dice[3], dice[0]

در حرکت d، جابه‌جایی اندیس‌ها به‌صورت زیر خواهد بود:

dice[0], dice[2], dice[1], dice[3] = dice[3], dice[0], dice[2], dice[1]

در حرکت e، جابه‌جایی اندیس‌ها به‌صورت زیر خواهد بود:

dice[4], dice[3], dice[5], dice[2] = dice[3], dice[5], dice[2], dice[4]

در حرکت f، جابه‌جایی اندیس‌ها به‌صورت زیر خواهد بود:

dice[4], dice[3], dice[5], dice[2] = dice[2], dice[4], dice[3], dice[5]

پیچیدگی زمانی: O(n)

کتاب‌خوان کالجی

برای نگه‌داری اطلاعات کتاب‌ها، می‌توان از تعدادی HashMap یا همان unordered_map استفاده کرد. تنها چالش موجود در سؤال، است که اگر فصل y پیش‌نیاز مستقیم یا غیرمستقیم فصل x باشد و بخواهیم فصل x را به پیش‌نیازهای فصل y اضافه کنیم، این اتفاق نباید بیفتد. برای بررسی این مورد، می‌توان از ساختمان داده‌ی disjoint-set استفاده کرد. برای بهبود پیچیدگی زمانی آن، می‌توان از تکنیک نخ‌کشی (path compression) استفاده کرد.

پیچیدگی زمانی: O(n \log^* n) (n تعداد دستورات ورودی است.)

جدول امتیازات

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

پیچیدگی زمانی: O(n) (زیرا در بدترین حالت، هر بار باید جدول امتیازات یک مسابقه چاپ شود.)