Problem Statement
The floor of our dining room is a rectangle divided into a grid of R by C unit square tiles. The tiles have integer coordinates ranging from (0, 0) to (R-1, C-1).
Some of the tiles are empty, others contain pillars that support the roof. There are at most N pillars (explained below).
We want to place a L x 1 dining table somewhere into the dining room. The table must be placed parallel to one of the sides and it must cover exactly L empty tiles.
In other words, the table must be placed either "horizontally" or "vertically", and it must avoid all pillars.
You are given the dimensions of the dining room and the table, and the coordinates of all pillars (as described below).
Return the number of ways in which the table can be placed.
In order to keep the input small, we will simply pick one specific pattern for the pillars:
- Let r(i) = (4*i*i + 7*i) modulo R.
- Let c(i) = (i*i*i + 8*i + 13) modulo C.
- For each i from 0 to N-1, inclusive, the tile with coordinates (r(i), c(i)) contains a pillar.
- No other tile contains a pillar.
Definition
- Class:
- DinnerTable
- Method:
- count
- Parameters:
- int, int, int, int
- Returns:
- long
- Method signature:
- long count(int R, int C, int L, int N)
- (be sure your method is public)
Notes
- The reference solution does not use any properties of the pattern of pillars. It can correctly solve the task for any configuration of N pillars.
- Watch out for integer overflow when computing the values r(i) and c(i).
- Different values of i may give you the same tile (r(i), c(i)). If that happens, there will be fewer than N pillars.
- For any valid input the return value is guaranteed to fit into a 64-bit signed integer variable.
Constraints
- R will be between 1 and 10^9, inclusive.
- C will be between 1 and 10^9, inclusive.
- L will be between 2 and 10^9, inclusive.
- N will be between 0 and 10^5, inclusive.
Examples
5
6
6
0
Returns: 5
The dining room has 5 rows by 6 columns. The dining table has length 6. There are no pillars. There are exactly 5 valid ways to place the table: it has to fill one of the rows.
5
6
5
0
Returns: 16
Same dining room as above, but now the table only has length 5. There are two ways to place it into each row (either it touches the left or the right side), and there is one way to place it into each column. That's a total of 5*2 + 6*1 = 16 ways.
5
6
7
0
Returns: 0
This table is too long for this dining room.
5
6
4
2
Returns: 20
The two pillars are at (0, 1) and at (1, 4). Thus, the dining room looks as follows ('O' is a pillar, '.' is an empty tile): .O.... ....O. ...... ...... ...... There are 11 ways to place the table "horizontally" and 9 ways to place it "vertically". Two of these are shown below, with 'X's denoting the table. .O.... XXXXO. ...... ...... ...... .O.... ...XO. ...X.. ...X.. ...X..
5
6
4
3
Returns: 20
The answer for N=3 is exactly the same as for N=2. This is because for i=2 we get the cell (r(i), c(i)) = (0, 1) again, thus there is no new pillar.
5
6
4
5
Returns: 16
The dining room now looks as follows: .O.... ....O. .O..O. ...... ......
100000
100000
10000
20000
Returns: 17666220715
Watch out for integer overflows!
4
1
2
100000
Returns: 0
This dining room is completely covered by pillars. There is no room at all for the table.
987654321
978653421
123456789
100000
Returns: 1690367251671856877
89877
99986
12345
100000
Returns: 13723698847
4718803
255999072
3176882
0
Returns: 1587748714453757
29944491
7
2
0
Returns: 389278376
1
1945526
24174
0
Returns: 1921353
7903922
34947
14318558
0
Returns: 0
2919165
35080
426
0
Returns: 203553062275
110
25260934
93
0
Returns: 3233389432
3013833
114494300
387439
0
Returns: 644606283270546
112321
7
938976
0
Returns: 0
94494
181
33064496
0
Returns: 0
85092
276590639
1193
0
Returns: 46741503836224
24
8945303
127377
6
Returns: 211629819
2
13860
183614149
3
Returns: 0
306
432
40807903
5
Returns: 0
268678067
234
27
1
Returns: 118755699515
858
5
14
2
Returns: 4212
2
580797
775021
10
Returns: 0
791
63
2316021
2
Returns: 0
123164334
6734477
19
8
Returns: 1658892410907764
556067011
151985874
519151
9
Returns: 168661075683554691
190
6971853
1971
90370
Returns: 1182025628
122
834068577
2
94703
Returns: 202678286839
6
19
956401
93356
Returns: 0
38
949044
3607615
91782
Returns: 0
59
9231579
4668061
96420
Returns: 132342051
197744
12938
15810
94907
Returns: 1481923430
504901299
1163439
1003
90010
Returns: 1174336467474492
3
104066
102
92029
Returns: 103965
1890
4183939
197167964
98246
Returns: 0
106560
3
729607861
96177
Returns: 0
5
2367
11
97564
Returns: 5020
3677
1
28
90012
Returns: 0
33531870
937591722
230
91672
Returns: 62878185040890704
58
81102786
4090
97795
Returns: 4335363407
318753615
55525680
187003764
95183
Returns: 7308452804019312
38560077
505
2536895
94136
Returns: 10951047632
4443723
39011912
23290
98319
Returns: 345699657880065
105719
143
355083
97999
Returns: 0
59268
49341891
10178987
95535
Returns: 1973213318208
21
94
2375
92321
Returns: 0
1362
18
457
95706
Returns: 10872
234
377248
4950119
95147
Returns: 0
68
5205
2478386
95231
Returns: 0
228748045
252093638
245112076
98038
Returns: 1596354311328517
2
1151487
161359710
97194
Returns: 0
152
3930714
13
93071
Returns: 1145461907
130030650
22891
3
95328
Returns: 5952802539280
679
300202
12
90724
Returns: 402250011
1
5806803
14243
96073
Returns: 0
359
286978148
838425
96910
Returns: 62016675639
236
113750028
7
93763
Returns: 53006216723
237379
8
46354791
96837
Returns: 0
9877000
7038066
304824124
91072
Returns: 0
21
11918
261091346
93235
Returns: 0
265257
131
93454
98721
Returns: 7559376
16290850
13638
36127049
99608
Returns: 0
110790068
4257065
66
95094
Returns: 943273551045083
11
1
14
97602
Returns: 0
4831
234731
4511476
91069
Returns: 0
850593
15
973634708
95449
Returns: 0
48
117239125
112
96184
Returns: 5616718906
3259
2
5128
99193
Returns: 0
19211
1
245957608
96931
Returns: 0
334
32214913
84877
91230
Returns: 6632096604
5
292
2
92009
Returns: 1486
405
132616266
2
99794
Returns: 107286160630
748
166
516071
98029
Returns: 0
868887352
127467781
2100
97011
Returns: 221508193639994887
113210308
13453473
937922
96168
Returns: 2927169960747045
6
990
40355407
91763
Returns: 0
669538
6270153
993417
95573
Returns: 3454773631841
9691851
2574514
11149
94266
Returns: 49764771215865
5992867
2784241
660951
90651
Returns: 27471429769297
7017546
8168619
762035
95299
Returns: 102944801639751
2574943
4557142
998888
94196
Returns: 16214047924100
5649323
6957630
699135
91827
Returns: 69684625724829
3547717
3062886
661626
93776
Returns: 17260450349492
4833801
4222105
493036
98646
Returns: 36267236158026
5819826
2718465
563582
95913
Returns: 26739818635048
1970976
2557558
975864
92911
Returns: 5564171143894
9572696
3916851
576125
99362
Returns: 67116080588772
8949742
5475312
679897
98877
Returns: 88077874455548
3555200
4280424
52782
95988
Returns: 30011976520162
6481748
2984631
524021
99974
Returns: 33640674301471
2956910
3343093
432190
90879
Returns: 16980379171720
7966989
5582566
585212
98839
Returns: 80918239510119
1352403
4442959
109863
92269
Returns: 11361533020759
8746078
9822639
710416
93412
Returns: 158505856582996
4691825
6634622
921919
91818
Returns: 51674769169248
4387618
9376161
385079
91959
Returns: 76911767569200