المپدیا

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

ابزار کاربر

ابزار سایت


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

گوجه

سکانس اوّل‎:

صفحه سیاه است. سکوت مطلق. صدای زنگ الکترونیکی. یک نور کوچک روشن می‌شود. چند صدای فشرده‌شدن کلید. سکوت مطلق. مجدداً چند صدای فشرده‌شدن کلید؛ این بار آهسته‌تر. صدای قهقهه‌ی بلند [که آرامش بیننده را مختل می‌کند]. دوربین به سمت نور کوچک حرکت می‌کند. نور کوچک ناگهان خاموش می‌شود. صدای خنده دور شده و پایان می‌یابد. صفحه مجدّداً کاملاً سیاه می‌شود‎. ‎

سکانس دوم:‎

دوربین روی دو نوجوان فوکوس کرده است. صدای سخنرانی از بلندگو می‌آید. هر دو کم سن و سال هستند و گلایه از خستگی‌های روزمره در چهره‌شان موج می‌زند. صدای بلندگو گوش‌خراش است. نوجوان عقب‌تر با موهای بور و قد کوتاه، چهره‌ی بشّاش‌تری دارد؛ حال آن‌که نوجوان جلویی با قامتی رشید، چهره‌ی مستحکم‌تری دارد. از حرکت لب‌هایشان نمی‌توان چیزی دریافت. [دوربین زوم این می‌کند.]‎ صدای بلندگو رفته رفته بم شده و صدای دو نوجوان واضح‌تر می‌شود‎.‎

‎ نوجوان عقب‌تر [ با لب‌خند شیطنت‌آمیز ] : ‎«جُک گوجه(‎‎مضمون این لطیفه، حکایت گوجه‌ای‌ست که به‌دلیل ازدحام سایر گوجه‌ها از پشت وانت حامل گوجه به داخل خیابان پرت شده و به‌شدّت له می‌شود‎(‎ رو شنیدی؟»‎

‎ نوجوان جلوتر [ با تلاش برای کنترل خنده‌ی قابل پیش‌بینی ] : ‎«نه!» ‎

[دوربین زوم اوت می‌کند‎.‎] نوجوان جلوتر چند جمله‌ی کوتاه می‌گوید که واضح نیست. [صدای خنده‌ی نوجوان جلوتر.]‎ هم‌زمان صدای خنده‌ی نوجوان پشت‌سری نوجوان عقبی صدای خنده‌ی نوجوان جلویی را همراهی می‌کند. صدای دو خنده با جلوه‌ی خاصی بر صدای سخن‌رانی غلبه می‌کند. تصاویر محو است؛ صداها نیز به‌تدریج محو می‌شوند. صفحه کاملاً سفید می‌شود. [صدای خنده].

‎‎ سکانس سوم‎:‎

دوربین روی هر سه نوجوان فوکوس کرده و پس از چند لحظه به‌سرعت زوم اوت می‌کند. هر دو نوجوان جلویی هم‌چنان دارند می‌خندند. صدای خنده‌ها کم‌تر و کم‌تر شده و در همان زمان، صدای بلندگو مجدّداً افزایش می‌یابد. نوجوان جلویی با نفر جلویی خود و نوجوان عقب‌تر از عقبی با نوجوان پشت‌سری خود آرام صحبت می‌کنند. صدای خنده مجدّداً بر صدای بلندگو چیره می‌شود‎.‎

مسئله

‎$n$‎ دانش‌پژوه در صف صبح‌گاه قرار دارند. شب گذشته به تعدادی از آن‌ها ‎«جُک گوجه‎» از طرف فرد ناشناسی از طریق پیام کوتاه‎ ارسال شده‌است.

می‌دانیم از دقیقه‌ی اوّل، در ابتدای هر دقیقه، هر کسی که ‎«جُک گوجه‎» را (به هر نحوی) شنیده باشد، آن را برای دو دانش‌پژوه جلویی و عقبی‌اش (در صورت وجود) تعریف می‌کند.

اگر برنامه‌ی صبح‌گاه تا دقیقه‌ی ‎$k$‎اُم طول بکشد، به فرد ناشناس کمک کنید تا بتواند تعداد افرادی که ‎«جُک گوجه‎» را نشنیده‌اند تعیین کند‎!‎

ورودی

  • در سطر اول ورودی ‎$n$‎ تعداد کل دانش‌پژوهان، ‎$m$‎ تعداد دانش‌پژوهانی که شب قبل جُک گوجه را به‌صورت پیام کوتاه دریافت کرده‌اند و سپس عدد ‎$k$‎، مّدت زمان برنامه‌ی صبح‌گاه آمده است. ‎ ‎
  • در سطر بعد ‎$m$‎ عدد که شماره‌ی دانش‌پژوهانی که جک را به‌صورت پیام کوتاه گرفته‌اند، نوشته شده‌اند. می‌دانیم دانش‌پژوهان، شماره‌های ‎$1$‎ تا ‎$n$‎ را دارند.
  • ‎ $0 \leq m \leq n \leq 200,000$‎.
  • ‎ $0 \leq k \leq 10^9$‎.

خروجی

در تنها سطر فایل خروجی تعداد دانش‌پژوهان ‎(بدشانس)‎ ای را بنویسید که پس از پایان مراسم صبح‌گاه، «جک گوجه‎» را نشنیده‌اند.

محدودیت‌ها

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

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

ورودي نمونه خروجي نمونه
17 3 2
3 7 16
4

ابزار صفحه