ColourHolic
SRM 635 · 2014-08-25 · by Xellos0
Problem Statement
VendelÃn has a part-time job in an "all for 1 euro" bargain store. He was given the task of putting several items into a row on one long shelf in the display window.
VendelÃn is shape-blind: he only cares about the items' colours. This time, he sees that each of his items comes in one of just 4 colours: turquoise, magenta, beige and lavender (but don't worry, we've numbered them 0 through 3 for your convenience). Also, in order to attract customers, he wants each two adjacent items on the shelf to have different colours.
You're given an
Compute and return the number of sequences of items such that no two adjacent items share the same colour. Since this number can get very large, return it modulo 1,000,000,009.
Constraints
- n will contain exactly 4 elements.
- Each element of n will be between 0 and 50,000, inclusive.
- There will be at least 1 item, so the elements of n won't all be equal to 0.
- At least 2 elements of n won't exceed 200.
{1,0,2,3}
Returns: 10
There are 10 possible sequences of 1 turquoise (colour 0), 2 beige (colour 2) and 3 lavender (colour 3) items with no two adjacent items sharing the same colour. For example, (0,3,2,3,2,3) or (3,2,0,3,2,3) are valid sequences of colours. However, (3,2,2,3,2,3) isn't valid.
{1,1,1,1}
Returns: 24
All 4! permutations of these items are valid.
{42,42,42,9001}
Returns: 0
There are way too many items of colour 3. In any sequence, there would be two adjacent items of this colour.
{8,0,0,8}
Returns: 2
{0,5,1,3}
Returns: 4
{110,30000,200,29999}
Returns: 118115350
Make sure you're using 109+9 as the modulus!
Submissions are judged against all 81 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ColourHolic with a public method int countSequences(vector<int> n) · 81 test cases · 2 s / 256 MB per case