NITT1 - My Reaction when there is no internet connection

no tags 

There is college whose name will not be disclosed. To raise the level the college management installed wifi connections. There was poor hostel where there was a poor floor. The floor had n rooms. Three routers were setup just for that floor to increase the signal strength. Still there they weren't able to operate the internet. Also no router can hold more than the current connections from that wing. They finally found that if three adjacent room connects to a same router then there won't be an internet connection established. You know which room is connected to which router. Since they are very lazy (as it is the typical character of their college) they want to swap the router connection between certain room so that the number of unswapped rooms are maximum and also no three continuous rooms are connected to the same wifi router.

Input

First line T denoting the number of cases (T<=40)

For each line a string x is given which determines which denotes which room is connected to which router (size of x<=50)

Output

Output the maximum unswapped rooms which follows the above mentioned condition or output -1 if it is not possible to make a valid arrangement

Example

Input:
2
111222333
11111111322

Output:
6
7

hide comments
hodobox: 2017-08-06 20:39:12

the first time I had to use for cycles with depth 7 :P

enigmus: 2016-10-13 17:06:27

I've had such a hard time implementing solution to this problem. It's easy to think of a recursive solution, however implementing it as an iterative solution almost killed me.
Recursive solutions will not pass and complexity is O(9*n^3)

Baqir khan : 2016-07-13 22:20:31

Read the input line, which which which which :D

Rishav Goyal: 2015-07-12 18:45:50

not a bad problem

Alex Anderson: 2012-10-10 01:50:51

This was tricky. Nice.

AC Srinivas: 2012-10-02 06:45:05

1st case:
the routers at pos 3,4,7 (numbered 1,2,3 respectively) can be swapped among themselves to give 112322133 (one possible configuration), remaining 9-3=6 rooms are unswapped.
----------------------------------------------------
2nd case:
routers at pos 3,6,10,11(numbered 1,1,2,2 respectively) can be swapped among themselves to give 11211211311. 11-4=7 rooms unswapped.

Last edit: 2012-10-02 07:03:47
Damian Straszak: 2012-10-01 21:53:38

Could you explain the first testcase? This is not clear from the problem statement.


Added by:jack(chakradarraju)
Date:2012-09-29
Time limit:1s-3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64