المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳

دیشب پس از قهرمانی تیم $1$ در مسابقات آسیایی کبدی یک فاجعه‌ی باور نکردنی رخ داد! صبح امروز کشف شد نوشته زیر جام مسابقات که نام قهرمان مسابقات بر روی آن ثبت می شود، تغییر کرده است. پلیس قبل از رسانه‌ای شدن موضوع تمام مظنونین به ارتکاب این دسیسه را دستگیر کرد و مورد بازجویی قرار داد. در طول بازجویی از مظنونی که به حضور در موزه‌ی نگه‌داری جام در لحظه‌ی $t$ اعتراف کرده بود، این جمله شنیده شد: «تیم $a$ صدبار شرف داره به تیم $b$!» کارآگاهان خبره از این جمله چنین برداشت کردند که در لحظه‌ی حضور مظنون در موزه، در صورتی که نام قهرمان $a$ ثبت شده باشد، مظنون آن را به $b$ تغییر داده است.

همچنین کارآگاهان در طول بررسی‌ها به بعضی اطلاعات تکمیلی نیاز دارند. آن‌ها می‌خواهند بدانند با توجه با اعترافات فعلی، نام قهرمان در لحظه‌ی $t$ چه چیزی بوده است؟

شما $q$ پرسمان در پیش رو دارید. هر کدام یا نتیجه‌ی یک بازجویی است که در اختیار شما قرار می‌گیرد، و یا یک پرسش است که شما باید به آن پاسخ بدهید.

ورودی

  • در سطر اول ورودی عدد طبیعی $q$، تعداد پرسمان‌ها آمده است.
  • در هریک از $q$ سطر بعد، نتیجه‌ی یک بازجویی به شکل ‍‍‍‍$t \ a \ b$ ~ و یا یک پرسش به شکل $t$ ? آمده‌است. تمام زمان‌های آمده در ورودی متمایزند.
  • دقت کنید در ابتدا نام تیم $1$ زیر جام نوشته شده‌ است.
  • $1 \leq q \leq 2 * 10^5$
  • $1 \leq t \leq 10^9$
  • $1 \leq a, b \leq 2 * 10^5$

خروجی

برای هر پرسش، جواب را در سطری جداگانه چاپ کنید.

زیرمسئله‌ها

  • زیرمسئله اول (۵ نمره): $q \leq 10000$
  • زیرمسئله دوم (۱۰ نمره): $a, b \leq 2$ و $q \leq 50000$
  • زیرمسئله سوم (۱۵ نمره): $a, b \leq 100$ و $q \leq 50000$
  • زیرمسئله چهارم (۳۰ نمره): $q \leq 50000$
  • زیرمسئله پنجم (۱۵ نمره): $a, b \leq 100$
  • زیرمسئله ششم (۲۵ نمره): بدون محدودیت اضافی

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
7
? 10
~ 5 2 3
? 8
~ 1 1 2
? 11
~ 3 2 4
? 6
1
1
3
4

ابزار صفحه