المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۹:عملی:سوال ۱۰

Soldiers

$n$ سرباز با شماره‌های $1$ تا $n$ به ترتیب پشت‌سرهم در یک صف ایستاده‌اند، به‌طوری که سرباز $1$ در ابتدای صف و سرباز $n$ در انتهای صف قرار دارد. روی سر بعضی از سربازان یک کلاه گذاشته‌ایم. هر سرباز کلاه خودش و تمام افراد جلویش را می‌بیند (یعنی سرباز $n$ کلاه همه را می‌بیند).

گروهبان این سربازان، برای بررسی میزان هوشیاری آن‌ها، از برخی آنان خواسته تا روی یک برگه ابتدا شماره خودشان و سپس تعداد کلاه‌هایی که می‌بیند (شامل کلاه خودش در صورت وجود) را بنویسد. می‌دانیم در بین پرسش شوندگان دقیقا یک نفر (نه کم‌تر و نه بیش‌تر) دروغ گفته است؛ یعنی تعداد کلاه‌هایی که روی کاغذ برای ما نوشته متفاوت با تعداد کلاه‌هایی بوده است که او می دیده. و البته با شناخت قبلی گروهبان تنها به برخی از پرسش شدگان (و نه همه‌ی آن‌ها) مظنون است و مطمئن است سرباز دروغگو بین یکی از این مظنونین است.

اکنون گروهبان از شما می‌خواهد تا با دریافت کاغذ و لیست مظنونین، مشخص کنید که آیا سرباز دروغگو به صورت یکتا قابل تشخیص است یا خیر؛ و اگر هست کدام سرباز است.

ورودی

  • هر ورودی شما چند سناریو است. در سطر اول ورودی تعداد این سناریوها ($t$) آمده است و در ادامه این سناریوها پشت‌سرهم می‌آیند.
  • برای هر سناریو ابتدا مقدار $n$ (تعداد سربازان) و سپس $k$ (تعداد پرسش شدگان) در یک سطر درج می‌گردد.
  • سپس در $k$ سطر بعدی، در سطر اطلاعات مربوط به یک پرسش‌شونده به صورت $n_i~a_i~s_i$ می‌آید که $n_i$ (اولین عدد سطر) شماره سرباز است. $a_i$ پاسخ سرباز به ماست (تعداد کلاه‌هایی که ادعا می‌کند دیده). و نهایتا $s_i$ برابر $1$ است اگر این سرباز مظنون به درغگو بودن است و $0$ است اگر مظمئن هستیم سرباز راستگو است.
  • $1\leq k \leq n \leq 3000$
  • شماره سربازان بین $1$ تا $n$ است و جواب هر سرباز نیز بین $0$ تا $n$ است.
  • می‌دانیم در بین پرسش شدگان حداقل یک مظنون وجود دارد.
  • تمام ورودی‌ها بر اساس یک حالت واقعی قرار دادن کلاه و دروغ گفتن دقیقا یک نفر، شکل گرفته‌اند.

خروجی

  • خروجی شما $t$ سطر است؛ هر سطر جواب بک سناریو (به ترتیب).
  • برای هر سناریو در صورتی که سرباز دروغگو را نمی‌توان الزاما به صورت یکتا از بین مظنونین پیدا کرد تنها مقدار $0$ را بنویسید. در غیر این‌صورت فقظ شماره سرباز درغگو را بنویسید.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
3‎
6 3
1 2 1
2 2 1
3 2 1
2 2
1 0 1
2 2 1
5 3
2 2 1
5 5 0
4 3 1
1
0
4

ابزار صفحه