In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
Let be a function acting on strings composed of the digits 0
and 1.
The function
transforms the string
by replacing (independently
and concurrently) every digit 0 with 1 and every digit
1 with the string
.
For example
,
(i.e.
assigns an empty string to the empty string).
Note that
is an injection, or a one-to-one function.
By
we denote the function
composed with itself
times.
In particular,
is the identity function
.
We are interested in the strings of the form
for
This sequence begins with the following strings:
,
,
,
,
,
.
We call the string a substring of the string
if it occurs
in
as a contiguous (i.e. one-block) subsequence.
A sequence of integers
is given.
Your task is to check whether a string of the form
is a substring of
for some
.
The first line of the standard input contains a single integer ,
, denoting the number of test units.
The first line of each test unit's description contains one integer
,
.
The second line of each description holds
non-negative integers
, separated by single spaces.
The sum of the numbers in the second line of any test unit description
does not exceed
.
Your programme should print out lines to the standard output,
one for each test unit.
Each line corresponding to a test unit should contain one word:
TAK (yes in Polish - if
is a substring of
for some
in that test unit,
or NIE (no in Polish) otherwise.
For the input data:
2 2 1 2 2 2 0
the correct result is:
TAK NIE
Explanation of the example:
The string from the first test unit is - it is a substring
of
for example.
In the second test unit there is a string
,
which is not a substring of
for any
.
Task authors: Wojciech Rytter and Bartosz Walczak.