Problem Statement
Consider the following problem:
"In the country of Absurdistan there are N airports. Each airport is either big or small. It is known that for each big airport there are at least B flights leaving it, and for each small airport there are at most S flights leaving it. Each flight is bidirectional and connects exactly two airports. No two flights connect the same pair of airports. It is possible to travel from any airport to any other airport using some sequence of flights. Determine the number of big airports. Find all solutions."
Let A(N,B,S) be the number of solutions the above task has for a given triple N, B, S. You are given six
- Nlo <= N <= Nhi
- Blo <= B <= Bhi
- Slo <= S <= Shi
- S < B
Definition
- Class:
- BigAndSmallAirports
- Method:
- solve
- Parameters:
- int, int, int, int, int, int
- Returns:
- long
- Method signature:
- long solve(int Nlo, int Nhi, int Blo, int Bhi, int Slo, int Shi)
- (be sure your method is public)
Notes
- It is possible that all airports in the country are of the same kind (all big or all small).
Constraints
- Nhi will be between 1 and 10,000,000, inclusive.
- Nlo will be between 1 and Nhi, inclusive.
- Bhi will be between 1 and 200, inclusive.
- Blo will be between 1 and Bhi, inclusive.
- Shi will be between 1 and 200, inclusive.
- Slo will be between 1 and Shi, inclusive.
Examples
20
20
3
3
2
2
Returns: 21
For N=20, B=3, S=2 each number of big airports (from 0 to N, inclusive) is possible. The image below shows one possible network of airports and flights with 3 big airports (squares) and 17 small airports (circles).
1
1
10
10
2
2
Returns: 1
In the case N=1, B=10, S=2 there is a single airport. It cannot have 10+ outgoing flights, therefore it has to be small. If the airport is small, all conditions are satisfied. Therefore A(N,B,S)=1.
10
10
8
8
3
3
Returns: 6
10
100
13
15
18
22
Returns: 0
There are no triples (N,B,S) such that N, B, S lie within the given ranges and B < S. Therefore the answer is the sum of zero values, which equals 0.
30
32
8
10
6
8
Returns: 768
1
10000000
1
200
1
200
Returns: 995000296045760393
1234567
9876543
20
170
10
160
Returns: 614060525958171480
1
1
1
1
1
1
Returns: 0
1
1
2
2
1
1
Returns: 1
2
2
2
2
1
1
Returns: 1
3
3
2
3
1
1
Returns: 2
4
4
1
10
1
10
Returns: 45
1
19
1
24
1
25
Returns: 16537
2
15
2
15
2
125
Returns: 4995
351
673532
2
165
3
162
Returns: 2994071838351546
1
7465338
99
199
14
155
Returns: 353587193620875457
1
7382746
6
76
23
70
Returns: 38589512136590030
2842837
4337404
46
77
14
73
Returns: 8123640594958168
2694072
4915024
3
178
166
166
Returns: 101396694182364
18722
7363994
109
149
6
121
Returns: 126486994715372655
5563449
6191571
14
50
2
4
Returns: 409789782445683
3156400
7996470
9
131
16
27
Returns: 35465314863380184
1608841
8422041
3
10
53
120
Returns: 0
3
9612968
49
99
2
105
Returns: 169663259247864896
2
8589826
1
74
20
102
Returns: 54785463833512673
4621442
7365436
14
129
3
186
Returns: 130679672795188800
1517603
5326209
1
163
5
189
Returns: 163703731555528989
474239
670504
1
161
94
133
Returns: 213440796061500
3280093
5659808
15
85
37
116
Returns: 12509364962038224
1171667
6031756
1
69
12
151
Returns: 28935181332518625
643244
3156906
23
152
34
137
Returns: 33031858506691408
486358
1309619
3
93
84
126
Returns: 33267628428705
4805602
9656579
4
4
108
109
Returns: 0
3
8517749
11
38
60
82
Returns: 0
979260
1227372
67
89
73
175
Returns: 37229631551656
3512950
7739834
1
89
1
2
Returns: 4161869958799995
3052859
3542395
33
114
2
27
Returns: 3441710877679152
1011809
1552010
1
91
2
18
Returns: 953559578123217
3026418
4624589
3
185
160
172
Returns: 1510112101910178
648389
4238073
3
123
3
10
Returns: 8174043800109440
1603691
3904315
35
151
28
124
Returns: 45960839502435000
1
1122725
2
21
2
137
Returns: 119748905376604
2210879
4355962
32
38
62
110
Returns: 0
4033862
6524304
12
28
1
16
Returns: 3378845210774953
1627604
4386203
11
152
53
128
Returns: 38770113726793800
4565338
6756078
165
176
31
138
Returns: 16071886894798224
1673150
5481169
28
74
13
158
Returns: 24328711126797060
2873321
3783310
75
116
3
3
Returns: 127206858737070
1247795
5970387
2
154
148
187
Returns: 357929724926676
2561949
2562768
53
175
56
101
Returns: 9326937332810
7376709
7860444
58
64
13
28
Returns: 412762583020480
1
3171794
2
83
17
27
Returns: 3375226184364433
2
4849396
2
43
32
40
Returns: 740774667508602
3170985
7782763
89
176
3
190
Returns: 287841730512682500
1851436
3068748
15
28
3
93
Returns: 775628126238231
2146370
2647180
57
110
27
64
Returns: 2419868879237376
6942259
9883126
2
93
29
162
Returns: 51460491904552640
3066505
6551988
26
156
41
49
Returns: 16745792658076710
4781827
6602978
47
172
45
184
Returns: 84250431117047664
3
2500328
73
125
28
148
Returns: 11762474953235420
1157770
6894273
120
142
1
121
Returns: 64204917675505608
5669338
9995100
24
37
1
1
Returns: 474324524213358
470766
542408
90
134
20
54
Returns: 57162237432300
1200558
1975598
32
132
125
199
Returns: 34463137414692
556273
9228003
8
40
132
144
Returns: 0
7199383
8131827
20
22
1
137
Returns: 428865356402865
4276846
7507419
22
64
12
16
Returns: 4092519257270235
1181859
2186010
114
177
2
40
Returns: 4220554291689216
1
7047058
125
132
35
84
Returns: 9932209515433053
2
3451945
2
62
103
106
Returns: 0
1
2969005
15
78
6
7
Returns: 564159973678784
2238877
4477333
27
68
126
155
Returns: 0
522961
4045920
11
19
2
14
Returns: 861135574871880
2
792385
3
32
15
18
Returns: 19464167305272
355658
731090
62
75
62
68
Returns: 14280063446250
4922631
9642499
63
156
3
174
Returns: 344105675371082394
2
10000000
1
200
1
200
Returns: 995000296045740493
2
2
100
100
1
1
Returns: 1
100
100
200
200
1
1
Returns: 0
10
10
20
20
1
1
Returns: 0
5
5
4
4
1
1
Returns: 2
30
2000000
1
10
1
8
Returns: 88000113979825
41
8508
101
135
125
170
Returns: 1990833295