TheHexagonsDivTwo
SRM 457 · 2009-11-12 · by vexorian
SRM 457 · 2009-11-12 · by vexorian · Brute Force, Math
Problem Statement
Problem Statement
John and Brus are interested in a new game called "Hexagon Flower". The rules are simple. You are given a flower formed by seven hexagons arranged as follows:
The objective of the game is to place a number in each hexagon of the flower such that all of the following conditions are satisfied:
Given n and k, return the total number of distinct solutions. Two solutions are considered the same if you can rotate one to form the other.
For example, if n = 8 and k = 4, then:
The top three placements are not valid. The other three placements are valid, but the first two among them are considered equal since one can be rotated to become the other.
The objective of the game is to place a number in each hexagon of the flower such that all of the following conditions are satisfied:
- Each number is an integer between 1 and n, inclusive.
- Each number is distinct.
- For every pair of adjacent hexagons, if the numbers placed in them are a and b, then a%k != b%k.
Given n and k, return the total number of distinct solutions. Two solutions are considered the same if you can rotate one to form the other.
For example, if n = 8 and k = 4, then:
The top three placements are not valid. The other three placements are valid, but the first two among them are considered equal since one can be rotated to become the other.
Constraints
- n will be between 1 and 300, inclusive.
- k will be between between 1 and 9, inclusive.
Examples
0)
7 3 Returns: 0
There is no way to place all 7 numbers (1 through 7, inclusive) such that no two adjacent numbers are equal modulo 3.
1)
8 3 Returns: 24
2)
8 4 Returns: 256
3)
20 5 Returns: 4692480
4)
8 4 Returns: 256
Submissions are judged against all 113 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class TheHexagonsDivTwo with a public method long long count(int n, int k) · 113 test cases · 2 s / 256 MB per case