Problem Statement
There are N duck houses in the kingdom, conveniently numbered 1 through N. Currently, there are no roads between the houses. The king assigned Mr. Dengklek to build exactly M bidirectional roads, each connecting a pair of houses.
The king imposed two rules on Mr. Dengklek:
- Let A and B be two different houses. Mr. Dengklek may build roads connecting these two houses if and only if 0 < |A-B| <= K. After the road is built, both house number A and house number B are said to be incident to the road. For each such pair of houses Mr. Dengklek may build multiple roads, each connecting the two houses.
- Each house must be incident to an even number of roads. (Zero is also an even number.)
Definition
- Class:
- DengklekBuildingRoads
- Method:
- numWays
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int numWays(int N, int M, int K)
- (be sure your method is public)
Notes
- The houses are not required to be connected. There may be pairs of houses such that it is impossible to travel from one to another by only using the roads.
- The roads are allowed to cross arbitrarily. (If two roads cross, the crossing is built using bridges, so that each road only connects the two houses at its ends.)
Constraints
- N will be between 1 and 30, inclusive.
- M will be between 0 and 30, inclusive.
- K will be between 1 and 8, inclusive.
Examples
3
4
1
Returns: 3
These are the three ways to build the roads:
4
3
3
Returns: 4
These are the four ways to build the roads:
2
1
1
Returns: 0
It is impossible to make each house incident to an even number of roads if there is only one road.
5
0
3
Returns: 1
10
20
5
Returns: 26964424
30
30
8
Returns: 201860393
30
30
7
Returns: 145979048
30
30
6
Returns: 177956313
30
30
5
Returns: 244633725
30
30
4
Returns: 457088350
30
30
3
Returns: 488218396
30
30
2
Returns: 36571349
30
30
1
Returns: 532655639
2
0
1
Returns: 1
2
1
1
Returns: 0
2
30
1
Returns: 1
4
30
3
Returns: 41208
4
30
1
Returns: 136
6
30
5
Returns: 595145665
8
30
3
Returns: 898450917
7
8
6
Returns: 55041
16
28
1
Returns: 40116600
30
2
2
Returns: 57
30
2
1
Returns: 29
10
2
5
Returns: 35
25
13
7
Returns: 309349042
30
15
4
Returns: 543238700
27
27
6
Returns: 69218107
3
19
6
Returns: 45
1
30
8
Returns: 0
4
16
7
Returns: 2673
23
28
1
Returns: 319959386
16
18
4
Returns: 250757448
29
29
7
Returns: 85065498
30
27
7
Returns: 627690142
30
2
8
Returns: 204