A greenhouse has 9 soil-moisture sensors mounted in a fixed 3x3 frame and labeled 1 through 9 in reading order:
1 2 3
4 5 6
7 8 9
A technician calibrates some of the sensors in a specific order, using each sensor at most once. Two sensors that appear consecutively in the calibration order can normally be linked directly no matter what — except for eight specific pairs that sit exactly two grid cells apart in a straight line (a row, a column, or a diagonal) with exactly one other sensor physically between them. For those eight pairs, the two sensors may only be linked directly if the sensor sitting between them has already been calibrated at some earlier point in the sequence (not necessarily immediately before). The eight restricted pairs, each with its required in-between sensor, are: {1,3} needs 2; {1,7} needs 4; {1,9} needs 5; {3,7} needs 5; {3,9} needs 6; {7,9} needs 8; {2,8} needs 5; {4,6} needs 5. Every other pair of distinct sensors can always be linked directly, in any order.
Given two integers L and H, count the total number of distinct calibration sequences of length k, for every k with L <= k <= H, where a sequence is an ordered list of distinct sensor labels such that every consecutive pair in it can be linked directly under the rule above given everything calibrated earlier in that same sequence. Two sequences differ if they differ in length or in any position's label.
A single line with two space-separated integers L and H.
Print a single integer: the total number of valid calibration sequences of length k summed over every k with L <= k <= H.
Example 1
Input
1 1
Expected
9
Explanation
Only length-1 sequences are wanted. Any single one of the 9 sensors, calibrated alone, is trivially valid (there is no consecutive pair to check), so the count is 9.
Example 2
Input
2 2
Expected
56
Explanation
Only length-2 sequences are wanted. For most starting sensors, all 8 remaining sensors can follow directly since the pair is unrestricted or the needed in-between sensor requirement doesn't block a first move without any prior history in a way that changes the count for this particular length; walking through all 9 starting sensors and every valid second sensor under the pair rule (blocking exactly the 8 restricted pairs whose in-between sensor has not yet been calibrated) gives a total of 56 valid length-2 sequences.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →