- محدودیت زمان: ۰.۵ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
محمدرضاص که کنکورش را داده، میخواهد در همه‌ی مسابقات برنامه‌نویسی کوئرا شرکت کند؛ اما اکنون درگیر حدس زدن درصدهای کنکور پویان (یک نوجوان تپل که تصمیم گرفته است وزن خود را کاهش دهد) است.
محمدرضاص ابتدا بنابه شناختی که از پویان دارد، یک ترتیب برای درصدهای درس‌های مختلف پویان پیش بینی میکند. او لیستی از این درس‌ها مینویسد که به نظرش درصدهای پویان در این درس‌ها به ترتیب این لیست بصورت صعودی است. (همه میدانند که پویان هیچوقت در دو درس، درصد برابری نمیگیرد.)
سپس پویان پیش‌بینی خودش از درصد‌هایش را رونمایی میکند. محمدرضاص هیچوقت در گفتن ترتیب درصدهای دروس پویان اشتباه نمیکند. پس اگر درصد‌هایی که پویان پیش‌بینی کرده به ترتیب محمدرضاص نبودند، پویان برخی از درصدها را اشتباه پیش‌بینی کرده است.
برای درست کردن ترتیب پیش‌بینی شده‌ی پویان، آنها تعدادی درس را انتخاب کرده و درصد گفته‌ی پویان در این درس‌ها را به هر عدد دلخواهی تغییر میدهند. (این عدد میتواند اعشاری هم باشد.) پس از این تغییرات درصدها باید به ترتیب پیش‌بینی شده توسط محمدرضاص باشند. پویان و محمدرضاص بین همه‌ی مجموعه درس‌هایی که میتوانند با تغییر درصد آنها ترتیب را درست کنند، مجموعه درس‌هایی را انتخاب میکنند که کمترین تعداد درس را داشته باشد.(برای رسیدن به مسابقه‌ی کوئرا! ) اگر انتخاب این کمترین تعداد درس‌ها چند حالت داشت، آنها مجموعه درس‌هایی را انتخاب میکنند که به اسامی آنها ترتیب الفبایی کوچکترین باشد.
در هر مجموعه درس‌ها، اسامی را به ترتیب الفبایی از کوچک به بزرگ در نظر میگیریم. (مقایسه‌ی اسم‌ها طبق ترتیب الفبایی مانند مقایسه‌ی تعریف‌شده‌ی رشته‌ها در زبان‌های برنامه‌نویسی است.) فرض میکنیم که تعداد درس‌های داخل مجموعه $A$ و $B$ برابر است. مجموعه درس‌های $A$ به ترتیب الفبایی کوچکتر از مجموعه درس‌های $B$ است اگر و تنها اگر عدد $i$ وجود داشته باشد که اسم درس‌های اول، دوم، سوم، ... و $i - 1$م در $A$ و $B$ برابر باشد و اسم درس $i$م در $A$ از نظر الفبایی کوچکتر از اسم درس $i$م در $B$ باشد.
با ورودی گرفتن ترتیب محمدرضاص و درصدهای پویان، مجموعه درس‌های بهینه برای تغییر دادن را خروجی دهید.
ورودی
در سطر اول ورودی حداکثر ۶۴ اسم درس آمده است که ترتیب پیش‌بینی شده‌ی درس‌ها از طرف محمدرضاص را نشان میدهد. همه‌ی این اسامی رشته‌های به طول کمتر-مساوی ۲۰ و متمایز هستند که از حروف کوچک انگلیسی و آندرلاین تشکیل شده‌اند. این درس‌ها به ترتیب درصد از کم به زیاد آمده‌اند.
در سطر دوم درصدهای پویان برای این درس‌ها، به ترتیب سطر قبل آمده است. یعنی عدد $i$م این درس نمایانگر درصد گفته‌شده توسط پویان برای درس با نام $i$م در سطر اول است.
درصدها اعداد صحیح بین ۱ و ۱۰۰ هستند.
خروجی
در تنها سطر خروجی اسم درس‌هایی که در انتخاب بهینه، درصدشان تغییر میکند را بنویسید. این اسامی باید از نظر الفبایی به ترتیب صعودی خروجی داده شوند.
تضمین میشود که در ورودی‌های داده‌شده، نیاز است درصد حداقل یک درس تغییر کند.
مثال
ورودی نمونه ۱
dini_1 zaban fizik_pish arabi_1_loghat shimi
20 15 40 30 41
خروجی نمونه ۱
arabi_1_loghat dini_1
آنها میتوانند با تغییر درصد درس‌های zaban و arabi_ 1_ loghat نیز ترتیب را درست کنند، اما چون dini _1 به ترتیب الفبایی کوچکتر از zaban است، آنها dini _1 و arabi _1 _loghat را انتخاب و تغییر میدهند. به این شکل، آن ها میتوانند نمره‌ها را به ترتیب زیر کنند:
10 15 40 40.5 41
ارسال پاسخ برای این سؤال