IPS - Interleaved Periodic String
An interleaved periodic string S can be written down using the following procedure :
- Write down any two strings s1 and s2 of lengths p1 and p2 respectively. The strings must consist of only 0s and 1s, and can possibly be empty.
- Concatenate some copies of the string s1 to obtain string S1.
- Concatenate some copies of the string s2 to obtain string S2.
- Interleave the strings S1 and S2 to obtain S.
To interleave two strings, merge their characters arbitrarily, maintaining the relative order in which they occur in both strings. For example, the strings "101" and "011" can be interleaved to get "011011" or "101011", however they cannot be interleaved to form "110110". Given S, find the minimum possible value of (p1 + p2).
Input :
The input consists of multiple test cases. The first line contains the number of test cases T. Each of the next T lines contain a string S consisting of only 0's and 1's.
Input Constraints
1 ≤ T ≤ 20
1 ≤ length of S ≤ 16
Output :
Output T lines, one corresponding to each test case, containing the minimum value of (p1 + p2) for the corresponding test case.
Sample Input :
1
0101
Example Output :
2
hide comments
Ravi Kiran:
2010-03-01 11:12:14
I dont think this was that bad a question to be moved in to tutorial.
|
|
Pritam Bhattacharya:
2010-01-19 18:12:19
well, problems even easier than this one do exist in the classical problemset .. still, I may consider ! |
|
Luka Hrabar:
2010-01-19 18:12:19
Last edit: 2010-09-17 06:33:50 |
Added by: | Pritam Bhattacharya |
Date: | 2010-01-05 |
Time limit: | 0.100s |
Source limit: | 1000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: NODEJS OBJC PERL6 SQLITE VB.NET |
Resource: | ACM ICPC 2009 Regionals (Asia-Amritapuri site) |