المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۸:عملی:سوال ۲۲

سوال ۲۲

یک پشته مرتب حاوی لیست ترتیب‌داری از اعداد و یک شمارنده‌ است که دو دستور را می‌پذیرد:

دستور $PUSH$: این دستور عدد مقدار شمارنده را یک واحد می‌افزاید و حاصل را به آخر لیست اضافه می‌کند. مثلا اگر پشته‌ی مرتبی حاوی لیست $(1,4,2,3,5)$ و محتوای عددی شمارنده ۷ باشد، پس از اجرای این دستور محتوای لیست، $(1,4,2,3,5,8)$ خواهد شد.

دستور $POP$: این دستور عدد واقع در آخر لیست را از لیست حذف می‌کند و آن را در خروجی چاپ می‌کند. بدیهی است که اگر لیست خالی باشد، اجرای این دستور غیر قانونی است. برای مثال اگر این دستور را روی پشته‌ی $(3,6,4,2)$ اعمال کنیم، عددی که در خروجی چاپ می‌شود، ۲ خواهد بود.

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

ورودی

عدد $n$ و این ترتیب خاص در فایل ورودی آمده‌اند. در سطر اول این فایل عددد $n$ و در سطر بعد از آن اعداد ۱ تا $n$ با ترتیب مورد نظر آمده‌اند.

خروجی

در هر خط از فایل خروجی یک دستور را بنویسید. برای نمایش دستور $Push$ از حرف بزرگ $U$ و برای نمایش دستور $POP$ از حرف بزرگ $P$ استفاده کنید.

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

ورودي نمونه خروجي نمونه
4
3 2 1 4
U
U
U
P
P
P
U
P

ابزار صفحه