시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 2 | 0 | 0 | 0.000% |
Let h be a function acting on strings composed of the digits 0 and 1. The function h transforms the string w by replacing (independently and concurrently) every digit 0 with 1 and every digit 1 with the string ,,10”. For example h(,,1001”)=,,101110”, h(,,”)=,,” (i.e. h assigns an empty string to the empty string). Note that h is an injection, or a one-to-one function. By h_k we denote the function h composed with itself k times. In particular, h0 is the identity function h0(w)=w.
We are interested in the strings of the form hk(,,0”) for k=0,1,2,3,… This sequence begins with the following strings:
,,0”, ,,1”, ,,10”, ,,101”, ,,10110”, ,,10110101”.
We call the string x a substring of the string y if it occurs in y as a contiguous (i.e. one-block) subsequence. A sequence of integers k1,k2,…,kn is given. Your task is to check whether a string of the form hk1(,,0”)⋅hk2(,,0”)⋅⋅⋅hkn(,,0”) is a substring of hm(,,0”) for some m, and if it is, you shuold find minimal such m.
The first line of the standard input contains a single integer t, 1 ≤ t ≤ 13, denoting the number of test units. The first line of each test unit's description contains one integer n, 1 ≤ n ≤ 100,000. The second line of each description holds n non-negative integers k1,k2,…,kn, separated by single spaces. The sum of the numbers in the second line of any test unit description does not exceed 10,000,000.
Your programme should print out t 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 hk1(,,0”)⋅hk2(,,0”)⋅⋅⋅hkn(,,0”) is a substring of hm(,,0”) for some in that test unit, or NIE (no in Polish) otherwise.
2 2 1 2 2 2 0
TAK NIE
The string from the first test case is ,,110” - it is a substring of h4(,,0”)=,,10110”. In the second test unit there is a string ,,100”, which is not a substring of hm(,,0”) for any m.