باگ کد مجید


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

مجید که به تازگی برنامه‌نویسی یاد گرفته است، شبه کدی برای مرتب سازی صعودی یک آرایه به اسم aa به طول nn نوشته است که به وضوح غلط است. این تکه کد به صورت زیر است:

for i = 1 to n - 2  
    for j = 1 to n - 1   
        if a[j] > a[j + 1]    
            swap(a[j], a[j + 1]) 
C

میلاد جایگشتی از اعداد ۱ تا nn دارد که بعضی از اعداد آن مشخص نیست و به جای آن صفر گذاشته شده است.

حال ما می‌خواهیم بدانیم آیا می‌توانیم جای صفرهای جایگشت، اعدادی قرار بدهیم به طوری که در انتها:

  1. کد مجید نتواند جایگشت را به درستی به صورت صعودی مرتب کند.
  2. هر یک از اعداد ۱ تا nn دقیقاً یک‌بار در آرایه آمده باشند.

(برای فهمیدن بهتر، بخش ورودی و توضیح نمونه‌ها را بخوانید.)

ورودی🔗

در خط اول عدد nn که تعداد اعداد جایگشت است به شما داده می‌شود. در خط بعدی nn عدد،بین 00 تا nn، که با فاصله جدا شده‌اند به شما داده می‌شود که اعداد جایگشت میلاد است. 1n100 0001 \le n \le 100\ 000

خروجی🔗

اگر می‌توانستیم صفر‌ها را به گونه‌ای عوض کنیم که شرایط صورت سوال را داشت در خط اول خروجی عبارت ‍‍‍‍Yes و در خط بعدی جایگشت کامل را به همراه اعدادی که به جای صفرها جایگزین شده‌اند چاپ کنید. (چنانچه چندین جایگشت وجود داشت، شما به دلخواه یکی از آن‌ها را چاپ کنید.)

در غیر اینصورت در یک خط عبارت No را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

4 
1 3 0 2 
Plain text

خروجی نمونه ۱🔗

No
Plain text

توضیح: تنها عددی که می‌تواند جای ۰ بگذارد عدد ۴ است که برنامه مجید می‌تواند این جایگشت را مرتب کند.

ورودی نمونه ۲🔗

4
0 0 0 0
Plain text

خروجی نمونه ۲🔗

Yes
4 3 2 1
Plain text

توضیح: اگر جایگشت فوق را به برنامه مجید بدهیم آن را به درستی مرتب نمی‌کند. توجه کنید که جایگشت فوق یکی از جواب های مسئله است؛ جایگشت‌های دیگری نیز وجود دارد که برنامه‌ی مجید روی آن‌ها درست کار نمی‌کند.

ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.