Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:آزمون های اینترنتی ۸۹ تا ۹۱:سوال ۷۲

Words

اگر ‎w‎ یک رشته از کاراکترهای ‎0‎ و ‎1‎ باشد، ‎h(w)‎ رشته‌ای است که به‌جای هر کاراکتر ‎0 از w‎ یک کاراکتر ‎1‎ قرار می‌دهد و به‌جای هر کاراکتر ‎1 از w‎ یک رشته ‎10‎ قرار می‌دهد. برای مثال ‎h(1001)‎ برابر است با ‎101110. حال توابع زیر از روی ‎h‎ تعریف می‌شود:

  • h0(w)=w
  • h1(w)=h(w)
  • hk>1(w)=h(hk1(w))

به شما ‎n‎ عدد ‎k1‎ تا ‎kn‎ داده شده است، شما باید تحقیق کنید آیا عدد ‎m‎ وجود دارد که رشته ‎hk1(0)+hk2(0)++hkn(0)‎ زیررشته ای از ‎hm(0)‎ باشد یا نه.

‎ ‎a+b‎ رشته‌ای است که از کنار هم قرار دادن دو رشته ‎a‎ و ‎b‎ به‌دست می آید‎.

ورودی

  • در سطر اول ورودی، عدد ‎1t10‎ نشان‌دهنده تعداد تست‌ها آمده است.
  • در سطر اول هر تست، عدد ‎1n105‎ آمده است.
  • در سطر دوم هر تست، ‎n‎ عدد ‎k1‎ تا ‎kn‎ آمده‌اند.
  • تمام اعداد ورودی کم‌تر یا مساوی ‎109‎ هستند.‎

خروجی

به ازای هر تست در صورتی که عدد ‎m‎ وجود دارد عبارت ‎TAK‎ و در غیر این صورت عبارت ‎NIE‎ را چاپ کنید.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
2‎
2‎
1 2‎
2‎
2 0
TAK
‎NIE

ابزار صفحه