|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|1 초||1024 MB||0||0||0||0.000%|
After a successful presentation of your coding skills on the Fizz Buzz problem you have advanced to the second round of interviews for your dream job of code ninja at FizzBuzz Corp. In this interview you will tackle the Generalized Fizz Buzz problem.
Generalized Fizz Buzz is similar to the original Fizz Buzz. The program must print positive integers starting from 1, but some special numbers (and their multiples) should be replaced by strings. If something is divisible by multiple special numbers, it must be replaced by a concatenation of all their strings.
In this problem, your task isn’t to implement Generalized Fizz Buzz. Instead, you will be given a sequence and you need to decide whether it can be the output of a Generalized Fizz Buzz program.
A particular instance of Generalized Fizz Buzz is defined by the following parameters:
Their meaning is as follows:
For example, the original Fizz Buzz corresponds to k = 2, d = (3, 5), and s = (
buzz). The correct output of that program for n = 17 would be:
1 2 fizz 4 buzz fizz 7 8 fizz buzz 11 fizz 13 14 fizzbuzz 16 17
Note that instead of 15 we printed the concatenation of s1 (
fizz) and s2 (
buzz) because 15 is divisible both by d1 (3) and by d2 (5). Also note that you cannot print
buzzfizz for 15 because you cannot change the order of the si when concatenating them.
Monika has also written her own implementation of a Generalized Fizz Buzz program. Monika’s program can only handle inputs where each of the strings si has between 1 and 25 characters, inclusive. (Her program can handle arbitrarily large values of k and di.)
Monika has shown you a sequence of labels ℓ1, …, ℓn. Find the largest q such that the prefix ℓ1, …, ℓq can be the output of Monika’s program.
The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.
Each test case consists of two lines. The first line contains a positive integer n ≤ 1000: the number of labels in the sequence you were given. The second line contains the sequence: n non-empty tokens ℓ1, …, ℓn separated by single spaces. Each token will only contain digits and lowercase English letters.
For each test case output one line with the corresponding integer q.
5 7 mlem mlem mlem mlem mlem mlem fail 7 1 qizz quzz qizz 5 quzzqizz 007 8 1 2 3 4 hunter2 is my password 2 haha hahahaha 9 1 bat 3 batman robin batbat 7 batmanman 9
6 5 4 2 9
mlem. Both Samko’s and Monika’s program can handle this input, so for each of them the answer is 6.
qizzand 3 with
quzz. The first five tokens match that sequence, but the next one should be
quzzqizz, and the last one should be
hunter2is wrong because it contains both letters and numbers.
haha). Note that the strings si do not have to be distinct.
bat, 4 was replaced by
man, 5 by
robin, 6 also by
bat, and 8 also by