Problem Statement
You are given
- The tree T has exactly n nodes (labeled 0 through n-1).
- S(T) modulo m equals r.
If there are such trees, return the smallest possible value S(T). Otherwise, return -1.
Definition
- Class:
- ExactTree
- Method:
- getTree
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int getTree(int n, int m, int r)
- (be sure your method is public)
Constraints
- n will be between 2 and 50, inclusive.
- m will be between 2 and 100, inclusive.
- r will be between 0 and m-1, inclusive.
Examples
4
100
9
Returns: 9
For a tree T on 4 vertices there are only two possible values of S(T): 9 and 10. (One tree that has S(T)=9 is a tree with the edges 0-1, 0-2, and 0-3. One tree that has S(T)=10 is a tree with the edges 0-1, 1-2, and 2-3.) We are only interested in trees T such that S(T) modulo 100 = 9. Given this constraint, the smallest actually possible value S(T) is 9.
4
100
10
Returns: 10
4
100
0
Returns: -1
6
2
0
Returns: 28
6
2
1
Returns: 25
25
100
0
Returns: 700
50
97
89
Returns: 2708
17
85
14
Returns: 354
49
27
24
Returns: 2616
30
74
12
Returns: 974
19
89
40
Returns: 396
42
11
5
Returns: 1798
4
46
35
Returns: -1
40
92
83
Returns: 1739
13
18
12
Returns: 174
14
6
3
Returns: 189
9
23
10
Returns: 102
44
36
17
Returns: 2177
50
29
27
Returns: 2724
26
88
19
Returns: 811
43
63
9
Returns: 1962
44
89
71
Returns: 2118
2
92
14
Returns: -1
28
48
16
Returns: 928
46
58
25
Returns: 2345
3
38
9
Returns: -1
4
68
58
Returns: -1
21
60
49
Returns: -1
16
36
3
Returns: 291
21
13
8
Returns: 502
9
94
25
Returns: -1
36
2
1
Returns: 1225
19
13
11
Returns: 388
35
55
44
Returns: 1474
43
39
21
Returns: 2088
20
39
37
Returns: 427
14
69
48
Returns: 255
37
39
30
Returns: 1512
8
29
20
Returns: 49
23
79
3
Returns: 714
31
10
7
Returns: -1
31
97
38
Returns: 1008
4
55
31
Returns: -1
44
21
18
Returns: 1929
9
11
10
Returns: 76
33
80
35
Returns: -1
31
55
14
Returns: 1114
26
92
32
Returns: 768
37
96
58
Returns: 1498
50
35
0
Returns: 2730