المپدیا

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

ابزار کاربر

ابزار سایت


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

Sepidedam

علی در هنگام انجام دوی صبحگاهی به دستگاه عجیبی برخورد کرد. در این دستگاه $n$ عدد دور دایره در جایگاه‌های $0$ تا $n - 1$ نوشته شده‌اند و یک دکمه زیر این دایره قرار داده شده است. پس از بررسی‌های فراوان علی به این نتیجه رسید که با زدن دکمه‌ی دستگاه عملیات زیر انجام می‌شود:

اگر پیش از زدن دکمه‌ی دستگاه در جایگاه $i$ ام عدد $a_i$ و پس از زدن دکمه‌ی دستگاه در این جایگاه عدد $b_i$ نوشته شده باشد:

$$b_i = a_{(i + c_0) \operatorname{mod} n} \oplus a_{(i + c_1) \operatorname{mod} n} \oplus \ldots \oplus a_{(i + c_{k - 1}) \operatorname{mod} n}$$

برنامه‌ای بنویسید که مشخص کند اعداد پس از $t$ بار فشرده شدن دکمه چه تغییری می‌کنند.

پیاده‌سازی

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

  • void getStatus(int n, int *a, int k, int *c, string ts, int *ans)

این تابع دقیقا یک‌بار فراخوانی می‌شود. آن را طوری پیاده‌سازی کنید که اعداد نهایی را در آرایه‌ی مربوطه بنویسد.

  • $n$: تعداد اعداد دستگاه
  • $a$: آرایه‌ای به طول $n$. در ابتدا در جایگاه $i$ $(0 \le i \le n - 1)$ ام دور دایره عدد $a_i$ نوشته شده است.
  • $k$: تعداد اعضای آرایه‌ی $c$
  • $c$: آرایه‌ای به طول $k$. معادل آرایه‌ی $c$ در متن سوال.
  • $ts$: تعداد دفعات فشرده شدن دکمه‌ی دستگاه در مبنای دو.
  • $ans$: آرایه‌ای به طول $n$. وضعیت دستگاه را، پس از $t$ بار فشرده شدن دکمه، در این آرایه بریزید.

ارزیاب نمونه

ارزیاب نمونه ورودی را به صورت زیر می‌خواند:

  1. در خط اول یک رشته به طول $n$ آمده است که هر حرف آن صفر یا یک است و حرف $i$ $(0 \le i \le n - 1)$ام آن برابر $a_i$ است.
  2. در خط دوم یک رشته به طول $n$ آمده است که هر حرف آن صفر یا یک است و اگر حرف $i$ $(0 \le i \le n - 1)$ ام آن یک باشد، عدد $i$ در دنباله‌ی $c$ آمده است.
  3. در خط سوم یک رشته آمده است که برابر با عدد $t$ در مبنای دو است.

زیرمسئله‌ها

  • زیرمسئله‌ی اول (۷۵ نمره): $k \times n \le 10^5$.
  • زیرمسئله‌ی دوم (۲۵ نمره): بدون محدودیت اضافی.

محدودیت‌ها

  • محدودیت زمان: ۵ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت
  • $1 \le n, k \le 10^5$
  • $1 \le |ts| \le 10^5$
  • حداکثر $15$ عدد یک در $ts$ وجود دارد.

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

ورودی نمونه خروجی نمونه
1010
0100
1
0101

ابزار صفحه