Button Cycles

Problem #448  

Tags: unlabeled

Who solved this?

No translations... yet

Ann and Bob discovered two boxes of buttons. One contained round buttons and the other contained square buttons. We will represent a round button with the letter "O" and a square button with the letter "X". Ann put down a row of 5 buttons, containing 3 round buttons and 2 square buttons. The row is represented as OOXXO. Ann decided that it would be interesting to create further rows of buttons where each row would be derived from the row above by following a simple rule. Bob said that they should invent a rule which is easily modified so that they could investigate the way in which the rows of buttons evolved for different variations of the rule.

After some discussion Ann and Bob decided that the rule should be determined by a pair of numbers x and y. For each position in the new row, x and y would specify two positions in the row above. If the buttons in these positions are the same, we put a round button "O" in the new row. If the two buttons are different we put a square button "X" in the new row. If we begin with the row of 5 buttons OOXXO, we can number the positions from 1 to 5, going from left to right. If we want to find the correct button to go into position 2 on the next row, we count x places to the right of 2 and y places to the right of 2, in order to find the positions of the two buttons in the previous row to use for the comparison. If either, or both, of these counts take us past the end of the row, we simply continue counting from the start of the row. The following example should help to clarify the process.

Consider the rule x, y = 2, 3 and a first row of OOXXO. The 5 buttons on the next row are determined as follows:

New button 1:   Old buttons 3 and 4 are X and X so the new button is O
New button 2:   Old buttons 4 and 5 are X and O so the new button is X
New button 3:   Old buttons 5 and 1 are O and O so the new button is O
New button 4:   Old buttons 1 and 2 are O and O so the new button is O
New button 5:   Old buttons 2 and 3 are O and X so the new button is X

We see that the new row is OXOOX. If we apply the rule 3 times, starting with the row OOXXO, we get the 4 rows shown below:

OOXXO
OXOOX
OXXXX
OOXXO

Notice that the 4th row is the same as the first. 3 steps of the rule have returned the row to its starting position. If we continue applying the rule to this example we will find that rows repeat every 3 steps. Each of these rows is part of a cycle of length 3. However, some starting rows will never be repeated, no matter how many times the rule is applied. An example of such a row is XXOOX. Examining all possible starting rows of 5 buttons shows that 15 of these rows have a cycle length of 3. There is also a single example OOOOO which has a cycle length of 1. Note that the cycle length is the smallest number of steps needed to repeat a pattern. In the example above, it is obvious that rows repeat every 6 steps. However, this does not constitute a cycle of length 6.

In this problem, you will be given a row of buttons (with some length N), which is guaranteed to be part of a cycle when the given rule (x and y) is applied. You are asked to find the length of the cycle and the number of different possible starting rows (of the same length N, using the same rule x,y) which are part of a cycle having the same cycle length as the example.

In order to find an efficient solution to this problem, you will probably need to use some mathematical ideas. However, there is no need to use any mathematics which has not already been relevant to a number of other Code Abbey problems. An efficient solution in normal Python solves the problem in a few seconds at most.

Input and Answer The first line of the problem will be a single integer T denoting the number of test cases. Each test case has two lines of data. The first of these contains 3 integers: The row length N, followed by x and y (the rule to use). The second of the two lines contains a string showing the arrangement of N buttons to be used for the starting row. For each test case give the cycle length of the starting row, followed by a space and then the number of different starting rows with this cycle length. Combine all answers into a single string, separated by single spaces.

Example:

input:
2
5 2 3
OOXXO
21 4 8
OXOXOXOXOXOXOXOXOXOXO

answer:
3 15 63 1048068
You need to login to get test data and submit solution.