Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:سوال های تمرینی دوره ی تابستان:سوال ۲۳

Huffman

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

ما برای اینکه رشته را بتوانیم به یک کد دودویی تبدیل کنیم، باید ابتدا به هر کدام از حرف‌های رشته یک کد دودویی نسبت بدهیم.

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

به عبارت دیگر، کدی که به حرف iام نسبت داده می‌شود باید کوچک‌تر باشد از کدی که به حرف i+1ام نسبت داده شده است. از بین تمامی کدهای صعودی، کدی را انتخاب کنید، که طول آن کمینه شود.

ورودی

  • در خط اول ورودی عدد n آمده است.
  • سپس در خط بعدی n عدد بخوانید که عدد iام نمایانگر تعداد تکرارهای حرف iام در رشته است.
  • n حداقل ۲ و حداکثر ۴۰۰ است.
  • تمامی اعداد ورودی طبیعی و از ۱۰۰۰,۰۰۰,۰۰۰ تجاوز نمی‌کنند.

خروجی

خروجی شامل n خط می‌باشد که در خط iام خروجی، کد نسبت داده شده به حرف iام را چاپ کنید. در صورتی که بیش از یک جواب وجود داشت، یکی از آن‌ها را به دلخواه چاپ کنید.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
5
1 8 2 3 1
00
01
10
110
111

پاسخ

منتظر پر کردن این قسمت توسط علاقمندان هستیم.


ابزار صفحه